Implementations of the Simplex method differ only in very specific aspects such as the pivot rule. Similarly, most relaxation methods for mixed-integer programming differ only in the type of cuts and the exploration of the search tree. Implementing instances of those frameworks would therefore be more efficient if linear and mixed-integer programming solvers let users … Read more
We are interested in methods to solve mixed-integer nonlinear optimal control problems (MIOCPs) constrained by ordinary di erential equations and combinatorial constraints on some of the control functions. To solve these problems we use a rst discretize, then opti- mize approach to get a specially structured mixed-integer nonlinear program (MINLP). We decompose this MINLP into an … 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
Mathematical programs whose formulation is symmetric often take a long time to solve using Branch-and-Bound type algorithms, because of the several symmetric optima. One of the techniques used to decrease the adverse effects of symmetry is adjoining symmetry breaking constraints to the formulation before solving the problem. These constraints aim to make some of the … Read more
We describe a procedure to reduce variable bounds in Mixed Integer Nonlinear Programming (MINLP) as well as Mixed Integer Linear Programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction technique extends the implied bounds procedure used in MINLP and MILP and … Read more
The feasibility pump (FP) [5,7] has proved to be a successful heuristic for finding feasible solutions of mixed integer linear problems (MILPs). FP was improved in [1] for finding better quality solutions. Briefly, FP alternates between two sequences of points: one of feasible so- lutions for the relaxed problem (but not integer), and another of … Read more
One of the main concerns of national statistical agencies (NSAs) is to publish tabular data. NSAs have to guarantee that no private information from specific respondents can be disclosed from the released tables. The purpose of the statistical disclosure control field is to avoid such a leak of private information. Most protection techniques for tabular … Read more
We address a 1-dimensional cutting stock problem where, in addition to trim-loss minimization, we require that the set of cutting patterns forming the solution can be sequenced so that the number of stacks of parts maintained open throughout the process never exceeds a given $s$. For this problem, we propose a new integer linear programming … Read more
The Quadratic Assignment Problem (QAP) can be solved by linearization, where one formulates the QAP as a mixed integer linear programming (MILP) problem. On the one hand, most of these linearization are tight, but hardly exploited within a reasonable computing time because of their size. On the other hand, Kaufman and Broeckx formulation [1] is … Read more
In this paper, a variant of the Traveling Salesman Problem with Time Windows is considered, which consists in minimizing the sum of travel durations between a depot and several customer locations. Two mixed integer linear programming formulations are presented for this problem: a classical arc flow model and a sequential assignment model. Several polyhedral results … Read more