Events

Joint work with Marco Lübbecke:

In our talk, we propose an exact algorithm for the cut packing problem in general graphs via a column generation approach. For our approach, we discuss both combinatorial algorithms and a mixed-integer linear programming (MIP) formulation for solving the pricing problems. In order to further improve the dual bound, cutting planes from the literature are separated during the solution process. Together with the presentation of the theory, we also highlight the implementation issues and concepts used in SCIP 3.0. Finally, we present our current computational findings.

Today's MIP solvers, including SCIP, are equipped with a number of primal heuristics -- algorithms that try to construct good feasible solutions, thus potentially helping accelerate the solution process.

We will present several heuristics implemented in our generic branch-and-price solver GCG which is based on SCIP. It performs a Dantzig-Wolfe decomposition on any given MIP and solves it with branch-and-price, thus being able to exploit an underlying problem structure. Hence, it is well suited for problems which are known to have a structure, such as bin packing, cutting stock or the generalized assignment problem.

The heuristics presented here are consequently specially tailored for the branch-and-price scenario but still generic in that they are not restricted to one particular problem. We will discuss their performance in GCG as well as implementational details.

We present a SCIP-plug-in for solving general mixed-integer semidefinite programmes. We use an interior-point algorithm for solving the SDP-relaxations in every node and the branching framework of SCIP. Additionally we implemented an approximation scheme using cuts generated with the eigenvectors of the current node solution. Both can be used for general SDPs, no structure of special problems like max-cut is used. Combining both methods produces promising results. As examples we solve problems arising from Truss Topology Design with discrete bar areas and some max-cut instances. This is joint work with Jakob Schelbert and Lars Schew (FAU Erlangen-Nürnberg).

Deciding how to branch is one of the most important decisions any branch-and-bound based MIP solver has to take. In this talk, we discuss the so-called “hybrid branching” scheme, which combines the well-known concepts of strong-branching and pseudo-costs with more general criteria like conflicts and inferences originating from the SAT and CP context. Regarding a current example, we discuss drawbacks of current methods and present recent experiments concerning an extended strong branching.

Optimization-based Bound Tightening (OBBT) is a simple, yet computationally expensive procedure to reduce variable domains of mixed-integer nonlinear programs (MINLPs) by minimizing and maximizing each variable over a convex relaxation. We present techniques to reduce the computational effort incurred by OBBT and exploit dual information to construct globally valid inequalities (Lagrangian Variable Bounds). Propagating these yields a computationally cheap approximation of OBBT that helps to reduce the running time and number of nodes of a subsequent branch-and-bound solution process. We will outline how the present techniques are implemented in SCIP 3.0. This is joint work with Timo Berthold (Zuse Institute Berlin).

Joint work with Gerald Gamrath, Thorsten Koch, Alexander Martin, Matthias Miltenberger:

Preprocessing aims at eliminating redundant information from the problem formulation and simultaneously tries to strengthen the formulation by logical implications. Preprocessing can be very effective and often it might not be possible to solve certain problems without preprocessing. This is especially true for as MIPs formulated supply chain management (SCM) problems. We show two preprocessing algorithms which can be profitably used for solving SCM MIPs. The implementations of the preprocessing algorithms are done as presolver plugins within the non-commercial solver SCIP.

During the past years several methods to handle symmetries in integer programs have been introduced. This includes isomorphism pruning by Margot, orbital branching by Ostrowski et al., symmetry breaking constraints by Liberti, etc. In this talk we present a computational comparison of these different approaches in the framework SCIP. Of course, we also discuss implementation issues.