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.
- Aggregating diophantine equations
- Aggregation of constraints in integer programming
- Equivalent knapsack‐type formulations of bounded integer linear programs: An alternative approach
- Technical Note—Solving Integer Programming Problems by Aggregating Constraints
- Transformation of integer programs to knapsack problems
- Aggregation of constraints in integer programming
- Exact algorithm for the surrogate dual of an integer programming problem: Subgradient method approach
- Zero duality gap in integer programming: \(P\)-norm surrogate constraint method
- Optimal constraints aggregation method for ILP
- An aggregate function method for integer programming
- scientific article; zbMATH DE number 4039640 (Why is no real title available?)
- On generalized surrogate duality in mixed-integer nonlinear programming
- How effective is aggregation for solving 0-1 models?
- On the existence of duality gaps for mixed integer programming
- On zero duality gap in surrogate constraint optimization: the case of rational-valued functions of constraints
This page was built for publication: A result in surrogate duality for certain integer programming problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1122485)
