Contributed Session Fri.1.H 3013

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

Cluster 2: Combinatorial optimization [...]

Extended formulations


Chair: Ralf Borndörfer



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

Paolo Serafini
Compact formulations for large-scale LP problems

Coauthor: Giuseppe Lancia


There are many combinatorial problems which can be effectively dealt with via Integer Linear Programming by using column-generation or constraint-generation techniques. When the pricing for column generation can be solved by Linear Programming, it is possible to embed the positive reduced cost condition into the dual of the relaxed integer primal. Similarly, for constraint generation, if the separation problem is a Linear Program, it can be embedded into the integer primal. The new model has polynomial size and has the same lower bounds as the original exponential size model. We call "compact'' this reformulation. The compact reformulation may provide new insight into the problem structure and sometimes exhibits a computational better performance than the original formulation. It is possible to develop compact models for the following problems: Bin packing, Max cut, Stable set, TSP, Minimum routing cost tree, Steiner tree, Cycle packing, Alternate cycle decomposition, Job Shop, Protein fold comparison and various variant of TSP, like Prize collecting TSP and Time window TSP.



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

Achim Hildenbrandt
An extended formulation for the target visitation problem

Coauthors: Olga Heismann, Gerhard Reinelt


The target visitation problem (TVP) is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance traveled, a tour is evaluated also by taking preferences into account addressing the sequence in which the targets are visited. The problem thus is a combination of two well-known combinatorial optimization problems: the traveling salesman and the linear ordering problem. The TVP was introduced to serve the planning of routes for unmanned aerial vehicles (UAVs) and it can be employed to model several kinds of routing problems with additional restrictions. In this talk we want to point out some properties of the polyhedral structure of an associated polytope and also present an extended formulation. We will use this formulation to develop a branch-and-price algorithm. Computational results will be discussed.



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

Ralf Borndörfer
Configuration models for solving integrated combinatorial optimization problems

Coauthors: Olga Heismann, Marika Karbstein, Markus Reuther, Thomas Schlechte, Steffen Weider


The talk proposes configuration models as an effective approach to combinatorial optimization problems that integrate several types of constraints. Configurations are local building blocks of primal solutions. They can be used to express complex requirements, that would be difficult to formulate in terms of constraints, using an exhaustive, but
local, and hence manageable, enumeration of variables. This often gives rise to large, but combinatorially clean packing and covering type models, and it often produces strong LP bounds. Configuration models can be seen as an approach to construct extended formulations; these, in turn, lend themselves to column generation methods. Examples of successful applications of this method include railway track allocation (the configurations are occupations of track segments over time), vehicle rotation planning (the configurations correspond to train compositions), and line planning (configurations correspond to line bundles on an infrastructure segments).


  The majority of financial loan companies provide the service of getting North Carolina Loans Online for U.S. citizens. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.