Partial cover and complete cover inequalities (Q1331885)

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.