Partial cover and complete cover inequalities (Q1331885)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Partial cover and complete cover inequalities |
scientific article |
Statements
Partial cover and complete cover inequalities (English)
0 references
23 November 1995
0 references
The problem considered in this paper is of the form: \(\max cx\) s.t. \(ax\leq a_0\), \(bx\geq b_0\), \(x\in \{0, 1\}^n\), where \(c,a,b\in \mathbb{Z}^n_+\) and \(a_0\), \(b_0\) are positive integers. Additional constraints (inequalities) violated by a given optimal solution \(x^*\) of the associated linear problem satisfying \(0\leq x^*\leq 1\) are derived. These inequalities cut off some solutions of the associated linear problem which are not feasible for the original one. The authors state the conditions under which the inequalities of this type exist and propose heuristics to determine them. Computational results of an iterative procedure, where in each iteration the associated linear problem with additional inequalities is solved, are presented in the last part of the paper. The results show that the proposed inequalities are stronger than the classical cover inequalities.
0 references
0-1 integer problems
0 references
knapsack constraints
0 references
heuristics
0 references
cover inequalities
0 references