It is shown that the optimum of an integer program in fixed dimension with a fixed number of constraints can be computed with O(s) basic arithmetic operations and comparisons, where s is the binary encoding length of the input. This improves on the quadratic running time of previous algorithms, which are based on Lenstra's algorithm and binary search.

We present the results of our recent computational experience with 0-1/2 cuts embedded in ILOG Cplex 8.1. Joint work with G. Andreello and A. Caprara

We deal with non-rank facets of the stable set polytope of claw-free graphs. We extend results of Giles \& Trotter by (i) showing that for any nonnegative integer $a$ there exists a circulant graph whose stable set polytope has a facet-inducing inequality with ($a$,$a+1$)-valued coefficients (rank facets have only coefficients 0, 1), and (ii) providing new facets of the stable set polytope with up to five different non-zero coefficients for claw-free graphs. We prove that coefficients have to be consecutive in {\em any} facet with {\em exactly} two different non-zero coefficients (assuming they are relatively prime). Last but not least, we present a complete description of the stable set polytope for graphs with stability number 2, already observed by Cook and Shepherd.

The intention of the talk is to give an introduction into the area of "flows over time" or "dynamic flows". Flows over time have been introduced about forty years ago by Ford and Fulkerson and have many real-world applications such as, for example, traffic control, evacuation plans, production systems, communication networks, and financial flows. Flows over time are modeled in networks with capacities and transit times on the arcs. The transit time of an arc specifies the amount of time it takes for flow to travel from the tail to the head of that arc. In contrast to the classical case of static flows, a flow over time specifies a flow rate entering an arc for each point in time and the capacity of an arc limits the rate of flow into the arc at each point in time. We discuss recent approximation and hardness results for flows over time with multiple commodities and costs. The talk is based on joint work with Lisa Fleischer, Alex Hall, and Steffen Hippler.

Motivated by applications in road traffic control, we consider network flows featuring special characteristics. In contrast to classical static flow theory, time plays a decisive role. Firstly, the flow value on an arc may change over time. In the context of road traffic, this property reflects that the traffic volume on a street changes throughout the day. Secondly, there are transit times on the arcs which may vary with the current amount of flow using this arc. The latter feature is crucial for various real-life applications of flows over time; yet, it dramatically increases the degree of difficulty of the resulting optimization problems. Most problems dealing with flows over time and constant transit times can be translated to static flow problems in time-expanded networks. We develop an alternative time-expanded network which implicitely models flow-dependent transit times. Again, the whole algorithmic toolbox developed for static flows can be applied. This approach does not entirely capture the behavior of flows over time with flow-dependent transit times. However, we present approximation results for the quickest (multicommodity) flow problem which affirm its surprising quality.

The fractional prize collecting Steiner Tree problem is the following problem: Given a graph G=(V,E) with edge costs c_e and prizes for each vertex b_v>0, and a root vertex v0; the problem is to determine a subset W from V and a subset F from E so that G'=(W,F) is a subgraph of G spanning W and v0 and maximizing the function: sum_{v \in W} b_v / sum_{e \in F} c_e. We present a new O(n log n) algorithm in the case that G is a tree.

We show that the problem to decide whether two (convex) polytopes, given by their vertex-facet incidences, are combinatorially isomorphic is graph isomorphism complete, even for simple or simplicial polytopes. On the other hand, we give a polynomial time algorithm for the combinatorial polytope isomorphism problem in bounded dimensions. Furthermore, we derive that the problems to decide whether two polytopes, given either by vertex or by facet descriptions, are projectively or affinely isomorphic are graph isomorphism hard.

We present a branch & cut-approach for drawing graphs symmetrically in a fuzzy way: for a given graph G, we look for a graph G' that admits a symmetric drawing and that results from G by a minimum number of edge deletions (or creations). A similar approach can be used to search for (node- or edge-induced) common subgraphs in a fuzzy way.

For resource constrained scheduling problems, it is sometimes important to know all inclusion-minimal subsets of jobs that must not be processed simultaneously, the so-called minimal forbidden sets. They are given only implicitly by a linear inequality system, and can be interpreted in a more general context as the "minimal covers" of an independence system. We present several complexity results related to computation, enumeration, and counting of the minimal covers of an independence system. On this account, a simple backtracking algorithm for the enumeration of minimal covers is discussed as well. (Joint work with Frederik Stork)

