Refine
Year of publication
Document Type
- ZIB-Report (19) (remove)
Has Fulltext
- yes (19)
Keywords
- Mixed Integer Programming (19) (remove)
Constraint Programs and Mixed Integer Programs are closely related optimization problems originating from different scientific areas. Today's state-of-the-art algorithms of both fields have several strategies in common, in particular the branch-and-bound process to recursively divide the problem into smaller sub problems. On the other hand, the main techniques to process each sub problem are different, and it was observed that they have complementary strenghts. We propose a programming framework {\sffamily SCIP} that integrates techniques from both fields in order to exploit the strenghts of both, Constraint Programming and Mixed Integer Programming. In contrast to other proposals of recent years to combine both fields, {\sffamily SCIP} does not focus on easy implementation and rapid prototyping, but is tailored towards expert users in need of full, in-depth control and high performance.
Mixed integer programs ($MIPs$) are commonly solved with branch and bound algorithms based on linear programming. The success and the speed of the algorithm strongly depends on the strategy used to select the branching variables. Today's state-of-the-art strategy is called \emph{pseudocost branching} and uses information of previous branchings to determine the current branching. We propose a modification of \emph{pseudocost branching} which we call \emph{history branching}. This strategy has been implemented in $SIP$, a state-of-the-art $MIP$ solver. We give computational results that show the superiority of the new strategy.
MIPLIB 2003
(2005)
This paper reports on the fourth version of the Mixed Integer Programming Library. Since ({\sc miplib}) is to provide a concise set of challenging problems, it became necessary to purge instances that became too easy. We present an overview of the 27 new problems and statistical data for all 60 instances.
Network Spot Checking Games: Theory and Application to Toll Enforcing in Transportation Networks
(2014)
We introduce the class of spot-checking games (SC games). These games model
problems where the goal is to distribute fare inspectors over a toll network.
In an SC game, the pure strategies of network users correspond to
paths in a graph, and the pure strategies of the inspectors
are subset of edges to be controlled.
Although SC games are not zero-sum, we show that a Nash equilibrium
can be computed by linear programming.
The computation of a strong Stackelberg equilibrium is
more relevant for this problem, but we show that this is NP-hard.
However, we give some bounds on the \emph{price of spite},
which measures how the
payoff of the inspector
degrades when committing to a Nash equilibrium.
Finally, we demonstrate the quality of these bounds for a real-world application,
namely the enforcement of a truck toll on German motorways.
We present a game-theoretic approach to optimize the strategies of toll enforcement
on a motorway network. In contrast to previous approaches,
we consider a network with an arbitrary
topology, and we handle the fact that
users may choose their Origin-Destination path; in particular they may take a detour to
avoid sections with a high control rate. We show that a Nash equilibrium can be
computed with an LP (although the game is not zero-sum), and we give a MIP for the computation
of a Stackelberg equilibrium. Experimental results based on an application to the
enforcement of a truck toll on German motorways are presented.
We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.
This study examines the usability of a real-world, large-scale natural gas transport infrastructure for hydrogen transport. We investigate whether a converted network can transport the amounts of hydrogen necessary to satisfy current energy demands. After introducing an optimization model for the robust transient control of hydrogen networks, we conduct computational experiments based on real-world demand scenarios. Using a representative network, we demonstrate that replacing each turbo compressor unit by four parallel hydrogen compressors, each of them comprising multiple serial compression stages, and imposing stricter rules regarding the balancing of in- and outflow suffices to realize transport in a majority of scenarios. However, due to the reduced linepack there is an increased need for technical and non-technical measures leading to a more dynamic network control. Furthermore, the amount of energy needed for compression increases by 364% on average.
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.
In this article, strategical infrastructure planning problems in the design of large-scale telecommunication networks are discussed based on experiences from three projects with industrial partners: The access network planning of the German Gigabit-Wissenschaftsnetz (G-WiN) for DFN (Verein zur Förderung eines Deutschen Forschungsnetzes e.V.), the mobile network switching center location planning project for E-Plus Mobilfunk, and the fixed network switching center location planning project for TELEKOM AUSTRIA. We introduce a mathematical model for a hierarchical multi-commodity capacitated facility location problem, present adaptions of this basic model to the specific requirements within the different projects and discuss the individual peculiarities and model decisions made. Eventually, we present and discuss computational results of three associated case studies, illustrating '"how we did the job`` with mathematical methods.
We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases. On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. These produce better dual bounds for the smallest and largest instance of the benchmarking library PESPlib.