Split cuts are arguably the most effective class of cutting planes within a branch-and-cut framework for solving general Mixed-Integer Programs (MIP). Sparsity, on the other hand, is a common characteristic of MIP problems, and it is an important part of why the simplex method works so well inside branch-and-cut. In this work, we evaluate the … Read more
Given a point x inside a polytope P and a direction d, the projection of x along d asks to find the maximum step length t such that x+td is feasible; we say x+td is a pierce point because it belongs to the boundary of P. We address this projection sub-problem with arbitrary interior points … Read more
We consider an extended version of the classical Max-k-Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The … Read more
We give a variant of Basu–Hildebrand–Molinaro’s approximation theorem for continuous minimal valid functions for Gomory–Johnson’s infinite group problem by piecewise linear two-slope extreme functions [Minimal cut-generating functions are nearly extreme, IPCO 2016]. Our theorem is for piecewise linear minimal valid functions that have only rational breakpoints (in 1/q Z for some q ∈ N) and … Read more
We present an algorithm for finding the complete Pareto frontier of biobjective integer programming problems. The method is based on the solution of a finite number of integer programs. The feasible sets of the integer programs are built from the original feasible set, by adding cuts that separate efficient solutions. Providing the existence of an … Read more
We consider the integer points in a unimodular cone K ordered by a lexicographic rule defined by a lattice basis. To each integer point x in K we associate a family of inequalities (lex-inequalities) that defines the convex hull of the integer points in K that are not lexicographically smaller than x. The family of … Read more
State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics … Read more
Empty freight car allocation problems as well as eet sizing problems depict highly important topics in the eld of railway cargo optimization. Fleet sizing is mainly used in order to nd the minimal number of freight cars ( xed costs) needed to operate the transportation network successfully (e.g. satisfy customer demands). After a consignment is transported … Read more
Within this work, we present a warm-started algorithm for Model Predictive Control (MPC) of switched nonlinear systems under combinatorial constraints based on Combinatorial Integral Approximation (CIA). To facilitate high-speed solutions, we introduce a preprocessing step for complexity reduction of CIA problems, and include this approach within a new toolbox for solution of CIA problems with … Read more
In spite of being an extremely successful method to tackle mathematical programs involving a very large number of variables, Column Generation (CG) is known to suffer from stabilization issues which can slow down its convergence significantly. In this article, we propose a new parameter-free stabilization technique for CG based on solving a lexicographic pricing problem. … Read more