Talks and presentations
We study arc-flow formulations obtained from transition graphs or transition hypergraphs of dynamic programs.
These formulations are known for their generally strong linear relaxations and can be solved directly by a general purpose mixed integer linear programming (MILP) solver.
An advantage of the MILP formulation is that one can include additional linear constraints in the form of resource constraints.
In the absence of these, arc-flow formulations in graphs -- resp. hypergraphs -- form a totally unimodular -- resp. totally dual integral -- system, meaning the solution of the linear relaxation of the formulation is integer.
A drawback of the MILP formulation is its size which can be pseudo-polynomial or exponential.
We focus on cutting and packing problems with temporal constraints, i.e., temporal knapsack problem, temporal bin packing problem and their variants.
We introduce preprocessing techniques and dominance rules to reduce the size of the transition graphs and hypergraphs: symmetries reduction, equivalent states aggregation using methods from the literature and detection of states that can be replaced by other states where some constraints are relaxed.
Numerically, we confirm the strength of the linear relaxation of the arc-flow formulations, we observe that the sizes of the arc-flow formulations are significantly reduced by our techniques and show that these formulations are competitive and can outperform popular compact formulations from the literature.
Due to its length, the abstract is available upon request.
Automated storage and retrieval systems have been studied for years in the context of warehouse
optimization.
The number
of shelves and their height is generally determined in such a way that the number of retrieval operations
per
minute is
maximized, i.e., response time is often more important than the space used by the device. In our specific
study,
we
consider the case where capacity is highly constrained, and the efficiency of the system is not an issue. We
call our
problem the \emph{Automatic Storage Design} (ASD) problem.
In the ASD problem, the goal is to design a set of shelves in a box, design a set of compartments in every
shelf
and
assign items to the compartments, where deciding to assign an item is associated with a profit. The
objective is
to
maximize the total profit. The design parts are defined on a set of packing constraints, i.e., the sum of
the
shelves'
heights must not exceed the box's height and the sum of compartments' widths in every shelf must not exceed
the
box's
width. The assignment part is defined on a set of temporal knapsack constraints, i.e., the items must fit
with
respect
to their height, width, length and time windows. For an item to be a candidate for assignment in a
compartment,
its
height must be less than or equal to the compartment's height and its width must be equal to the
compartment's
width.
The length dimension represents the knapsack constraint, i.e., the sum of items' lengths with respect to
their
time
windows must not exceed the compartment's length. This problem generalizes the temporal knapsack problem,
and
the
three-dimensional three-stage guillotine cutting problem.
We consider several formulations based on integer linear programming (ILP) and dynamic programming. We
present a
compact
ILP formulation serving as a reference point. We formulate the ASD problem as a dynamic program with
additional
constraints and show that it is equivalent to the search for a max-cost flow in an directed acyclic
hypergraph.
From
this representation, we derive an ILP flow-model and a label setting algorithm. In order for our methods to
be
as
competitive as possible, we introduce several preprocessing procedures to reduce the size of the hypergraph.
Extensive numerical studies are performed on a set of 320 randomly generated instances to assess the
efficiency
of our
methods and compare them with each other.
We also evaluate the impact of the design and the temporal knapsack aspect of the problem on the results.
No abstract available.