Invited Session Fri.1.H 3005

Friday, 10:30 - 12:00 h, Room: H 3005

Cluster 2: Combinatorial optimization [...]

Combinatorial optimization in logistics


Chair: Erwin Pesch



Friday, 10:30 - 10:55 h, Room: H 3005, Talk 1

Jens Schulz
Explanation algorithms in cumulative scheduling

Coauthor: Stefan Heinz


In cumulative scheduling, conflict analysis is one of the key ingredients to solve these problems efficiently. Thereby, the computational complexity of explanation algorithms that explain infeasibilities or bound changes plays an important role. Their role is even more substantial when we are faced with a backtracking system where explanations need to be constructed on the fly. In this talk we present complexity results for computing minimum-size explanations for the propagation algorithms time-tabling, edge-finding, and energetic reasoning. We show that it is possible to compute in polynomial time minimum-size explanations for bound changes which result from energetic reasoning and edge-finding. In case of time-tabling, we prove that an important special case is already weakly NP-hard. In the context of bound-widening, the problems all become NP-hard. To this end, we establish a relation to unsplittable flow problems on the path. We evaluate different heuristic approaches and exact approaches to explain bound changes derived by these algorithms. Using these minimum-size explanations pays off in total compared to using faster but weaker explanation algorithms.



Friday, 11:00 - 11:25 h, Room: H 3005, Talk 2

Jenny Nossack
Benders decomposition for a 1-full-truckload pickup-and-delivery vehicle routing problem

Coauthor: Erwin Pesch


We address a pickup and delivery vehicle rounting problem with multiple depots, where routes have to be constructed to satisfy customer requests, which either involve the pickup or delivery of a single commodity. A fleet of homogeneous vehicles is available to fulfill the demand and supply of the customers under the objective to minimize the total distance traveled. Each vehicle has unit capacity and the commodities which are collected from the pickup customers can be used to accommodate the demand of the delivery customers. We model this problem as an integrated integer nonlinear programming problem that simultaneously solves an assignment and a routing problem, linked via coupling constraints. Exact solution approaches based on the classical and the generalized Benders
decomposition are presented to optimally solve the problem.



Friday, 11:30 - 11:55 h, Room: H 3005, Talk 3

Erwin Pesch
A branch-and-bound algorithm for the acyclic partitioning problem

Coauthor: Jenny Nossack


We focus on the problem of partitioning the vertex set of a
directed, arc- and vertex-weighted graph into clusters, i.e. disjoint sets. Clusters are to be determined such that the sum of the vertex weights within the clusters satisfies an upper bound and the sum of the arc weights within the clusters is maximized. Additionally, the graph is enforced to partition into a directed, acyclic graph where the clusters define the vertices. This problem is known as the acyclic partitioning problem and has been proven to be NP-hard. Real-life applications arise at rail-rail transshipment yards. We propose new integer programming formulations for the acyclic partitioning problem and suggest an exact solution approach based on an integration constraint propagation into a branch-and-bound framework. Computational results are reported to confirm the strength of our approach.


  . Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Cheap Levitra, but also as part of its analogs.