It is well known that selecting a good Mixed Integer Programming (MIP) formulation is crucial for an effective solution with state-of-the art solvers. While best practices and guidelines for constructing good formulations abound, there is rarely a systematic construction leading to the best possible formulation. We introduce embedding formulations and complexity as a new MIP … Read more
We describe new computer-based search strategies for extreme functions for the Gomory–Johnson infinite group problem. They lead to the discovery of new extreme functions, whose existence settles several open questions. ArticleDownload View PDF
The “sequential ordering problem” (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernández & Salazar introduced a “multi-commodity flow” (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables … Read more
We propose a novel method to fi nd Nash equilibria in games with binary decision variables by including compensation payments and incentive-compatibility constraints from non-cooperative game theory directly into an optimization framework in lieu of using first order conditions of a linearization, or relaxation of integrality conditions. The reformulation off ers a new approach to obtain and … Read more
We study a two-stage mixed-integer linear program (MILP) with more than 1 million binary variables in the second stage. We develop a two-level approach by constructing a semi-coarse model (coarsened with respect to variables) and a coarse model (coarsened with respect to both variables and constraints). We coarsen binary variables by selecting a small number … Read more
Given a mixed-integer set defined by linear inequalities and integrality requirements on some of the variables, we consider extended formulations of its continuous (LP) relaxation and study the effect of adding cutting planes in the extended space. In terms of optimization, extended LP formulations do not lead to better bounds as their projection onto the … Read more
A vast number of causal inference studies use matching techniques, where treatment cases are matched with similar control cases. For observational data in particular, we claim there is a major source of uncertainty that is essentially ignored in these tests, which is the way the assignments of matched pairs are constructed. It is entirely possible, … Read more
Transport networks with hub structure organise the exchange of shipments between many sources and sinks. All sources and sinks are connected to a small number of hubs which serve as transhipment points, so that only few, strongly consolidated transport relations exist. While hubs and detours lead to additional costs, the savings from bundling shipments, i.e. … Read more
Fitting piecewise affine models to data points is a pervasive task in many scientific disciplines. In this work, we address the k- Piecewise Affine Model Fitting with Pairwise Linear Separability problem (k-PAMF-PLS) where, given a set of real points and the corresponding observations, we have to partition the real domain into k pairwise linearly separable … Read more
With the fast-growing demand in the electricity market of the last decades, attention has been focused on alternative and flexible sources of energy such as hydro valleys. Managing the hydroelectricity produced by the plants in hydro valleys is called the hydro unit commitment problem. This problem consists in finding the optimal power production schedule of … Read more