The p-center problem: Using equivalent instances to obtain better results
ArticleDownload View PDF
(Mixed) Integer Linear Programming
An algorithmic framework in the criterion space for bi-objective mixed integer linear problems
We propose a criterion space search algorithm for bi-objective mixed integer linear programming problems. The Pareto frontier of these problems can have a complex structure, as it can include isolated points, open, half-open and closed line segments. Therefore, its exact detection is an achievable though hard computational task. Our algorithm works by alternating the resolution … Read more
Optimal Sports League Realignment
We consider approaches for optimally organizing competitive sports leagues in light of competitive and logistical considerations. A common objective is to assign teams to divisions so that intradivisional travel is minimized. We present a bilinear programming formulation based on k-way equipartitioning, and show how this formulation can be extended to account for additional constraints and … Read more
Mixed-Integer Linear Optimization for Cardinality-Constrained Random Forests
Random forests are among the most famous algorithms for solving classification problems, in particular for large-scale data sets. Considering a set of labeled points and several decision trees, the method takes the majority vote to classify a new given point. In some scenarios, however, labels are only accessible for a proper subset of the given … Read more
Detecting and Handling Reflection Symmetries in Mixed-Integer (Nonlinear) Programming
Symmetries in mixed-integer (nonlinear) programs (MINLP), if not handled appropriately, are known to negatively impact the performance of (spatial) branch-and-bound algorithms. Usually one thus tries to remove symmetries from the problem formulation or is relying on a solver that automatically detects and handles symmetries. While modelers of a problem can handle various kinds of symmetries, … Read more
Spatial branch-and-bound for nonconvex separable piecewise linear optimization
Nonconvex separable piecewise linear functions (PLFs) frequently appear in applications and to approximate nonlinearitites. The standard practice to formulate nonconvex PLFs is from the perspective of discrete optimization, using special ordered sets and mixed integer linear programs (MILPs). In contrast, we take the viewpoint of global continuous optimization and present a spatial branch-and-bound algorithm (sBB) … Read more
Extended Formulations for Control Languages Defined by Finite-State Automata
Many discrete optimal control problems feature combinatorial constraints on the possible switching patterns, a common example being minimum dwell-time constraints. After discretizing to a finite time grid, for these and many similar types of constraints, it is possible to give a description of the convex hull of feasible (finite-dimensional) binary controls via extended formulations. In … Read more
The Multi-Stop Station Location Problem: Exact Approaches
The multi-stop station location problem (MSLP) aims to place stations such that a set of trips is feasible with respect to length bounds while minimizing cost. Each trip consists of a sequence of stops that must be visited in a given order, and a length bound that controls the maximum length that is possible without … Read more
Heuristic Methods for Γ-Robust Mixed-Integer Linear Bilevel Problems
Due to their nested structure, bilevel problems are intrinsically hard to solve–even if all variables are continuous and all parameters of the problem are exactly known. In this paper, we study mixed-integer linear bilevel problems with lower-level objective uncertainty, which we address using the notion of Γ-robustness. To tackle the Γ-robust counterpart of the bilevel … Read more
Tricks from the Trade for Large-Scale Markdown Pricing: Heuristic Cut Generation for Lagrangian Decomposition
In automated decision making processes in the online fashion industry, the ‘predict-then-optimize’ paradigm is frequently applied, particularly for markdown pricing strategies. This typically involves a mixed-integer optimization step, which is crucial for maximizing profit and merchandise volume. In practice, the size and complexity of the optimization problem is prohibitive for using off-the-shelf solvers for mixed … Read more