Semi-Continuous Cuts for Mixed-Integer Programming

Ismael de Farias (defariasbuffalo.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

Citation:

Download: [PDF]

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

Modify/Update this entry