On a Polynomially Solvable Subclass of the Clique Problem with Applications in Energy-Efficient Timetabling - Gemander, Patrick (Operations Research Proceedings 2018, 2019)
The clique problem under multiple-choice constraints is an NP-hard variant of the general clique problem, which incorporates a structure commonly found in real-world applications like underground, railway or runway scheduling. It is relevant whenever there is a set of decisions with discrete options for each decision and possible conflicts between options. In this article, we identify a polynomial-time solvable subclass and determine its complete convex hull using graph-theoretic arguments related to perfect graphs. Since the convex hull can have exponentially many facets, we present criteria on how to more efficiently find the stable sets required to describe the convex hull as well as a polynomial-time separation algorithm. Finally, the theoretical results were successfully applied to energy-efficient underground and railway scheduling.

The SCIP Optimization Suite 5.0 - Gleixner, Ambros; Eifler, Leon; Gally, Tristan; Gamrath, Gerald; Gemander, Patrick; Gottwald, Robert Lion; Hendel, Gregor; Hojny, Christopher; Koch, Thorsten; Miltenberger, Matthias; Müller, Benjamin; Pfetsch, Marc E.; et al. (2017)
This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On mixed-integer linear programs, SCIP 5 is about 41% faster than SCIP 4 and over twice as fast on instances that take at least 100 seconds to solve. For mixed-integer nonlinear programs, SCIP 5 is about 17% faster overall and 23% faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the linear programming solver SoPlex, the Steiner tree solver SCIP-Jack, the mixed-integer semidefinite programming solver SCIP-SDP, and the parallelization framework UG.<br
Keywords: Constraint integer programming; linear programming; mixed-integer linear programming; mixed-integer nonlinear programming; optimization solver; branch-and-cut; branch-and-price; column generation framework; parallelization; mixed-integer semidefinite programming; Steiner tree optimization

The SCIP Optimization Suite 7.0 - Gamrath, Gerald; Anderson, Daniel; Bestuzheva, Ksenia; Chen, Wei-Kun; Eifler, Leon; Gasse, Maxime; Gemander, Patrick; Gleixner, Ambros; Gottwald, Leona; Halbig, Katrin; Hendel, Gregor; Hojny, Christopher; et al. (2020)
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear optimization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides improvements in the Benders’ decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders’ decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SD

Two-row and two-column mixed-integer presolve using hash-based pairing methods - Chen, Weikun; Gemander, Patrick; Gleixner, Ambros; Gottwald, Leona; Martin, Alexander; Weninger, Dieter (2019)
In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolving techniques successfully is their speed. Hence, most methods inspect constraints or variables individually in order to guarantee linear complexity. In this paper, we present new hashing-based pairing mechanisms that help to overcome known performance limitations of more powerful presolving techniques that consider pairs of rows or columns. Additionally, we develop an enhancement to one of these presolving techniques by exploiting the presence of set-packing structures on binary variables in order to strengthen the resulting reductions without increasing runtime. We analyze the impact of these methods on the MIPLIB 2017 benchmark set based on an implementation in the MIP solver SCIP.
Keywords: Linear programming; Mixed-integer linear programming; Optimization solver; Presolve

Two-row and two-column mixed-integer presolve using hashing-based pairing methods - Gemander, Patrick; Chen, Wei Kun; Weninger, Dieter; Gottwald, Leona; Gleixner, Ambros; Martin, Alexander (EURO Journal on Computational Optimization, 2020)
In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolve techniques successfully is their speed. Hence, most methods inspect constraints or variables individually in order to guarantee linear complexity. In this paper, we present new hashing-based pairing mechanisms that help to overcome known performance limitations of more powerful presolve techniques that consider pairs of rows or columns. Additionally, we develop an enhancement to one of these presolve techniques by exploiting the presence of set-packing structures on binary variables in order to strengthen the resulting reductions without increasing runtime. We analyze the impact of these methods on the MIPLIB 2017 benchmark set based on an implementation in the MIP solver SCIP.
CRIS-Team Scopus Importer:2020-08-28
Keywords: Linear programming; Mixed-integer linear programming; Optimization solver; Presolve