A polyhedral study of the semi-continuous knapsack problem (Q2434996): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 08:11, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A polyhedral study of the semi-continuous knapsack problem |
scientific article |
Statements
A polyhedral study of the semi-continuous knapsack problem (English)
0 references
3 February 2014
0 references
This paper is on the inequality description of the closure of the convex hull of a knapsack constraint with variables belonging to the union of two intervals, i.e. the semi-continuous knapsack polyhedron. The authors study the inequalities of the polyhedron and use the inequalities as cuts in a branch and cut. A main contribution is the lifting technique and lifting results for non-trivial inequalities. Lifting coefficients of all variables can be approximated in quadratic time. Computational results show the effectiveness of semi-continuous cuts on real instances of the stochastic unit commitment problem with linear costs and on randomly generated linear programs with semi-continuous variables. The unit commitment problem is to find the right time to start and stop power generating units in order to minimize the total operating cost subject to satisfying the demand and technological constraints.
0 references
semi-continuous variables
0 references
mixed-integer programming
0 references
disjunctive programming
0 references
polyhedral combinatorics
0 references
branch and cut
0 references
unit commitment problem
0 references