New symmetries in mixed-integer linear optimization

We present two novel applications of symmetries for mixed-integer linear programming. First we propose two variants of a new heuristic to improve the objective value of a feasible solution using symmetries. These heuristics can use either the actual permutations or the orbits of the variables to find better feasible solutions. Then we introduce a new … Read more

The Value Function of a Mixed-Integer Linear Program with a Single Constraint

The value function of a mixed-integer linear program (MILP) is a function that returns the optimal solution value as a function of the right-hand side. In this paper, we analyze the structure of the value function of a MILP with a single constraint. We show that the value function is uniquely determined by a finite … Read more

Duality for Mixed-Integer Linear Programs

This paper is a survey of and some minor extensions to the theory of duality for mixed-integer linear programs. The theory of duality for linear programs is well-developed and has been extremely successful in both theory and practice. Much of this broad framework can be extended to MILPs in principle, but this has proven largely … Read more