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 graph partition problem is the problem of partitioning the vertex set of a graph into a fixed number of sets of given sizes such that the total weight of edges joining different sets is optimized. In this paper we simplify a known matrix-lifting semidefinite programming relaxation of the graph partition problem for several classes … Read more
We address the exact solution of a very challenging (and previously unsolved) instance of the quadratic 3-dimensional assignment problem, arising in digital wireless communications. The paper describes the techniques developed to solve this instance to proven optimality, from the choice of an appropriate mixed-integer programming formulation, to cutting planes and symmetry handling. Using these techniques … Read more
After an introduction to main ideas of semi-infinite optimization, this article surveys recent developments in theory and numerical methods for standard and generalized semi-infinite optimization problems. Particular attention is paid to connections with mathematical programs with complementarity constraints, lower level Wolfe duality, semi-smooth approaches, as well as branch and bound techniques in adaptive convexification procedures. … Read more
In this paper we examine the impact of using the Sherali-Adams procedure on highly symmetric integer programming problems. Linear relaxations of the extended formulations generated by Sherali-Adams can be very large, containing on the order of n choose d many variables for the level-d closure. When large amounts of symmetry are present in the problem … Read more
Symmetry plays an important role in optimization. The usual approach to cope with symmetry in discrete optimization is to try to eliminate it by introducing artificial symmetry-breaking conditions into the problem, and/or by using an ad-hoc search strategy. In this paper we argue that symmetry is instead a beneficial feature that we should preserve and … Read more
We study the problem of packing equal circles in a square from the mathematical programming point of view. We discuss different formulations, we analyse formulation symmetries, we propose some symmetry breaking constraints and show that not only do they tighten the convex relaxation bound, but they also ease the task of local NLP solution algorithms … Read more
The presence of symmetry is common in certain types of scheduling problems. Symmetry can occur when one is scheduling a collection of jobs on multiple identical machines, or if one is determining production schedules for identical machines. General symmetry-breaking methods can be strengthened by taking advantage of the special structure of the symmetry group in … Read more
Computing the 1-width of the incidence matrix of a Steiner Triple System gives rise to small set covering instances that provide a computational challenge for integer programming techniques. One major source of difficulty for instances of this family is their highly symmetric structure, which impairs the performance of most branch-and-bound algorithms. The largest instance in … Read more
If a mathematical program (be it linear or nonlinear) has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for automatically finding the formulation group of any given Mixed-Integer Nonlinear Program, and reformulating the problem so … Read more