Finding a linear layout of a graph having minimum bandwidth is a combinatorial optimization problem that was studied since the 60s. Differently from other classical problems, the approach based on stating a suitable integer linear programming formulation and solving the associated linear programming relaxation seems to be useless in this case. This makes it nontrivial to design algorithms capable of solving to optimality instances of reasonable size. In this paper, we illustrate a new simple lower bound on the optimal bandwidth and its extension within an enumerative algorithm, leading to integer linear programming relaxations that can be solved efficiently and provide effective lower bounds if part of the layout is fixed. Keeping the integrality constraints in these relaxations is essential for this purpose. We show that the resulting method can solve to proven optimality 24 out of the 30 instances with less than 200 nodes from the literature, each within less than one minute on a personal computer. The new approach is also analyzed on randomly generated instances with up to 1000 nodes. Moreover, we propose for the first time a method to compute the well-known density lower bound on the optimal bandwidth, that succeeds in finding this bound within minutes for most literature instances with up to 250 nodes.

We describe a new software system SCIL that introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint programming and contribute significantly to the expressive power, ease of use, and efficiency of constraint programming systems.

We explore Small Instance Relaxations in the branch-and-cut approach to the symmetric TSP. For small TSP instances up to $10$ cities all facets of the associated polytopes are known. We exploit this pool of facets. The separation procedure is: Shrink a TSP support graph to at most $10$ vertices, search a violated facet in the pool, and eventually lift it to obtain a cutting-plane. We invest the cactus-tree in the generation of promising small graphs. Minimum and near-minimum multiway cuts are considered. We present an algorithm generating all $k$-way cuts of a graph with weight $k\lambda/2$ where $\lambda$ is the weight of a global mincut. Computational results demonstrating the potential of the SIR approach are provided. Advantages of both SIRs and local cuts by Applegate et al.\ are mentioned.

We investigate semidefinite relaxations of the Max-Cut problem, which are formulated in terms of the edges of the graph, thereby exploiting the (potential) sparsity of the problem. We show how this is related to higher order liftings of Anjos and Wolkowicz and Lasserre. Contrary to the basic semidefinite relaxation, which is based on the nodes of the graph, the present formulation leads to a model which is significantly more difficult to solve. We present preliminary computational results where we combine interior point methods with the bundle concept. These results indicate that this model is manageable for sparse graphs on a few hundred nodes and yields very tight bounds. (joint work with F. Rendl)

In classical two-stage stochastic programming the expected value of the total costs is minimized. Recently, mean-risk models - studied in mathematical finance for several decades - have attracted attention in stochastic programming. We consider Conditional Value-at-Risk as risk measure in the framework of two-stage stochastic integer programming. The talk addresses structure, stability and algorithms for this class of models. In particular, we study continuity properties of the objective function, both with respect to the first-stage decisions and the integrating probability measure. Further, we present an explicit mixed-integer linear programming formulation of the problem when the probability distribution is discrete and finite. Finally, a solution algorithm based on Lagrangean relaxation of nonanticipativity is proposed.

We consider 2-Dimensional (Finite) Bin Packing (\FBP), which is one of the most important generalizations of the well-known Bin Packing (\BP) and calls for orthogonally packing a given set of rectangles (that cannot be rotated) into the minimum number of unit size squares. There are many open questions concerning the approximability of \FBP, whereas the situation for the {\em 2-stage} case, in which the items must first be packed into {\em shelves} that are then packed into bins, is essentially settled. For this reason, we study the asymptotic worst-case ratio between the optimal solution values of the 2-stage and general \FBP, showing that it is equal to $\Tinf=1.691\ldots$, the well-known worst-case ratio of the {\em Harmonic} algorithm for \BP. This ratio is achieved by packing the items into shelves by decreasing heights as in the Harmonic algorithm and then optimally packing the resulting shelves into bins. This immediately yields polynomial time approximation algorithms for \FBP\ whose asymptotic worst-case ratio is arbitrarily close to $\Tinf$, i.e.\ substantially smaller than $2+\eps$, that was the best ratio achievable so far and constituted the first (recent) improvement over the $2.125$ ratio shown in the early 80s. In particular, we manage to push the approximability threshold below $2$, which is often a critical value in approximation. The main idea in our analysis is to use the fact that the fractional and integer \BP\ solutions have almost the same value, which is implicit in the approximation schemes for the problem, as a stand-alone structural result. This implies the existence of modified heights for the shelves whose sum yields approximately the number of bins needed to pack them. With this in mind, our proof can easily be adapted to different cases. For instance, we can derive new upper bounds on the worst-case ratio of several shelf heuristics for \FBP, among which a bound of $(\frac{17}{10})(\frac{11}{9})=2.077\ldots$ (rather than $2.125$) on the 20-years-lasting champion mentioned above. Moreover, we can easily derive the asymptotic worst-case ratio between the 2-stage and general \FBP\ solution values as a function of the maximum width of the rectangles, showing that this ratio is independent of the maximum height.

