Quite recently, there has been some progress by different people in analyzing the Random-Edge variant of the Simplex-Algorithm. In my talk, I will survey these developments and present in more detail the first two general (non-trivial) bounds on the worst-case behaviour of the Random-Edge Simplex-Algorithm. These bounds have been obtained in joint work with Bernd Gaertner (ETH Zuerich).

For a real world problem --- transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand --- we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost function that is based on minimizing the expected number of pallets that still need transportation. For speed, the convex relaxation is solved approximately by a bundle approach yielding an online schedule in 5 to 12 minutes for up to 3 warehouses and 40000 articles; in contrast, computation times of state of the art LP-solvers are prohibitive for online application. In extensive numerical experiments on a real world data stream, the approximate solutions exhibit negligible loss in quality; in long term simulations the proposed method reduces the average number of pallets needing transportation due to short term demand to less than half the number observed in the data stream.

We first consider the following question: Is it possible to replace a constraint of a MIP formulation with a new and tighter inequality? We show that, if there is a valid inequality, which dominates a constraint of the formulation, then there is also a coefficient in the formulation that can be strengthened (lifted). We also show that an algorithm, which is based on strengthening one coefficient at a time, stops after a finite number of strengthening steps. We then give examples for which the difference between the quality of the original formulation and a resulting strengthened formulation is relatively large: on some problems, the effect of modifying the coefficients in the original formulation is larger than the effect of adding 20 rounds of mixed integer Gomory cuts (in terms of amount of integrality gap closed). We finish by demonstrating how coefficient strengthening can be used to design a model for a production planning problem. First, an initial formulation of a small problem is produced, and the coefficients in this formulation are strengthened with expensive techniques. The resulting formulation is then evaluated by tracing the logic of each strengthening step. The result is a new understanding of how to model the problem, and possibly a number of fast pre-processing techniques. We believe that this suggests that it might be of interest to construct a tool for strengthening coefficients.

We consider unrelated parallel machine scheduling problems with the objective to minimize the schedule makespan. In addition to its machine-dependence, the processing time of any job is also dependent on the usage of a scarce renewable resource. An amount of k units of that resource, e.g. workers, can be distributed over the jobs at any time, and the more of that resource is allocated to a job, the smaller its processing time. The model generalizes the classical unrelated machine scheduling problem, adding a resource-time tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos, the difference lying in the fact the resource is renewable and not a total budget constraint. We use a two-phased LP rounding technique to assign resources to jobs and jobs to machines. Combined with Graham's list scheduling, we thus prove the existence of a constant approximation algorithm. Moreover, we derive a lower bound for the employed LP-based analysis, and we prove an inapproximability result. (Joint work with A. Grigoriev and M. Sviridenko)

We present new linear time algorithms using the SPQR-tree data structure for computing planar embeddings of planar graphs optimizing certain distance measures. Experience with orthogonal drawings generated by the topology-shape-metrics approach shows that planar embeddings following these distance measures lead to improved quality of the final drawing in terms of bends, edge length, and drawing area. Given a planar graph, the algorithms compute the planar embedding with \begin{enumerate} \item the minimum depth among the set of all planar embeddings of $G$, \item the external face of maximum size among the set of all planar embeddings of $G$, \item the external face of maximum size among the set of all embeddings of $G$ with minimum depth. \end{enumerate}

