Integer programming formulations describe optimization problems over a set of integer points. A fundamental problem is to determine the minimal size of such formulations, in particular, if the size of the coefficients or sparsity of the constraints is bounded. This article considers lower and upper bounds on these sizes both in the original and in … Read more
We propose a method for solving mixed-integer nonlinear programs (MINLPs) to global optimality by discretization of occuring nonlinearities. The main idea is based on using piecewise linear functions to construct mixed-integer linear program (MIP) relaxations of the underlying MINLP. In order to find a global optimum of the given MINLP we develope an iterative algorithm … Read more
We present a branch-and-cut algorithm for solving discrete bilevel linear programs where the upper-level variables are binary and the lower-level variables are either pure integer or pure binary. This algorithm performs local search to find improved bilevel feasible solutions. We strengthen the relaxed node subproblems in the branch-and-cut search tree by generating cuts to eliminate … Read more
The aim of Network Design Problem with Vulnerability Constraints (NDPVC), introduced by Gouveia and Leitner [EJOR, 2017], is to design survivable telecommunications networks that impose length bounds on the communication paths of each commodity pair, before and after the failure of any k links. This problem was proposed as an alternative to the Hop-Constrained Survivable … Read more
In entry-exit gas markets as they are currently implemented in Europe, network constraints do not affect market interaction beyond the technical capacities determined by the TSO that restrict the quantities individual firms can trade at the market. It is an up to now unanswered question to what extent existing network capacity remains unused in an … Read more
In this article, we provide an overview of the current state of the art with respect to solution of mixed integer linear optimization problems (MILPS) in parallel. Sequential algorithms for solving MILPs have improved substantially in the last two decades and commercial MILP solvers are now considered effective off-the-shelf tools for optimization. Although concerted development … Read more
In this paper, we consider symmetric binary programs that contain set packing, partitioning, or covering inequalities. To handle symmetries as well as set packing, partitioning, or covering constraints simultaneously, we introduce constrained symresacks which are the convex hull of all binary points that are lexicographically not smaller than their image w.r.t. a coordinate permutation and … Read more
A regular timetable is a collection of events that repeat themselves every specific time span. This even structure, whenever applied at a whole network, leads to several benefits both for users and the company, although some issues are introduced, especially about dimensioning the service. It is therefore fundamental to properly consider the interaction between the … Read more
In this paper we present a four-level market model that accounts for airport capacity extension, fleet investment, aircraft scheduling, and ticket trade in a liberalized aviation market with independent decision makers. In particular, budget-constrained airports decide on the first level on their optimal runway capacity extension and on a corresponding airport charge. Airports anticipate optimal … Read more
Cutting planes are derived from specific problem structures, such as a single linear constraint from an integer program. This paper introduces cuts that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set $S\cap P$, where $S$ is a closed set, … Read more