Refine
Document Type
- ZIB-Report (4)
Language
- English (4)
Has Fulltext
- yes (4)
Is part of the Bibliography
- no (4)
Keywords
- integer programming (4) (remove)
Institute
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.
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.
We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, the crews of the tours have to be scheduled. Thus, we developed a personalized crew rostering model. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The paper focuses first on different requirements for the rostering and how they can be modeled in detail. The second focus is on a bicriterion analysis of the planning problem to find the balance between the control quality and the roster acceptance. On the one hand the tour planning is a profit maximization problem and on the other hand the rostering should be made in a employee friendly way. Finally, computational results on real-world instances show the practicability of our method.
Sports rankings are obtained by applying a system of rules to evaluate the
performance of the participants in a competition.
We consider rankings that result from assigning an ordinal rank to each
competitor according to their performance.
We develop an integer programming model for rankings that allows us
to calculate the number of points needed to guarantee
a team the ith position, as well as the minimum number of points
that could yield the ith place.
The model is very general and can thus be applied to many types of sports.
We discuss examples coming from football (soccer), ice hockey, and
Formula~1. We answer various questions and debunk a few myths along the way.
Are 40 points enough to avoid relegation in the Bundesliga?
Do 95 points guarantee the participation of a team in the NHL playoffs?
Moreover, in the season restructuration currently under consideration in the NHL,
will it be easier or harder to access the playoffs?
Is it possible to win the Formula~1 World Championship without winning at least one race
or without even climbing once on the podium?
Finally, we observe that the optimal solutions of the aforementioned model
are associated to extreme situations which are unlikely to happen. Thus,
to get closer to realistic scenarios, we enhance the model by adding some
constraints inferred from the results of the previous years.