Several combinatorial optimization problems can be formulated as large size Set-Covering Problems. We use the Set-Covering formulation to obtain a general heuristic algorithm for this type of problems, and describe our implementation of the algorithm for solving two variants of the well-known (One-Dimensional) Bin Packing Problem: the Two-Constraint Bin Packing Problem and the basic version of the Two-Dimensional Bin Packing Problem. In our approach, both the ``column generation" and the ``column optimization" phases are heuristically performed. Extensive computational results on test instances from the literature show that, for the two considered problems, this approach is competitive, with respect to both the quality of the solution and the computing time, with the best heuristic and metaheuristic algorithms proposed so far.

The goal of the Clocktree-Design Problem is to distribute a signal from a source on a chip to several (currently up to 200.000) sinks, using a clocktree consisting of wires and repowering circuits. In the classical problem, the signal has to reach all sinks simultaneously, but by using individual arrival time intervals at the sinks, the frequency of the chip can be increased without violating timing restrictions. I will present the first algorithm for the arisen 'Clocktree Problem with individual arrival time intervals'. Tested on some actual chips, we could improve the frequency by approx. 10\%-20\% while decreasing the power consumption compared to clocktrees designed by the classical method. The algorithm is now used for industrial designs and the first chips designed by this tool are already in production.

We study different models for planning the capacity of telecommunication networks, with the restriction that the capacity has to be installed on a tree. Different versions of the problem are presented, and some polynomially solvable cases are identified, while the general problem is shown to be NP-hard. For the special case of unit costs in a complete graph, the optimal solution turns out to be a Gomory-Hu tree representing the minimum cuts in the graph. We present the complete description of the associated polyhedron for small instances of this special case, provide a conjecture on the polyhedron in higher dimensions and outline some links with the all-pair minimum cut problem.

We consider the nearest-neighbor problem, which is defined as follows: given a fixed set P of n data points in some metric space X, build a data structure such that for each given query point q a data point from P closest to q can be found efficiently. The underlying metric space is usually the d-dimensional real space R^d together with one of the L_p-metrics, 1<= p<= infty. In many applications, the dimension d of the search space is quite high and can reach several hundreds or even several thousands. Therefore, running times and storage requirements exponential in d are prohibitive in these cases. Because of their exponential dependence on the dimension, all known techniques for exact nearest-neighbor problem are in fact in high dimensions not competitive with the brute-force method, which just determines the distance of q to each point in P and selects the minimum. This talk presents algorithms for solving the high-dimensional exact nearest-neighbor problem with respect to the L_{infty}-distance. These algorithms considerably improve the brute-force method, they are simple and easy to implement, and have a linear storage requirement.

Given an infeasible linear inequality system, the maximum feasible subsystem problem (MaxFS) is to find a feasible subsystem of maximum cardinality. MaxFS is NP-hard and has many interesting applications, some of which will be presented. For the investigation of the 0-1 polytope corresponding to MaxFS, results about independence system polyhedra can be applied, e.g., generalized antiweb facets only occur under very special circumstances. The tools used for this result are based on a (combinatorial) connection between the minimal infeasible subsystems and the support of vertices of an alternative polyhedron.

Martin Groetschel, Laslo Lovasz and Alexander Schrijver use a construction of Dmitrii Yudin and Arkadii Nemirovskii to polynomially separate a point x from a centered bounded convex K using a membership oracle. In this note, we present a natural and simple construction which solve the same problem but for the simpler case of polyedra. Namely, given a well defined polyedron P with non-empty interior, a point x not in P and a point a in int(P), using a polynomial number of calls of the membership oracle, we find a facet of P whose supporting hyperplane separates x from P.

It is a longstanding open problem whether there exists a polynomial size description of the perfect matching polytope. We give a partial answer to this question by proving the following result. The polyhedron defined by the constraints of the perfect matching polytope which are active at a given perfect matching can be obtained as the projection of a compact polyhedron. Thus there exists a compact linear program which is unbounded if and only if the perfect matching is not optimal with respect to a given edge weight. This result provides a simple reduction of the maximum weight perfect matching problem to compact linear programming.

Given a planar point set we investigate perfect matchings, spanning trees, and triangulations of minimum stabbing number. The stabbing number of a matching (tree, triangulation) is the maximal number of intersections of any line with matching edges (tree edges, triangles). A small stabbing number is a desirable property of data structures for location queries in the widest sense. We prove that minimizing the stabbing number is NP hard for all three problems. We present integer programming formulations and evaluate their performance computationally. We outline how to obtain approximation results from the LP relaxation.

Bisubmodular functions are a natural ``directed'', or ``signed'', extension of submodular functions with several applications. Recently Fujishige and Iwata showed how to extend the Iwata, Fleischer, and Fujishige (IFF) algorithm for submodular function minimization (SFM) to bisubmodular function minimization (BSFM). However, they were able to extend only the weakly polynomial version of IFF to BSFM. Here we investigate the difficulty that prevented them from also extending the strongly polynomial version of IFF to BSFM, and we show a way around the difficulty. This new method gives a somewhat simpler strongly polynomial SFM algorithm, as well as the first combinatorial strongly polynomial algorithm for BSFM.

