90C90 Applications of mathematical programming
Refine
Year of publication
Document Type
- ZIB-Report (39)
- Doctoral Thesis (5)
- Master's Thesis (3)
Is part of the Bibliography
- no (47)
Keywords
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a new cut generator and two new cut selection schemes, a new branching rule, a new LP interface, and several bug fixes. The SCIP Optimization Suite 9.0 also features new Rust and C++ interfaces for SCIP, new Python interface for SoPlex, along with enhancements to existing interfaces. The SCIP Optimization Suite 9.0 also includes new and improved features in the LP solver SoPlex, the presolving library PaPILO, the parallel framework UG, the decomposition framework GCG, and the SCIP extension SCIP-SDP. These additions and enhancements have resulted in an overall performance improvement of SCIP in terms of solving time, number of nodes in the branch-and-bound tree, as well as the reliability of the solver.
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 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in SCIP-Jack.
In 2005 the European Union liberalized the gas market with a disruptive change and decoupled trading of natural gas from its transport. The gas is now transported by independent so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer the maximum possible capacities at each entry and exit such that any resulting gas flow can be realized by the network. The revenue from selling these capacities more than one billion Euro in Germany alone, but overestimating the capacity might compromise the security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs.
This is a report on a large project in mathematical optimization, set out to develop a new toolset for evaluating gas network capacities. The goals and the challenges as they occurred in the project are described, as well as the developments and design decisions taken to meet the requirements.
Exploiting structure in non-convex quadratic optimization and gas network planning under uncertainty
(2017)
The amazing success of computational mathematical optimization over
the last decades has been driven more by insights into mathematical
structures than by the advance of computing technology. In this vein,
we address applications, where nonconvexity in the model and
uncertainty in the data pose principal difficulties.
The first part of the thesis deals with non-convex quadratic programs.
Branch&Bound methods for this problem class depend on tight
relaxations. We contribute in several ways: First, we establish a new
way to handle missing linearization variables in the well-known
Reformulation-Linearization-Technique (RLT). This is implemented
into the commercial software CPLEX. Second, we study the optimization
of a quadratic objective over the standard simplex or a knapsack
constraint. These basic structures appear as part of many complex
models. Exploiting connections to the maximum clique problem and RLT,
we derive new valid inequalities. Using exact and heuristic separation
methods, we demonstrate the impact of the new inequalities on the
relaxation and the global optimization of these problems. Third, we
strengthen the state-of-the-art relaxation for the pooling problem, a
well-known non-convex quadratic problem, which is, for example,
relevant in the petrochemical industry. We propose a novel relaxation
that captures the essential non-convex structure of the problem but is
small enough for an in-depth study. We provide a complete inner
description in terms of the extreme points as well as an outer
description in terms of inequalities defining its convex hull (which
is not a polyhedron). We show that the resulting valid convex
inequalities significantly strengthen the standard relaxation of the
pooling problem.
The second part of this thesis focuses on a common challenge in real
world applications, namely, the uncertainty entailed in the input
data.
We study the extension of a gas transport network, e.g., from our
project partner Open Grid Europe GmbH.
For a single scenario this maps to a challenging non-convex MINLP.
As the future transport patterns are highly uncertain, we propose a
robust model to best prepare the network operator for an array of
scenarios.
We develop a custom decomposition approach that makes use of the
hierarchical structure of network extensions and the loose coupling
between the scenarios.
The algorithm used the single-scenario problem as black-box subproblem
allowing the generalization of our approach to problems with the same
structure.
The scenario-expanded version of this problem is out of reach for
today's general-purpose MINLP solvers.
Yet our approach provides primal and dual bounds for instances with up
to 256 scenarios and solves many of them to optimality.
Extensive computational studies show the impact of our work.
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 branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers.
This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs.
Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem.
The recently imposed new gas market liberalization rules in Germany lead to a change of business of gas network operators.
While previously network operator and gas vendor where united, they were forced to split up into independent companies.
The network has to be open to any other gas trader at the same conditions, and free network capacities have to be identified and publicly offered in a non-discriminatory way.
We show that these new paradigms lead to new and challenging mathematical optimization problems.
In order to solve them and to provide meaningful results for practice, all aspects of the underlying problems, such as combinatorics, stochasticity, uncertainty, and nonlinearity, have to be addressed.
With such special-tailored solvers, free network capacities and topological network extensions can, for instance, be determined.
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 such that there exists a network state meeting all physical, technical, and legal constraints.
We describe a two-stage approach to solve the resulting complex and numerically difficult mixed-integer non-convex nonlinear feasibility problem. The first phase consists of four distinct algorithms facilitating mixed-integer linear, mixed-integer nonlinear, reduced nonlinear, and complementarity constrained methods to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances whose size is significantly larger than networks that have appeared in the literature previously.
This paper is concerned with optimal operation of pressurized water supply networks at a fixed point in time. We use a mixed-integer nonlinear programming (MINLP) model incorporating both the nonlinear physical laws and the discrete decisions such as switching pumps on and off. We demonstrate that for instances from our industry partner, these stationary models can be solved to ε-global optimality within small running times using problem-specific presolving and state-of-the-art MINLP algorithms.
In our modeling, we emphasize the importance of distinguishing between what we call real and imaginary flow, i.e., taking into account that the law of Darcy-Weisbach correlates pressure difference and flow along a pipe if and only if water is available at the high pressure end of a pipe. Our modeling solution extends to the dynamic operative planning problem.
The Steiner tree packing problem (STPP) in graphs is a long studied
problem in combinatorial optimization. In contrast to many other problems,
where there have been tremendous advances in practical problem
solving, STPP remains very difficult. Most heuristics schemes are ineffective
and even finding feasible solutions is already NP-hard. What makes
this problem special is that in order to reach the overall optimal solution
non-optimal solutions to the underlying NP-hard Steiner tree problems
must be used. Any non-global approach to the STPP is likely to fail.
Integer programming is currently the best approach for computing optimal
solutions. In this paper we review some “classical” STPP instances
which model the underlying real world application only in a reduced form.
Through improved modelling, including some new cutting planes, and by
emplyoing recent advances in solver technology we are for the first time
able to solve those instances in the original 3D grid graphs to optimimality.
The steel mill slab design problem from the CSPLIB is a combinatorial
optimization problem motivated by an application of the steel industry. It
has been widely studied in the constraint programming community. Several
methods were proposed to solve this problem. A steel mill slab library was
created which contains 380 instances. A closely related binpacking problem
called the multiple knapsack problem with color constraints, originated
from the same industrial problem, was discussed in the integer programming
community. In particular, a simple integer program for this problem has
been given by Forrest et al. The aim of this paper is to bring these
different studies together. Moreover, we adapt the model of Forrest et
al. for the steel mill slab design problem. Using this model and a
state-of-the-art integer program solver all instances of the steel mill
slab library can be solved efficiently to optimality. We improved,
thereby, the solution values of 76 instances compared to previous results.
Finally, we consider a recently introduced variant of the steel mill slab
design problem, where within all solutions which minimize the leftover one
is interested in a solution which requires a minimum number of slabs. For
that variant we introduce two approaches and solve all instances of the
steel mill slab library with this slightly changed objective function to
optimality.
MIPLIB 2010
(2010)
This paper reports on the fifth version of the Mixed Integer Programming Library.
The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups.
This includes the main benchmark test set of 87 instances, which
are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved.
For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to
test the accuracy of provided solutions using exact arithmetic.
Mobile communication is nowadays taken for granted. Having started
primarily as a service for speech communication, data service and
mobile Internet access are now driving the evolution of network
infrastructure. Operators are facing the challenge to match the
demand by continuously expanding and upgrading the network
infrastructure. However, the evolution of the customer's demand is uncertain.
We introduce a novel (long-term) network planning approach based on
multistage stochastic programming, where demand evolution is considered as
a stochastic process and the network is extended as to maximize the
expected profit. The approach proves capable of designing large-scale
realistic UMTS networks with a time-horizon of several years. Our
mathematical optimization model, the solution approach, and computational
results are presented in this paper.
Application of Multistage Stochastic Programming in Strategic Telecommunication Network Planning
(2010)
Telecommunication is fundamental for the information society. In both, the
private and the professional sector, mobile communication is nowadays taken
for granted. Starting primarily as a service for speech communication, data
service and mobile Internet access are now driving the evolution of network
infrastructure. In the year 2009, 19 million users generated over 33
million GB of traffic using mobile data services. The 3rd generation
networks (3G or UMTS) in Germany comprises over 39,000 base stations with
some 120,000 cells. From 1998 to 2008, the four network operators in
Germany invested over 33 billion Euros in their infrastructure. A careful
allocation of the resources is thus crucial for the profitability for a
network operator: a network should be dimensioned to match customers
demand. As this demand evolves over time, the infrastructure has to evolve
accordingly. The demand evolution is hard to predict and thus constitutes a
strong source of uncertainty. Strategic network planning has to take this
uncertainty into account, and the planned network evolution should adapt to
changing market conditions. The application of superior planning methods
under the consideration of uncertainty can improve the profitability of the
network and creates a competitive advantage. Multistage stochastic
programming is a suitable framework to model strategic telecommunication
network planning.
We present mathematical models and effective optimization procedures for
strategic cellular network design. The demand evolution is modeled as a
continuous stochastic process which is approximated by a discrete scenario
tree. A tree-stage approach is used for the construction of non-uniform
scenario trees that serve as input of the stochastic program. The model is
calibrated by historical traffic observations. A realistic system model of
UMTS radio cells is used that determines coverage areas and cell capacities
and takes signal propagation and interferences into account. The network
design problem is formulated as a multistage stochastic mixed integer
linear program, which is solved using state-of-the-art commercial MIP
solvers. Problem specific presolving is proposed to reduce the problem
size. Computational results on realistic data is presented. Optimization
for the expected profit and the conditional value at risk are performed and
compared.
Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust
programs with arbitrary recourse. We apply them to robust network design with polyhedral demand
uncertainty, introducing the affine routing principle.
We compare the affine routing to the well-studied static and dynamic routing schemes for robust
network design.
All three schemes are embedded into the general framework of two-stage network design with recourse.
It is shown that affine routing can be seen as a generalization of the widely used static
routing still being tractable and providing cheaper solutions. We investigate properties on the
demand polytope under which affine routings reduce to static routings and also develop conditions on
the uncertainty set leading to dynamic routings being affine. We show however that affine routings
suffer from the drawback that (even totally) dominated demand vectors are not necessarily supported
by affine solutions. Uncertainty sets have to be designed accordingly. Finally, we present
computational results on networks from SNDlib. We conclude that for these instances the
optimal solutions based on affine routings tend to be as cheap as optimal network designs for
dynamic routings. In this respect the affine routing principle can be used to approximate the cost
for two-stage solutions with free recourse which are hard to compute.
In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.
Since the initial application of mathematical optimisation methods to mine planning in 1965, the Lerchs-Grossmann algorithm for computing the ultimate pit limit, operations researchers have worked on a variety of challenging problems in the area of open pit mining. This thesis focuses on the open pit mining production scheduling problem: Given the discretisation of an orebody as a block model, determine the sequence in which the blocks should be removed from the pit, over the lifespan of the mine, such that the net present value of the mining operation is maximised. In practise, when some material has been removed from the pit, it must be processed further in order to extract the valuable elements contained therein. If the concentration of valuable elements is not sufficiently high, the material is discarded as waste or stockpiled. Realistically-sized block models can contain hundreds of thousands of blocks. A common approach to render these problem instances computationally tractable is the aggregation of blocks to larger scheduling units. The thrust of this thesis is the investigation of a new mixed-integer programming formulation for the open pit mining production scheduling problem, which allows for processing decisions to be made at block level, while the actual mining schedule is still computed at aggregate level. A drawback of this model in its full form is the large number of additional variables needed to model the processing decisions. One main result of this thesis shows how these processing variables can be aggregated efficiently to reduce the problem size significantly, while practically incurring no loss in net present value. The second focus is on the application of lagrangean relaxation to the resource constraints. Using a result of Möhring et al. (2003) for project scheduling, the lagrangean relaxation can be solved efficiently via minimum cut computations in a weighted digraph. Experiments with a bundle algorithm implementation by Helmberg showed how the lagrangean dual can be solved within a small fraction of the time required by standard linear programming algorithms, while yielding practically the same dual bound. Finally, several problem-specific heuristics are presented together with computational results: two greedy sub-MIP start heuristics and a large neighbourhood search heuristic. A combination of a lagrangean-based start heuristic followed by a large neighbourhood search proved to be effective in generating solutions with objective values within a 0.05% gap of the optimum.
The steel mill slab design problem from the CSPLib is a binpacking problem that is motivated by an application of the steel industry and that has been widely studied in the constraint programming community. Recently, several people proposed new models and methods to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called multiple knapsack problem with color constraints, originated from the same industrial problem, were discussed in the integer programming community. In particular, a simple integer programming for this problem has been given by Forrest et al. [3]. The aim of this paper is to bring these different studies together. Moreover, we adopt the model of [3] for the steel mill slab problem. Using a state of the art integer program solver, this model is capable to solve all instances of the steel mill slab library, mostly in less than one second, to optimality. We improved, thereby, the solution value of 76 instances.
This extended abstract is about algorithms for controlling elevator systems employing destination hall calls, i.e. the passenger provides his destination floor when calling an elevator. We present the first exact algorithm for controlling a group of elevators and report on simulation results indicating that destination hall call systems outperform conventional systems.
Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem, which arises in the operational planning of such networks. Given a capacitated directed graph and a set of communication demands, the goal is to find routing lengths that define a unique shortest path for each demand and minimize the maximum congestion over all links in the resulting routing. We illustrate the general decomposition approach our algorithm is based on, present the integer and linear programming models used to solve the master and the client problem, and discuss the most important implementational aspects. Finally, we report computational results for various benchmark problems, which demonstrate the efficiency of our algorithm.