Optimization Online


Branch-and-Cut for Separable Piecewise Linear Optimization: New Inequalities and Intersection with Semi-Continuous Constraints

Ming Zhao(ming.zhao***at***sas.com)
Ismael de Farias(ismael.de-farias***at***ttu.edu)

Abstract: We give new facets and valid inequalities for the separable piecewise linear optimization knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. In a companion paper (de Farias, Gupta, Kozyreff, Zhao, 2011) we demonstrate the efficiency of the inequalities when used as cuts in a branch-and-cut scheme.

Keywords: piecewise linear optimization, mixed-integer programming, knapsack problem, special ordered set, semi-continuous variables, polyhedral method, branch-and-cut

Category 1: Integer Programming

Citation: Department of Industrial Engineering, Texas Tech, 2011

Download: [PDF]

Entry Submitted: 03/23/2011
Entry Accepted: 03/23/2011
Entry Last Modified: 03/23/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society