In traditional multi-commodity flow theory, the task is to send a certain amount of each commodity from its start to its target node, subject to capacity constraints on the edges. However, no restriction is imposed on the number of paths used for delivering each commodity; it is thus feasible to spread the flow over a large number of different paths. Motivated by routing problems arising in real-life applications, such as, e.\,g., telecommunication, unsplittable flows have moved into the focus of research. Here, the demand of each commodity may not be split but has to be sent along a single path. In this talk, a generalization of this problem is studied. In the considered flow model, a commodity can be split into a bounded number of chunks which can then be routed on different paths. In contrast to classical (splittable) flows and unsplittable flows, already the single-commodity case of this problem is NP-hard and even hard to approximate. We present approximation algorithms for the single- and multi-commodity case and point out strong connections to unsplittable flows. Moreover, results on the hardness of approximation are presented. It particular, we show that some of our approximation results are in fact best possible, unless P=NP.

The length of the shortest cycle in a graph $G$ is called the girth of $G$. We show that if $G$ has girth at least $g$ and average degree at least $d$, then $tw(G) = \Omega \left (\frac {1}{g+1} (d-1)^{\lfloor (g-1)/2 \rfloor} \right )$. In view of a famous conjecture regarding the existence of graphs with girth $g$, minimum degree $\delta$ and having at most $c (\delta - 1)^ {\left \lfloor (g-1)/2 \right \rfloor}$ vertices (for some constant $c$), this lower bound seems to be almost tight (but for a multiplicative factor of $g+1$).

Graphs with circular symmetry, called webs, are relevant w.r.t. describing the stable set polytopes of quasi-line graphs and claw-free graphs. However, even the problem of finding all the facets of stable set polytopes of webs is open. We contribute to this problem by showing that the stable set polytopes of almost all webs admit non-rank facets, i.e., that almost all webs are not rank-perfect. This is joint work with Arnaud Pecher.

The k-partition problem is: Given a graph G and a positive integer k, partition the vertices of G into k sets, A(1), A(2), ..., A(k), where some of the sets may be required to be stable sets and some may be required to induce complete graphs, and some pairs A(i), A(j) may be required to be completely joined and some pairs may be required to not be joined at all, or decide that no such partition exists. The list k-partition problem is the same problem with the added constraint that each vertex v is given a list L(v) of which of the sets A(i) of the partition it can be in. Several well-known problems can be formulated as partition problems: clique-cutset is a 3-partition problem; 2-clique cutset and skew partition are 4-partition problems. We have classified the list 4-partition problems as either polytime-solvable or NP-complete, with a single exception. For that exception, a subexponential algorithm exists. This is joint work with Elaine Eschen, Chinh Hoang and R. Sritharan.

Given a simple graph $G=(V,E)$. We call biclique of $G$, the edge set of a complete bipartite partial subgraph of $G$. We say that $F\subset E$ is independent, if there is a biclique of $G$ including $F$. A minimum partition of $E$ into independent sets leads to a minimum biclique covering of $G$ (i.e. a minimum cardinality family of bicliques of $G$ covering $E$). When $G$ has positive weight function on the edges, we prove that finding a minimum weight dependent set of $G$ is in $P$. Thus, thanks to the ellipsoid method, we obtain an integer programming formulation of Minimum Biclique Covering Problem with polynomial continous relaxation. We also show that, generally, a maximum minimal dependent set of $G$ has size $\omega (G)$ or $\omega (G) -1$.

The construction of inverter trees becomes more and more important for timing optimization and reduced power consumption in physical design of modern chips. Inverter trees are signal trees where a signal has to be distributed from a source (an output pin of some circuit) to a number of sinks (input pins of other circuits). Feasible inverter trees have to respect several constraints (load constraints, parity constraints, and timing constraints). Moreover, these trees have to be embedded in a rectilinear fashion on the chip image avoiding blockages (preplaced macros and other circuits). Optimization goals are to maximize the slack and to minimize power consumption. In this talk we present bounds for the slack and power consumption, and propose a slack-bound-based greedy-like clustering heuristic to build up the inverter tree topology. Improved approximations for minimum power consumption rely on the approximation of rectilinear Steiner trees with length restrictions on obstacles. For the latter problem, we sketch a simple 2-approximation and more involved $\frac{2k}{2k-1} \alpha$--approximation algorithms where $\alpha$ denotes the performance guarantee for the ordinary Steiner tree problem in graphs and $k \geq 4$. Finally, we briefly report results from a computational study with instances from ASICS of IBM. Our computational results demonstrate that our code usually builds up inverter trees which are relatively close to the bounds and which compare favorably with a standard code currently used by IBM.