Optimization Online


Semi-Continuous Cuts for Mixed-Integer Programming

Ismael de Farias (defarias***at***buffalo.edu)

Abstract: We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Besides being important in its own right, the semi-continuous knapsack problem is a relaxation of general mixed-integer programming. We show how strong inequalities valid for the semi-continuous knapsack polyhedron can be derived and used in a branch-and-cut scheme for mixed-integer programming and problems with semi-continuous variables. We present computational results that demonstrate the effectiveness of these inequalities, which we call collectively semi-continuous cuts. Our computational experience also shows that dealing with semi-continuous constraints directly in the branch-and-cut algorithm through a specialized branching scheme and semi-continuous cuts is considerably more practical than the

Keywords: mixed-integer programming, semi-continuous variables, disjunctive programming, polyhedral combinatorics, branch-and-cut

Category 1: Integer Programming


Download: [PDF]

Entry Submitted: 12/07/2003
Entry Accepted: 12/08/2003
Entry Last Modified: 12/07/2003

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