A result in surrogate duality for certain integer programming problems
Aggregation is an approach for solving optimization problems with simultaneous linear equations as constraints. The system of equations is relaxed to only one equation (the surrogate constraint by a linear combination of the original constraints, i.e. by multiplying the system by an aggregating vector. For linear and integer linear problems there exist aggregating vectors such that the optima of the original problem (OP) and of the relaxed problem (RP) coincide. As the authors show this result is incorrect for mixed-integer programming problems. An example with a 2*4 constraint matrix is proposed. There is a gap between the optimal solutions of the OP and the RP for any aggregating vector.
scientific article; zbMATH DE number 4106612