In this report, we present the BOBILib, a collection of more than 2500~instances of mixed integer linear bilevel optimization problems. The goal of this library is to make a large and well-curated set of test instances freely available for the research community so that new and existing algorithms in bilevel optimization can be tested and … Read more
In the context of mixed-integer nonlinear problems (MINLPs), it is well-known that strong duality does not hold in general if the standard Lagrangian dual is used. Hence, we consider the augmented Lagrangian dual (ALD), which adds a nonlinear penalty function to the classic Lagrangian function. For this setup, we study conditions under which the ALD … Read more
\(\) We analyze the inverse of integer programs (IPs) using the Gomory corner relaxation (GCR). We prove the inverse GCR is equivalent to the inverse of a shortest path problem, yielding a polyhedral representation of the GCR inverse-feasible region. We propose a linear program formulation for the inverse GCR under \(L_1\) and \(L_\infty\) norms.The inverse … Read more
We consider the chance-constrained program (CCP) with random right-hand side under a finite discrete distribution. It is known that the standard mixed integer linear programming (MILP) reformulation of the CCP is generally difficult to solve by general-purpose solvers as the branch-and-cut search trees are enormously large, partly due to the weak linear programming relaxation. In … Read more
Article Download View The p-center problem: Using equivalent instances to obtain better results
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
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
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
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
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 optimisation, 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