SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
Date: 3rd and 4th June 2020
Organizer: Stephen J. Maher
We are happy to announce our upcoming SCIP Online Workshop planned for 3rd and 4th June 2020. It is intended for
The main focus of the workshop is to provide a forum for current and prospective SCIP users to discuss their applications and share their experience with SCIP.
We are excited to have Elina Rönnberg from Linkoping University, Sweden join us on Day 1 to give a plenary talk. Dr Rönnberg has extensive experience with mathematical and computational aspects of mixed integer programming. Dr Rönnberg will discuss the use of general purpose solvers within solution frameworks for large-scale scheduling problems.
Opportunities to discuss various aspect of SCIP will be provide through a number of different activities. Day 1 will present the first Q&A sessions with the SCIP developers. The developers will provide a shorts presentation of their topic areas. The participants will be given the opportunity to ask any SCIP question related to that topic. We encourage the participants to prepare questions before attending. Day 1 will close with a social event, where you can meet and talk with other participants of the workshop. On Day 2 we have 4 exciting talks on applications of SCIP and new developments for the optimization suite.
The workshop will be free of charge and will be held via Video Conference. If you want to attend the workshop, please write to SCIPonlineworkshop2020@exeter.ac.uk by May 29, 2020, and let us know by May 18, 2020 if you would like to give a talk.
The registration deadline has been extended to Monday 1st June.
Feel free to connect with you fellow workshop participants through Twitter and Slack.
Twitter: #SCIPOnlineWorkshop
Slack workspace
| Time | Speaker | Detailed Information | |
|---|---|---|---|
| 14:00 - 14:15 | Stephen Maher (University of Exeter, United Kingdom) |
Welcome
Abstract
| |
| 14:15 - 15:00 | Leon Eifler (Zuse Institute Berlin, Germany) |
SCIP Introduction Talk
SCIP is currently one of the fastest non-commercial solvers for mixed integer linear (MIP) and nonlinear programming (MINLP).
More specifically, SCIP is a plugin-based framework for constraint integer programming (CIP) and branch-cut-and-price that is available in source code and can be fully customized and extended for a wide variety of applications and research purposes.
In this introductory talk, we give an overview of Constraint Integer Programming in general, the SCIP design philosophy, and its various plugin types.
Furthermore, we discuss some of the newest features and improvements that were introduced in the recent release of SCIP 7.0 such as a built-in estimation of the remaining tree-size.
This talk is suitable for people who are new to SCIP as well as anyone who wants to brush up on their SCIP knowledge and learn about recent developments.
| |
| 15 minutes break | |||
| 15:15 - 16:15 | Elina Rönnberg (Linköping University, Sweden) |
Plenary talk: Decomposition approaches for a large-scale scheduling problem
Generic state-of-the-art solvers for discrete optimisation are exceptionally powerful tools that efficiently solve a variety of problems.
However, the scale and complexity of practically relevant problems can sometimes render these solvers incapable of even finding feasible solutions.
In such cases, one possibility is to develop solution approaches that exploit problem structure to decompose the problem and then use the generic solvers for addressing the resulting subproblems.
The success of such approaches relies on that the subproblems can be efficiently solved and that the information gained from that is sufficient to solve the original problem.
In an industry-academia collaboration between Linköping University and Saab Aeronautics, we address the scheduling of a kind of electronic systems in future aircraft.
Briefly, this problem can be described as a rich multiprocessor scheduling problem that also includes the scheduling of a communication network.
To find feasible solutions to practically relevant instances of this problem is challenging.
| |
| 15 minutes break | |||
| 16:30 - 17:30 | Chair: Stephen Maher (University of Exeter, United Kingdom) and Christine Tawfik (Zuse Institute Berlin, Germany) |
Parallel Q&A sessions - Benders Decomposition
This session will discuss the Benders' decomposition framework available within SCIP. We will present the four different methods for using the Benders' decomposition framework, i) through GCG, ii) supply an instance in the SMPS format, iii) using the default Benders' decomposition plugin, and iv) developing custom Benders' decomposition and cut generation plugins. Additionally, the primary methods for using the Benders' decomposition within PySCIPOpt will be discussed.
This session will be suitable for people who use SCIP as a black box solver and those who have had some experience developing custom SCIP solvers.
| |
| 16:30 - 17:30 | Chairs: Marco Lübbecke (RWTH Aachen, Germany) and Benjamin Müller (Cardinal Operations and Zuse Institute Berlin, Germany) |
Parallel Q&A sessions - Branch-and-price
This session will explain how SCIP can be used to solve optimization problems with branch-and-price. We will discuss the interaction of various plugins that are required to take full advantage of SCIP's branch-and-price capabilities. We also show how the GCG (Generic Branch-Cut-and-Price) framework can be used to automatically apply and solve a Dantzig-Wolfe decomposition for a specific optimization problem.
This session is suitable for people who are familiar with the theoretical aspects of branch-and-price and for people who are experienced in extending SCIP with plug-ins.
| |
| 16:30 - 17:30 | Chairs: Ksenia Bestuzheva (Zuse Institute Berlin, Germany) and Stefan Vigerske (GAMS Development Corporation) |
Parallel Q&A sessions - MINLP
This session will discuss the handling of nonlinear constraints within SCIP. We will present the basic methods that are employed by SCIP to solve problems with nonlinear constraints, e.g., NLPs and MINLPs. If there is interest, we can also present some of the on-going development on improving the handling of nonlinearities.
This session will be suitable for people who use SCIP as a black box solver.
|
slides |
| 16:30 - 17:30 | Chair: Felipe Serrano (Zuse Institute Berlin, Germany) and Matthias Miltenberger (Gurobi Optimization) |
Parallel Q&A sessions - PySCIPOpt - The Python Interface for the SCIP Optimization Suite
This session will show how to use SCIP's python interface, PySCIPOpt. We will first see the basic modeling functionality of PySCIPOpt and then discussed how to extend SCIP writing your own plugins in python.
The session should be accessible to anybody with some basic knowledge of modeling and optimization.
| |
| 16:30 - 17:30 | Chair: Yuji Shinano (Zuse Institute Berlin, Germany) and Daniel Rehfeldt (Zuse Institute Berlin, TU Berlin) |
Parallel Q&A sessions - FiberSCIP - Shared memory parallelization framework for SCIP
This session will provide an introduction to FiberSCIP for SCIP users. In this session we will discuss how FiberSCIP works, how to run FiberSCIP and how to parallelize your customized SCIP solver.
This session will be suitable for people who use SCIP as a black box solver and those who have had some experience developing custom SCIP solvers.
|
slides |
| 15 minutes break | |||
| 17:45 - 19:00 |
Social event |
| Time | Speaker | Detailed Information | |
|---|---|---|---|
| 14:00 - 14:30 | Christopher Hojny (Eindhoven University of Technology, Netherlands) |
Mixed-Integer Programming Techniques for the Connected Max-k-Cut Problem
We consider an extended version of the classical Max-k-Cut problem in
which we additionally require that the parts of the graph partition are
connected. For this problem we study two alternative mixed-integer
linear formulations and review existing as well as develop new
branch-and-cut techniques like cuts, branching rules, propagation,
primal heuristics, and symmetry handling. We indicate how these
techniques can be implemented using SCIP and analyze the impact of the
different techniques based on the underlying graphs.
| |
| 14:30 - 15:00 | Edwin Reynolds (Lancaster University, United Kingdom) |
Using SCIP as a branch-and-price framework to solve the Train Timetable Rescheduling Problem
By rerouting and retiming trains in real-time, the propagation of reactionary delay in complex station areas can be reduced. In this study, we propose a new optimisation model and solution algorithm that can be used to determine the best combination of route and schedule changes to make. Whilst several models have been proposed to tackle this problem, existing models either lack sufficient detail, or cannot be solved to optimality within the stringent time limits asociated with a real-time environment. We formulate the problem as a multicommodity flow problem on a time-space graph with a novel representation of the track capacity constraints and a new objective function based on utility maximisation. We present a tailored branch-and-price solution algorithm and test it on a set of new instances based on real data. Our experiments show that most of these instances can be solved to optimality within 20 seconds, and provably near-optimal solutions can be found for the remainder.
| |
| 15 minutes break | |||
| 15:15 - 15:45 | Giulia Zarpellon (Polytechnique Montréal, Canada) |
Parameterizing branch-and-bound search trees to learn branching policies
Learning branching policies for Mixed-Integer Linear Programming problems (MILPs) has become an active research area, with most works proposing to imitate the strong branching rule and specialize it to distinct classes of problems.
We aim instead at learning a policy that generalizes across heterogeneous MILPs: our main hypothesis is that parameterizing the state of the branch-and-bound (B&B) search tree can significantly aid this type of generalization.
We propose a novel imitation learning framework, and introduce new input features and architectures to represent branching.
Experiments with SCIP on MILP benchmark instances clearly show the advantages of incorporating to a baseline model an explicit parameterization of the state of the search tree to modulate the branching decisions.
The resulting policy reaches higher accuracy than the baseline, and on average explores smaller B&B trees, while effectively allowing generalization to generic unseen instances.
| |
| 15:45 - 16:15 | Leona Gottwald (Zuse Institute Berlin, Germany) |
PaPILO - Parallel Presolve for Integer and Linear Optimization
Presolving is an essential part constributing to the performance of SCIP and other modern solvers.
PaPILO, a new C++ library, provides presolving routines for MIP and LP problems.
Many presolving steps for such problems can benefit greatly from having a global view on the constraint matrix.
SCIP, however, is designed around constraint objects which contributes to its ability for handling a much larger class of problems than only MIPs.
PaPILO is optimized for MIP and LP problems and complements SCIP in this regard as part of the newest release of the SCIP optimization suite.
Modern hardware requires parallel algorithms to utilize its full potential, yet even most commercial solvers do not use multi-threading for the preprocessing step as of today. While the presolving itself is designed to be fast despite the lack of parallelization, this can come at the cost of failing to find important reductions due to working limits and heuristic filtering. PaPILO's design facilitates use of parallel hardware to allow for more aggressive presolving and presolving of huge problems. The archtitecture of PaPILO allows presolvers generally to run in parallel without requiring expensive copies of the problem and without special synchronization in the presolvers themselves. Additionally, the use of Intel's TBB library aids PaPILO to efficiently exploit recursive parallelism within expensive presolving routines, such as probing, dominated columns, or constraint sparsification. Despite PaPILO's use of parallelization, its results are guaranteed to be deterministic independently of the number of threads available. This talk will give insights into the important design choices enabling PaPILO's capabilities and details of its parallel algorithms. | |
| 16:15 - 16:30 | Stephen Maher (University of Exeter, United Kingdom) |
Closing
TBA
|
For more information, talks, and abstracts of the last SCIP Workshops, visit the homepage of the SCIP Workshop 2018, SCIP Workshop 2014 or SCIP Workshop 2012.
Programming introductions to SCIP can be found, e.g., in the course material of the 2015 workshop Combinatorial Optimization at Work.