ZIB-Report
Refine
Year of publication
Document Type
- ZIB-Report (425)
- Habilitation (4)
Keywords
- mixed integer programming (25)
- integer programming (21)
- constraint integer programming (13)
- branch-and-bound (11)
- mixed-integer programming (11)
- Mixed Integer Programming (9)
- Optimierung (9)
- MINLP (8)
- combinatorial optimization (8)
- line planning (8)
Institute
- Mathematical Optimization (429) (remove)
13-22
制約整数計画ソルバ SCIP の並列化
(2013)
制約整数計画(CIP: Constraint Integer Programming)は,制約プログラミング(CP: Constraint Programming),混合整数計画(MIP: Mixed Integer Programming), 充足可能性問題(SAT: Satisfiability Problems)の研究分野におけるモデリング技術と解法を統合している.その結果,制約整数計画は,広いクラスの最適化問題を扱うことができる.SCIP (Solving Constraint Integer Programs)は,CIPを解くソルバとして実装され,Zuse Institute Berlin (ZIB)の研究者を中心として継続的に拡張が続けられている.本論文では,著者らによって開発されたSCIP に対する2種類の並列化拡張を紹介する. 一つは,複数計算ノード間で大規模に並列動作するParaSCIP である. もう一つは,複数コアと共有メモリを持つ1台の計算機上で(スレッド)並列で動作するFiberSCIP である. ParaSCIP は,HLRN IIスーパーコンピュータ上で, 一つのインスタンスを解くために最大7,168 コアを利用した動作実績がある.また,統計数理研究所のFujitsu PRIMERGY RX200S5上でも,最大512コアを利用した動作実績がある.統計数理研究所のFujitsu PRIMERGY RX200S5上 では,これまでに最適解が得られていなかったMIPLIB2010のインスタンスであるdg012142に最適解を与えた.
11-43
The paper deals with the workload and busy period for the M/GI/1
system under FCFS discipline, where the customers may become
impatient during their waiting for service with generally
distributed maximal waiting times and also during their service
with generally distributed maximal service times depending
on the time waited for service. This general impatience mechanism,
originally introduced by Kovalenko (1961) and considered
by Daley (1965), too, covers the special cases of impatience
on waiting times as well as impatience on sojourn times,
for which Boxma et al. (2010), (2011) gave new results
and outlined special cases recently. Our unified approach
bases on the vector process of workload and busy time.
Explicit representations for the LSTs of workload and
busy period are given in case of phase-type distributed
impatience.
07-29
The timetable is the essence of the service offered by any provider of public transport'' (Jonathan Tyler, CASPT 2006). Indeed, the timetable has a major impact on both operating costs and on passenger comfort. Most European agglomerations and railways use periodic timetables in which operation repeats in regular intervals. In contrast, many North and South American municipalities use trip timetables in which the vehicle trips are scheduled individually subject to frequency constraints. We compare these two strategies with respect to vehicle operation costs. It turns out that for short time horizons, periodic timetabling can be suboptimal; for sufficiently long time horizons, however, periodic timetabling can always be done in an optimal way'.
11-40
Given the steady increase in cores per CPU, it is only a matter of time
until supercomputers will have a million or more cores. In this article, we
investigate the opportunities and challenges that will arise when trying to
utilize this vast computing power to solve a single integer linear optimization
problem. We also raise the question of whether best practices in sequential
solution of ILPs will be effective in massively parallel environments.
08-26
Den kürzesten Weg in einem Graphen zu finden ist ein klassisches Problem der Graphentheorie. Über einen Vortrag zu diesem Thema beim Tag der Mathematik 2007 von R. Borndörfer kam ich in Kontakt mit dem Konrad-Zuse-Zentrum (ZIB), das sich u.a. mit Wegeoptimierung beschäftigt. Ein Forschungsschwerpunkt dort ist im Rahmen eines Projekts zur Chipverifikation das Zählen von Lösungen, das, wie wir sehen werden, eng mit dem Zählen von Wegen zusammenhängt. Anhand von zwei Fragen aus der Graphentheorie soll diese Facharbeit unterschiedliche Lösungsmethoden untersuchen. Wie bestimmt man den kürzesten Weg zwischen zwei Knoten in einem Graphen und wie findet man alle möglichen Wege? Nach einer Einführung in die Graphentheorie und einer Konkretisierung der Probleme wird zunächst für beide eine Lösung mit auf Graphen basierenden Algorithmen vorgestellt. Während der Algorithmus von Dijkstra sehr bekannt ist, habe ich für das Zählen von Wegen einen eigenen Algorithmus auf der Basis der Tiefensuche entwickelt. Im zweiten Teil der Arbeit wird das Konzept der ganzzahligen Programmierung vorgestellt und die Lösungsmöglichkeiten für Wegeprobleme, die sich darüber ergeben. Schließlich wurden die vorgestellten Algorithmen am Beispiel des S- und U-Bahnnetzes von Berlin implementiert und mit Programmen, die die gleichen Fragen über ganzzahlige Programmierung lösen, verglichen.
19-38
In this paper we introduce a technique to produce tighter cutting planes for mixed-integer non-linear programs. Usually, a cutting plane is generated to cut off a specific infeasible point. The underlying idea is to use the infeasible point to restrict the feasible region in order to obtain a tighter domain. To ensure validity, we require that every valid cut separating the infeasible point from the restricted feasible region is still valid for the original feasible region. We translate this requirement in terms of the separation problem and the reverse polar. In particular, if the reverse polar of the restricted feasible region is the same as the reverse polar of the feasible region, then any cut valid for the restricted feasible region that \emph{separates} the infeasible point, is valid for the feasible region. We show that the reverse polar of the \emph{visible points} of the feasible region from the infeasible point coincides with the reverse polar of the feasible region. In the special where the feasible region is described by a single non-convex constraint intersected with a convex set we provide a characterization of the visible points. Furthermore, when the non-convex constraint is quadratic the characterization is particularly simple. We also provide an extended formulation for a relaxation of the visible points when the non-convex constraint is a general polynomial. Finally, we give some conditions under which for a given set there is an inclusion-wise smallest set, in some predefined family of sets, whose reverse polars coincide.
08-34
We consider an auction of slots to run trains through a railway network. In contrast to the classical setting for combinatorial auctions, there is not only competition for slots, but slots can mutually exclude each other, such that general conflict constraints on bids arise. This turns the winner determination problem associated with such an auction into a complex combinatorial optimization problem. It also raises a number of auction design questions, in particular, on incentive compatibilty. We propose a single-shot second price auction for railway slots, the Vickrey Track Auction (VTA). We show that this auction is incentive compatible, i.e., rational bidders are always motivated to bid their true valuation, and that it produces efficient allocations, even in the presence of constraints on allocations. These properties are, however, lost when rules on the submission of bids such as, e.g., lowest bids, are imposed. Our results carry over to generalized" Vickrey auctions with combinatorial constraints.
16-58
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixed-integer linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.
12-11
This paper provides a generic formulation for rolling stock planning
problems in the context of intercity passenger traffic. The main contributions
are a graph theoretical model and a Mixed-Integer-Programming
formulation that integrate all main requirements of the considered
Vehicle-Rotation-Planning problem (VRPP). We show that it is
possible to solve this model for real-world instances provided by our
industrial partner DB Fernverkehr AG using modern algorithms and
computers.