Semi-continuous cuts for mixed-integer programming

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

7 Scopus citations

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 that are valid for the semi-continuous knapsack polyhedron can be derived and used as cuts 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 "textbook" approach of modeling semi-continuous constraints through the introduction of auxiliary binary variables in the model.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsDaniel Bienstock, George Nemhauser
PublisherSpringer-Verlag
Pages163-177
Number of pages15
ISBN (Print)3540221131, 9783540221135
DOIs
StatePublished - 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3064
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Branch-and-cut
  • Disjunctive programming
  • Mixed-integer programming
  • Polyhedral combinatorics
  • Semi-continuous variables

Fingerprint Dive into the research topics of 'Semi-continuous cuts for mixed-integer programming'. Together they form a unique fingerprint.

Cite this