The presentation is based on a common work with Andras Sebo, Maurice Queyranne and Gerd Finke. (downloadable at: http://www-leibniz.imag.fr/NEWLEIBNIZ/LesCahiers/index.xhtm aout 2004, 108). Many recent extensions of this work will also be presented. I will lecture on common extensions of batch scheduling and graph coloring. Motivated by industrial applications, these extensions have led to interesting research in polyhedral and computational combinatorics. The two main extensions of coloring I will present are: "Bounded coloring" and "Weighted node coloring". In the first, the size of each color class is bounded in cardinality, the goal being to minimize the number of color classes. In the second, each vertex is given a weight and the cost of a color class is defined to be the maximum of the weights of the vertices in the class. The goal being to minimize the sum of the costs of the color classes. I will consider these problems on several classes of perfect graphs. New min-max relations, polynomial algorithms, NP-completeness and approximability results will be surveyed, together with diagrams providing an intuitive overview of the P-NPC frontier along the poset of subclasses of perfect graphs.

Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterization w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs $G$ where the stable set polytope STAB$(G)$ coincides with the fractional stable set polytope QSTAB$(G)$. Relaxations in polyhedral terms deal with the difference of STAB$(G)$ and QSTAB$(G)$ for imperfect graphs $G$. Allowing certain inequalities, the rank constraints, only to cut off all fractional extreme points of QSTAB$(G)$ yields rank-perfect graph as natural superclass of perfect graphs. The dilation ratio $\min \{t:$ QSTAB$(G) \subseteq t$ STAB$(G)\}$ of the two polytopes yields the imperfection ratio of $G$. We introduce a-perfect graphs as special rank-perfect graphs, determine their imperfection ratio and establish consequences for two larger graph classes, near-bipartite and quasi-line graphs, bounding their imperfection ratio by $3/2$.

Recently, Burer and Vandenbussche have proposed to solve lift-and-project relaxations for binary integer problems by exploiting the Augmented Lagrangian technique applied to the primal SDP. A similar approach has been investigated by J. Malick. We will apply the idea to the dual SDP. This approach seems to be more natural, and also gives an interesting interpretation of the augmented Lagrangian approach as a boundary-point method. (joint work with I. Dukanovic, J. Povh, F. Rendl)

We address the question to what extend polyhedral knowledge about individual knapsack constraints suffices or lacks to describe the convex hull of the binary solutions to their intersection. It turns out that the sign patterns of the weight vectors are responsible for the types of constraints needed to describe the convex hull of the intersection. In particular, we introduce the notion of an incomplete set inequality which is based on a combinatorial principle for the intersection of two knapsacks. We outline schemes to compute nontrivial bounds for the strength of such inequalities w.r.t. the intersection of the convex hulls of the initial knapsacks. An extension of the inequalities to the mixed case is also given. This opens up the possibility to use the inequalities in an arbitrary simplex tableau.

Some ideas to formulate and solve multi-stage stochastic integer programs with risk objectives will be discussed. Special attention is paid to risk measures inducing decomposable problem structures.

In this talk we deal with the General Routing Problem defined on a "windy" graph, i.e., a graph G=(V,E) with two nonnegative costs, c_{ij} and c_{ji}, associated with each edge (i,j) in E. We present several families of facet-defining inequalities for its associated polyhedron, including a new class, the Zigzag inequalities, that also apply to other Arc Routing Problems. Computational results with a Branch-and-Cut algorithm are also presented on instances of medium and high size.

Many 'real-world' problems, especially in traffic applications, can be modeled as static network routing or flow problems. Often however, a static model does not give a sufficiently exact picture of the considered application and one has to take care of the time-dependencies as well. A nice and powerful framework that captures such time-dependencies is the theory of dynamic network flows. In this theory the time-expanded network is a well-known tool since it allows to map dynamic, i.e., time-dependent problems to static ones. But it has an important disadvantage: the time-expanded network is extremely large and thus seems to be irrelevant for any practical applications. In this talk we report on a project for routing automated guided vehicles in the Hamburg Harbor. We show various problems that occur when using a static model for this application and therefor present a dynamic model for it. Building up on the time-expanded network, we give an implicit time expansion, that still captures the existing time-dependencies. This dynamic approach not only allows a very compact model but can also be used for designing practically efficient algorithms.

\noindent It is a long standing open problem to find an explicit description of the stable set polytope of \emph{claw-free graphs}. Yet more than 20~years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even no conjecture at hand today. \noindent Such a conjecture exists for the class of \emph{quasi-line graphs}. This class of graphs is a proper superclass of line graphs and a proper subclass of claw-free graphs for which it is known that not all facets have $0/1$~normal vectors. \emph{Ben Rebea's conjecture} states that the stable set polytope of a quasi-line graph is completely described by \emph{clique-family} inequalities. Chudnovsky and Seymour recently provided a decomposition result for claw-free graphs and proved that Ben Rebea's conjecture holds, if the quasi-line graph is not a \emph{fuzzy circular interval graph}. \noindent In this paper, we give a proof of Ben Rebea's conjecture by showing that it also holds for fuzzy circular interval graphs. Our result builds upon an algorithm of Bartholdi, Orlin and Ratliff which is concerned with integer programs defined by circular ones matrices.

Packing a maximum number of disjoint triangles into a given graph is NP-hard. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polytime-solvable for several classes of structured graphs, including chordal and weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as cocomparability graphs, circle graphs, circular-arc graphs, and outerplanar graphs. The results apply more generally to covering the greatest number of nodes by independent packings of members of any family of connected graphs, and to independent packings of the largest number of connected graphs. We give a min-max theorem for the maximum size of an independent packing of connected graphs in a chordal graph.

In this talk, we present some polyedral results related to the bipartite induced subgraph problem and some applications of that problem to DNA sequencing. First we describe several classes of valid inequalities and give necessary and sufficient conditions for these constraints to be facet defining. In particular, we will discuss a large class of valid inequalities, called cellular inequalities. We will show that some special cases of this class can be separated in polynomial time. We develop a branch-and-cut algorithm based on these results. We will finally discuss applications to the so-called SNP haplotype assembly problem in the DNA sequencing process.

The talk addresses the problem of optimizing a polynomial with real coefficients over binary variables. It is shown how to derive a complete polyhedral description of the linearization of such a problem in a simple way from the polyhedral description of the linearization of some quadratic optimization problem. The number of variables in the latter linearization is only slightly larger than in the former. If polynomial constraints are present in the original problem, then their linearized counterparts carry over to the linearized quadratic problem unchanged. If the original problem formulation doesn't contain any constraints, we obtain a reduction to unconstrained quadratic zero-one optimization, which is equivalent to the well-studied max-cut problem. The separation problem for general unconstrained polynomial zero-one optimization thus reduces to the separation problem for the cut polytope. This allows to transfer the entire knowledge gained for the latter polytope by intensive research and, in particular, the sophisticated separation techniques that have been developed. Preliminary experimental results obtained with a straightforward implementation of this approach are reported.

We describe the simplest technique to tackle 0-1 Quadratic Programs among those that turn out to be successful in practice. This method is due to and familiar to the Quadratic Assignment experts, even if it took some time to realize that most approaches to the problem could be interpreted in these terms, whereas it does not appear to be known outside this community. Since the technique is completely general and is by far the most successful one in several other cases, such as Quadratic Knapsack, we illustrate it in its full generality, pointing out its relationship to Lagrangian and linear programming relaxations and discussing further extensions. We believe that this method should be in the background of every practitioner in Combinatorial Optimization.

THE VERTEX SEPARATOR PROBLEM, by Egon Balas (Lecture based on joint work with Cid Carvalho de Souza, University of Campinas, Brazil) The vertex separator (VS) problem in a graph G =(V,E) asks for a partition of V into nonempty subsets A, B, C, such that there is no edge between A and B, and |C| is minimized subject to a bound on max{|A|,|B|}. We give a mixed integer programming formulation of the problem and investigate the vertex separator polytope (VSP), the convex hull of incidence vectors of vertex separators. Central to our investigation is the relationship between separators and dominators. Several classes of valid inequalities are investigated, along with the conditions under which they are facet defining for the VSP. Some of our proofs combine in new ways projection with lifting. A branch-and-cut algorithm for the VS problem based on the inequalities discussed here was implemented and tested on a wide variety of VS problem instances drawn from the literature and inspired by various applications. Our computational experience throws new light on the role of cut density as distinct from cut strength.

Balas and Ng characterized the class of facets of the set-covering polytope defined by inequalities with coefficients in {0,1,2}. We extend their work to the class of inequalities with coefficients in {0,1,2,3}. We discuss conditions for minimality (facetness), generating procedures, (sequential and simultaneous) lifting theory and other interesting theoretical properties of facets in this family.

Virtual private network design is the following problem. Given a communication network, represented as a weighted graph and thresholds on the nodes of this graph, which represent the amount of flow that a node can send to and receive from the network. The task is to reserve capacities at minimum cost and to specify paths between every ordered pair of nodes such that all valid traffic-matrices can be routed along the corresponding paths. This problem is motivated by the fact that the exact amount of flow which is exchanged between terminals is not known in advance and prediction is often illusive. In this talk we provide a new lower bound on the optimum solution to the problem, which is based on general matchings between terminals and is proved with Hu's two-commodity flow theorem. This improves upon previous lower bounds which were based on bipartite matchings between senders and receivers. We apply our new lower bound to show that a simple algorithm which was many times described in the literature, is in fact a 1+R/S-approximation algorithm, where R is the sum of the input thresholds and S is the sum of the output thresholds. If R=S, this shows that the simple routing scheme is a two-approximation. This generalizes the two-approximiability of the symmetric problem, where the input and output thresholds of each node are equal (STOC'01). Finally we provide a new approximation algorithm which, in combination with the simple algorithm mentioned above, yields a 3.55-approximation algorithm for virtual private network design and improves upon previous approximations ($5.55$ STOC'03, $4.74$ SODA'05). (joint work with F. Eisenbrand, G. Oriolo, and M. Skutella)

A variety of integer programming formulations have been proposed for Vehicle Routing Problems (VRPs), including the so-called two- and three-index formulations, the set partitioning formulation, and various formulations based on extra variables representing the row of one or more commodities. Until now, there has not been a systematic study of how these formulations relate to each other. An exception is a paper of Luis Gouveia, which shows that a one-commodity flow formulation of Gavish and Graves yields, by projection, certain `multistar' inequalities in the two-index space. We give a survey of formulations for the capacitated VRP, and then present various results of a similar flavour to those of Gouveia. In particular, we show that:
- the three-index formulation, augmented by certain families of valid inequalities, gives the same lower bound as the two-index formulation, augmented by certain simpler families of valid inequalities,
- the two-commodity flow formulation of Baldacci et al. gives the same lower bound and the same multistar inequalities as the one-commodity Gavish and Graves formulation,
- a certain non-standard multi-commodity flow formulation, with one commodity per customer, implies by projection certain `hypotour-like' inequalities in the two-index space,
- the set partitioning formulation implies by projection both multistar and hypotour-like inequalities in the two-index space. We also briefly look at some other variants of the VRP, such as the VRP with time windows, and derive multistar-like inequalities for them. We also present polynomial-time separation algorithms for some of the new inequalities. This is a joint work with Adam Letchford

We present formulations for the Precedence Constrained Assymetric Travelling Salesman (PCATS) problem obtained by relating formulations of the ATS problem with formulations of the so-called linear ordering problem. We introduce several exponential sized sets of cut-like inequalities to link formulation of these two problems and show that they contain known inequalities as particular cases. From a practical point of view, we discuss polynomial routines to separate these inequalities and give preliminary results evaluating the strength of our formulations. This is a joint work with Luis Gouveia

Let G=(V,E) be a graph with n vertices and m edges. For a red-blue coloring of the vertices of G, let r (resp. b) denote the number of edges with at least one red (resp. blue) end-vertex. Our aim is to find a red-blue coloring such that max(r,b) is minimized. Since this problem is NP-complete, we try to solve it approximately. Thus we present a polynomial time algorithm that solves the problem exactly if G is a tree and a polynomial time approximation algorithm for arbitrary G. We also present a generalization of the problem.

We investigate the benefit of "primal-dual" reformulations of integer programs, using a simple class of integer programs as a model. We report on computational experiments with primal-dual reformulation techniques within a branch-and-cut system, where we obtain promising results for some very hard integer programs. (Joint work with Robert Weismantel.)

We consider the problem of packing a maximum collection of edge disjoint paths connecting a given set of pairs $s_i,t_i$ ($i=1,2,...,k$) in an undirected graph $G$. We show that a relaxation of this problem, the all-or-nothing flow has a polylog integrality gap (for its natural LP) and there is a corresponding approximation algorithm.

This talk is based on ongoing joint work together with Gabriele Di Stefano (Aquila), Stefan Krause (Braunschweig), and Marco Lübbecke (Berlin). Partitioning a permutation into a minimum number of monotone subsequences is known to be NP-hard. We show NP-hardness of partitioning permutations into various other types of subsequences and we derive corresponding mixed integer models. LP rounding yields constant factor approximations. For online partitioning, when the elements of the permutation become available to an algorithm sequentially, we prove a logarithmic lower bound on the competitive ratio. Some computational experiments help evaluating the discussed algorithmic approaches.

The edge coloring problem ask for assigning colors to the edges of a graph such that no two edges of the same color are adjacent and the number of different colors is minimum. We give algorithms for approximate edge coloring of multigraphs, i.e., parallel edges are allowed. For any epsilon>0 we need at most (1+epsilon)OPT+O(1/epsilon) colors. The running time is polynomial in 1/epsilon, the number of nodes in the graph and the logarithm of the maximum edge multiplicity. Previously known algorithms for multigraph edge coloring had asymptotic approximation ratio of at least 11/10. This is joint work with Peter Sanders.

A (3/16)n^2 upper bound is shown for sorting by "short swaps", i.e. reversals of substrings of lengths 2 and 3. This improves an earlier upper bound of (1/4)n^2 given by Heath and Vergara. Related results are also described for sorting 0-1 sequences arranged around a circle by "short swaps" operations. We describe a (3/16) n^2 upper bound on the number of steps needed to sort by "short swaps", i.e. substring reversals of lengths 2 and 3. This improves on the upper bound of (1/4) n^2 given previously by Heath and Vergara. Related results are given concerning sorting networks and sorting 0-1 sequences by short swaps.

We give a new 0-1 linear program which modelizes the minimum clique partition problem (i.e. the coloring problem in $\overline{G}$). According to our knowledge, this is the first formulation using only edge variables (and actually a significant number of edge variables can be ignored). The continuous relaxation of this 0-1 program can be solved in polynomial time. This leads to new polynomial bounds for the chromatic number and also to a 3-approximation greedy algorithm to compute $\chi(\overline{G})+m-n$.

This talk is dedicated to reverse 1-median problems on graphs. We are given an undirected graph G=(V,E) with edge lengths c(e) > 0 for e in E and vertex weights w(v) > 0 for v in V. Each edge e is associated with a cost function f_e(b_e) which corresponds to the cost of decreasing the edge length c(e) by the amount b_e. Moreover, we are given a prespecified vertex v_0 in V and a budget B. The task in the reverse 1-median problem is to reduce the edge lengths such that the total cost caused by this process does not exceed the given budget and such that the sum of the weighted distances from all vertices to v_0 is minimized. In other words, the goal of the reverse 1-median is to improve the objective function value of the given vertex v_0 with respect to the objective function of the 1-median problem as much as it is possible with the given budget. In general, this problem is strongly NP-hard for arbitrary graphs even for linear cost functions and there does not exist any polynomial time algorithm with constant approximation ratio unless P=NP holds. In this talk we will present a linear time algorithm for the special case where G is a cycle. We show that this case reduces to determining a global minimum of a suitably defined piecewise linear function z(x). It turns out that this function has O(|V|) breakpoints. Based on these observations we obtain a linear time algorithm for the reverse 1-median problem on a cycle. Further properties of the function z ensure that the solution determined by our algorithm is integral provided that the input data are integers. (Joint work with R.E. Burkard and J. Hatzl)

We analyze a separation procedure for Mixed-Integer Programs related to the work of Gomory and Johnson on interpolated subadditive functions. Our approach has its roots in the Gomory-Johnson characterization on the master cyclic group polyhedron. We compute, for the first time, the lower bound value obtained when adding (implicitly) all the interpolated subadditive cuts that can be derived from the individual rows of an optimal LP tableau, thus approximating the optimization over the so-called Gomory's Corner polyhedron. The computed bound is compared with that obtained when only Gomory mixed-integer cuts are used, on a large test-bed of MIPLIB instances.

Mixed integer programs for batch processes as occurring in the chemical industry are analyzed and new computational results on benchmark problems are reported. Moreover we report on a new iterated construction heuristic which yields favorable results for problems of higher complexity.

We study LP formulations for the continuous mixing set: \[ P^{CMIX}=\{(s,r,z) \in R \times R^{n}_+ \times Z^{n} | s + r_{j}+ z_j \geq f_j, \ \forall j \}. \] and $P_+^{CMIX}=P^{CMIX} \cap \{s \geq 0\}$. These sets regularly appear as substructures in complex inventory problems modelled as mixed-integer programs. Also, $P^{CMIX}$ generalizes the MIR set and the mixing set which have proven useful in solving general MIPs. In a recent paper, Miller and Wolsey give an extended formulation for the continuous mixing set of size $O(n^2)$ variables and constraints. We present two new LP formulations of polynomial size for $P^{CMIX}$. The first enables us to show that adding any number of constraints of the form $z_i-z_j \leq b$ or $z_i \leq b$ where $b$ is integer does not destroy the integrality of $conv(P^{CMIX})$. The second is very compact as it has only $O(n)$ variables and $O(n^2)$ constraints. We also define a family of valid inequalities for $P^{CMIX}$ which are shown to be sufficient to describe the convex hull of the set. These ``cycle'' inequalities generalize the ``mixing'' inequalities of Gunluk and Pochet. The separation can be carried out in $O(n^3)$ time.

How difficult is, in practice, to optimize exactly over the first Chvatal closure of a generic ILP? Which fraction of the integrality gap can be closed this way, e.g., for some hard problems in the MIPLIB library? Does it pay to insist on rank-1 Chvatal-Gomory inequalities until no such inequality is violated, or one should better follow the usual strategy of generating (mixed-integer) Gomory cuts of any rank from the optimal tableau rows? How effective is this general-purpose approach for solving matching problems, where the first Chvatal closure coincides with the integer hull? Can this approach be useful as a research (off-line) tool to guess the structure of some relevant classes of inequalities, when a specific combinatorial problem is addressed? In this paper we give, for the first time, concrete answers to the above questions, based on an extensive computational analysis. Our approach is to model the rank-1 Chvatal-Gomory separation problem, which is known to be NP-hard, through a MIP model, which is then solved through a general-purpose MIP solver. As far as we know, this approach was never implemented and evaluated computationally by previous authors, though it gives a very useful separation tool for general ILP problems. We report the optimal value over the first Chvatal closure for a set of ILP problems from MIPLIB 3.0. We also report, for the first time, the optimal solution of a very hard instance from MIPIB 2003, namely ``nsrand-ipx'', obtained by using our cut separation procedure to preprocess the original ILP model. Finally, we describe a new class of ATSP facets found with the help of our separation procedure.

This talk focuses on the outer description of the convex hull of all integer solutions to a given system of linear inequalities. It will be shown that if the given system contains lower and upper bounds for the variables, then the convex hull can be produced by iteratively generating so-called mod-2 cuts only. This fact is surprising and might even be counterintuitive, since many integer rounding cuts exist that are not mod-2, i.e., representable as the zero-one-half combination of the given constraint system. The key, however, is that in general many more rounds of mod-2 cut generation are necessary to produce the final description compared to the traditional integer rounding procedure.

We investigate a network design problem under traffic uncertainty which arises when provisioning Virtual Private Networks (VPNs): given a set of terminals that must communicate with one another, and a set of possible traffic matrices, sufficient capacity has to be reserved on the links of the large underlying public network so as to support all possible traffic matrices while minimizing the total reservation cost. The problem admits several variants depending on the desired topology of the reserved links, and the nature of the traffic data uncertainty. We present compact linear mixed-integer programming formulations for the problem with the classical hose traffic model and for a new, less conservative, robust variant relying on the traffic statistics that are often available. These flow-based formulations allow to solve optimally medium-to-large-size instances with commercial MIP solvers. We also propose a combined branch-and-price and cutting plane algorithm to tackle larger instances. Computational results obtained for several classes of instances are reported and discussed. Our linear mixed-integer formulations and the algorithm can be extended to the problem of network design under the polyhedral demand uncertainty model, where the requests are assumed to lie in a arbitary polyhedron or a union of polyhedra.