Partial cover and complete cover inequalities (Q1331885): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0167-6377(94)90010-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2042428770 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Pivot and Complement–A Heuristic for 0-1 Programming / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Facets of the Knapsack Polytope From Minimal Covers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Solving Large-Scale Zero-One Linear Programming Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Heuristic algorithms for the multiple knapsack problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4040221 / rank | |||
Normal rank |
Latest revision as of 17:30, 22 May 2024
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