Marc E. Pfetsch The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic … Read more
The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances … Read more
The handling of symmetries in mixed integer programs in order to speed up the solution process of branch-and-cut solvers has recently received significant attention, both in theory and practice. This paper compares different methods for handling symmetries using a common implementation framework. We start by investigating the computation of symmetries and analyze the symmetries present … Read more
Augmentation methods for mixed-integer (linear) programs are a class of primal solution approaches in which a current iterate is augmented to a better solution or proved optimal. It is well known that the performance of these methods, i.e., number of iterations needed, can theoretically be improved by scaling methods. We extend these results by an … Read more
SOS1 constraints require that at most one of a given set of variables is nonzero. In this article, we investigate a branch-and-cut algorithm to solve linear programs with SOS1 constraints. We focus on the case in which the SOS1 constraints overlap. The corresponding conflict graph can algorithmically be exploited, for instance, for improved branching rules, … Read more
For an infeasible network flow system with supplies and demands, we consider the problem of finding a minimum irreducible infeasible subsystem cover, i.e., a smallest set of constraints that must be dropped to obtain a feasible system. The special cases of covers which only contain flow balance constraints (node cover) or only flow bounds (arc … Read more
Given a weighted undirected graph~$G$ and a nonnegative integer~$k$, the maximum~$k$-star colorable subgraph problem consists of finding an induced subgraph of~$G$ which has maximum weight and can be star colored with at most~$k$ colors; a star coloring does not color adjacent nodes with the same color and avoids coloring any 4-path with exactly two colors. … Read more
Infeasible network flow problems with supplies and demands can be characterized via violated cut-inequalities of the classical Gale-Hoffman theorem. Written as a linear program, irreducible infeasible subsystems (IISs) provide a different means of infeasibility characterization. In this article, we answer a question left open in the literature, by showing a one-to-one correspondence between IISs and … Read more
In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements … Read more
The problem of finding a minimum l^1-norm solution to an underdetermined linear system is an important problem in compressed sensing, where it is also known as basis pursuit. We propose a heuristic optimality check as a general tool for l^1-minimization, which often allows for early termination by “guessing” a primal-dual optimal pair based on an … Read more