Refine
Document Type
- ZIB-Report (15)
Language
- English (15)
Has Fulltext
- yes (15) (remove)
Keywords
- Column generation (2)
- linear programming (2)
- mixed-integer semidefinite programming (2)
- parallelization (2)
- Branch-and-cut (1)
- Branch-and-price (1)
- Constraint integer programming (1)
- Iterative algorithm (1)
- LP solver (1)
- Linear programming (1)
- MINLP solver (1)
- MIP solver (1)
- Mixed-integer linear programming (1)
- Mixed-integer nonlinear programming (1)
- Mixed-integer semidefinite programming (1)
- Optimization solver (1)
- Parallelization (1)
- SCIP, Mathematical optimization, Python, Modeling (1)
- SCIP-Jack (1)
- Steiner tree optimization (1)
- Steiner tree problem (1)
- Steiner tree problems (1)
- Steiner tree solver (1)
- Steiner tree variants (1)
- Tail assignment (1)
- branch-and-cut (1)
- branch-and-price (1)
- branch-cut-and-price framework (1)
- column generation framework (1)
- constraint integer programming (1)
- domain propagation (1)
- generic column generation (1)
- maximum-weight connected subgraph (1)
- maximum-weight connected subgraph problem (1)
- mixed integer programming (1)
- mixed-integer linear and nonlinear programming (1)
- mixed-integer linear programming (1)
- mixed-integer nonlinear programming (1)
- modeling (1)
- multi-criteria optimization (1)
- optimization solver (1)
- parallel branch-and-bound (1)
- portfolio solvers (1)
- prize-collecting Steiner tree (1)
- prize-collecting Steiner tree problem (1)
- reduction techniques (1)
- simplex method (1)
The tail assignment problem is a critical part of the airline planning process that assigns specific aircraft to sequences of flights, called lines-of-flight, to be operated the next day. The aim of this paper is to develop an operationally flexible tail assignment that satisfies short-range---within the next three days---aircraft maintenance requirements and performs the aircraft/flight gate assignment for each input line-of-flight. While maintenance plans commonly span multiple days, the related tail assignment problems can be overly complex and provide little recourse in the event of schedule perturbations. The presented approach addresses operational uncertainty by extending the one-day routes aircraft maintenance routing approach to satisfy maintenance requirements explicitly for the current day and implicitly for the subsequent two days. A mathematical model is presented that integrates the gate assignment and maintenance planning problems. To increase the satisfaction of maintenance requirements, an iterative algorithm is developed that modifies the fixed lines-of-flight provided as input to the tail assignment problem. The tail assignment problem and iterative algorithm are demonstrated to effectively satisfy maintenance requirements within appropriate run times using input data collected from three different airlines.
The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving multi-objective problems, and SCIP-SDP for solving mixed-integer semidefinite programs. The SCIP Optimization Suite has been continuously developed and has now reached version 4.0. The goal of this report is to present the recent changes to the collection. We not only describe the theoretical basis, but focus on implementation aspects and their computational consequences.
SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP.
Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most previous work has been focused on classical sequential algorithms. Since parallel computation has become increasingly mainstream, it is necessary to re-examine and modernize these practices. In this paper, we propose a framework for assessment based on the notion that resource consumption is at the heart of what we generally refer to as the “effectiveness” of an implementation. The proposed framework carefully distinguishes between an implementation’s baseline efficiency, the efficacy with which it utilizes a fixed allocation of resources, and its scalability, a measure of how the efficiency changes as resources (typically additional computing cores) are added or removed. Efficiency is typically applied to sequential implementations, whereas scalability is applied to parallel implementations. Efficiency and scalability are both important contributors in determining the overall effectiveness of a given parallel implementation, but the goal of improved efficiency is often at odds with the goal of improved scalability. Within the proposed framework, we review the challenges to effective evaluation and discuss the strengths and weaknesses of existing methods of assessment.
The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem.
By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack.