This survey talk will give a historical perspective on the polyhedral approach to solving mixed integer linear programs.

The validity of Gomory Mixed Integer Cuts relies on the correctness of arithmetic calculations, which is not guaranteed in floating point arithmetic used by modern computers. In practice, numerical tolerances and low rank cuts are used to try to overcome this problem. These measures, however, do not guarantee that the resulting cuts will be valid. In this work we propose solutions to always generate valid cuts, and analyze the trade-offs in working harder to generate them.

It has been known for some time that valid inequalities for the 0-1 knapsack polytope can be used effectively as cutting planes for general 0-1 linear programs. We present some new results on the separation problems associated with these inequalities. We give: 1. An exact separation algorithm for the extended cover inequalities of Balas (1975) that runs in O(nb) time, where n is the number of items and b is the capacity of the knapsack. 2. A remarkably effective separation heuristic for the lifted cover inequalities of Balas (1975) and Wolsey (1975), that runs in O(n^2) time. 3. An exact separation algorithm for the weight inequalities of Weismantel (1997) that runs in O((n+a')b) time, where a' is the weight of the largest item. 4. An exact separation algorithm for the 0-1 knapsack polytope itself. Computational experiments on MIPLIB instances have given interesting and very encouraging results. This talk is based on joint work with Konstantinos Kaparis, University of Southampton.

We discuss an implementation of the lexicographic version of Gomory's fractional cutting plane method and of two heuristics mimicking the latter one. In computational testing on a battery of MIPLIB problems we compare the performance of these variants with that of the standard Gomory algorithm, both in the single-cut and in the multi-cut (rounds of cuts) version, and show that they provide a radical improvement over the standard procedure. In particular, we report the exact solution of ILP instances from MIPLIB such as stein15, stein27, and bm23, for which the standard Gomory cutting plane algorithm is not able to close more than a tiny fraction of the integrality gap. (Joint work with Egon Balas and Arrigo Zanette)

We study a system of linear inequalities associated with the uncapacitated facility location problem. We show that this system defines a polytope with integer extreme points if and only if the graph does not contain a certain type of odd cycles. We give a polynomial algorithm to recognize this type of cycles. We also derive odd cycle inequalities and give a separation algorithm.

We study a well-known linear programming relaxation of the p-median problem. We characterize all directed graphs for which this system of inequalities defines an integral polytope. This shows that for these graphs the p-median problem is easy to solve. We also have a polynomial algorithm that recognizes this class of graphs.

In this talk, we give a review of the group relaxation approach for the solution of mixed integer programs. We first survey the seminal work of Gomory and Johnson on finite and infinite group problems. Second, we describe the different tools that have been proposed for the study of group problems, including newer results that have been introduced for group problems with multiple constraints. Third, we discuss the recent computational work of various authors regarding the corner polyhedron and group cuts. We conclude with remarks and possible directions of future research with respect to the group approach.

One way to construct the Gomory Mixed Integer Cuts (GMIC) is the following: (a) Create a single-row group relaxation of a MIP. (b) Fix the integer variables to zero and generate a minimal cut with respect to the continuous variables. (c) Then lift the integer variables into this cut. Recently, Andersen et al. (2006), Borozan and Cornuejols (2007), and Cornu\'ejols and Margot (2007) characterized the minimal and extreme inequalities for the two-row group relaxation in which the integer variables are fixed to zero. In this talk, we consider ways to lift the integer variables into these cuts (i.e., generating cuts similar to the GMIC, except now using two rows).

Different classes of valid inequalities for the 0-1 single node flow set have been studied in the literature and superadditive lifting procedures have been suggested to strengthen them. This includes generalized flow cover inequalities. Furthermore, it is well known that particular complemented mixed integer rounding (c-MIR) inequalities for certain mixed knapsack relaxations of the 0-1 single node flow set are at least as strong as special cases of generalized flow cover inequalities. The branch-and-cut framework SCIP incorporates a cutting plane separator which utilizes this approach. In this talk, we introduce our separation heuristic for the so-called c-MIR flow cover cuts and present computational results concerning the impact of different aspects of the algorithm. Computational experiments have shown that our final separator helps to improve the overall performance of SCIP even if it is used in combination with the general c-MIR separator.

Joint work with Andrea Lodi and Matteo Fischetti. Split cuts are a famous class of disjunctive cuts for mixed integer linear programs. By fixing a priori the disjunction, split cuts can be separated by solving a so called Cut Generating Linear Program (CGLP). The CGLP is however defined on a polyhedral cone which needs to be truncated by means of some normalization conditions, and different normalization conditions yield very different cuts. Another important class of valid inequalities are Mixed Integer Gomory (MIG) cuts. Violated MIG cuts can be read from the optimal simplex tableau without any computational effort. We recall the correspondence between MIG cuts from the simplex tableau and basic solutions of the CGLP, and we investigate the impact of the normalization on the separated inequalities. We compare different normalization conditions showing that even the most effective ones can ``select" optimal basic solutions of the CGLP corresponding to very weak cuts. In particular, we show that redundant constraints hurt the separation procedure, since they create many ``weak" vertices of the CGLP and can cheat the normalization in selecting ``strong" cuts. A computational analysis is reported and discussed.

We present a new graph composition that produces a graph $G$ from a given graph $H$ and a fixed graph $B$ called gear and we study its polyhedral properties. This composition yields counterexamples to a conjecture on the facial structure of $STAB(G)$ when $G$ is claw-free. (Joint work with A. Galluccio and P. Ventura)

NOTE: If there is pressure, forget about this talk and give the slot to others. If you would like to hear the talk: We define a satisfiability problem called 3IFFSAT that is a particular case of SAT. The instances consist of a combination of 2CNF and 3CNF clauses. The problem 3IFFSAT is NP-complete. But for a subclass that arises from certain applications, the problem can be solved in linear time using logic decomposition techniques.

Biology and molecular medicine are two areas of research with a high potential of discovering fundamental mechanisms that may influence our way of thinking about the living cell or the human body. So far, the majority of results discovered in these areas are based on intuitive interpretation of experimental or statistical data. A key question is whether mathematics can contribute to advance these fields. In this talk we shall give a clear positive answer by presenting an exact mathematical approach to a fundamental problem in systems biology, namely, to the problem of reconstructing structure and function of causal interaction networks of biological systems from experimental data. Our approach provides a provenly complete list of all feasible network alternatives that account for the experimentally observed mass or signal flux in the system (or ensures that no solution exists using the considered parameters only).

We present an overview of integer linear programming problems arising in the analysis of metabolic networks in computational biology.

It has recently been shown that a very general class of continuous and discrete NP-hard optimization problems can be formulated as linear problems over the cone of completely positive (CPP) matrices. CPP matrices are also doubly nonnegative (DNN), and up to size 4x4 these matrix classes agree. For the 5x5 case we give a precise characterization of how a matrix that is DNN but not CPP differs from a CPP matrix. We also show how an extreme matrix of this type can be separated from the cone of CPP matrices. (Joint work with Sam Burer and Mirjam Duer)

The minimum k-partition (MkP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. We propose a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. The two key ingredients for this algorithm are: the combination of semidefinite programming with polyhedral results; and a novel iterative clustering heuristic (ICH) that finds feasible solutions for the MkP problem. The SBC algorithm computes globally optimal solutions for dense graphs with up to 60 vertices, for grid graphs with up to 100 vertices, and for different values of k, providing the best exact approach to date for 3 or more partitions. This is joint work with Bissan Ghaddar (Waterloo) and Frauke Liers (Cologne).

Piecewise linear functions (PLFs) are important on their own and as an approximation to nonlinear functions. Beale and Tomlin showed that modeling PLFs through special ordered sets of type 2 (SOS2) is far superior to using 0-1 variables. Here we give cutting planes that are valid for the SOS2 formulation. Our computational experience shows that our cutting planes reduce tremendously the time required by MIP branch-and-cut and SOS2 branch-and-bound for finding an optimum of a separable PLF subject to linear constraints. Joint work with Ming Zhao.

A central result in the theory of integer optimization states that a system of linear diophantine equations $A x = b$ has no integral solution if and only if there exists a vector in the dual lattice, $y^TA$ integral such that $y^Tb$ is fractional. We extend this result to systems that both have equations and inequalities $\{Ax=b, Cx\leq d\}$. We show that a certificate of integral infeasibility is a linear system with $\rank(C)$ variables containing no integral point. The result also extends to the mixed integer setting. This is joint work with Q. louveaux and K. Andersen.

joint work with Matthias Jach and Robert Weismantel For deriving strong global bounds on the optimal value of mixed-integer nonlinear optimization problems, the question of determining the convex and convave envelopes for nonlinear functions is of major interest. Despite this necessity of having convex and concave envelopes at hand, very little is known in the literature. The limited availability of formulas for the envelopes is due to the fact that their standard representations are non-convex optimization problems that are intractable, in general. In this talk we show how to reduce the problem of computing the envelopes to lower-dimensional optimization problems when the underlying function meets certain convexity properties.

Concave cost minimization arises frequently in practice, yet little seems to be known about how to solve these problems (optimally or approximately). We show how to use methods from fixed cost minimization to solve generic and specilized versions of concave cost minimization problems. This is joint work with Dan Stratila.

We give an efficient algorithmic framework for optimizing the sum of an binary-encoded "external" weight function and an arbitrary function of a fixed number of "internal" weight functions over a set of integer points, when the internal weights are encoded in binary but take only a fixed number of values. The framework yields an efficient algorithm when the integer points come from the bases or independent sets of a matroid/polymatroid or from a multi-dimensional knapsack. We also have an efficient algebraic algorithm for the case of vectorial matroids, when the internal weights are encoded in unary and there is no external weight function. For the case of bases of a matroid, we describe an application to model fitting. Joint work with Robert Weismantel and Shmuel Onn.

Binet matrices furnish a direct generalization of network matrices and arise from the node-edge incidence matrices of bidirected graphs in the same way as network matrices do from directed graphs. We provide a polynomial-time algorithm for testing whether a given matrix is binet.

The majority judgement provides a theoretical and practical answer to the problem of finding a mechanism that amalgamates the opinions, evaluations or "preferences" of many individuals into a society's or a jury's opinion, evaluation and rank-ordering of candidates or alternatives. In particular, it does away with the classical paradoxes and impossibilities of traditional social choice theory (including Arrow's). It has been tested in elections and wine competitions.

Many problems in combinatorial optimization have supermodular, or increasing marginal optimal costs. In a cooperative game with supermodular costs, the average cost per player increases as the number of players increases, diminishing the appeal of sharing costs with other players. This observation leads us to wonder, "how much do we need to penalize a coalition of players for defecting in order to achieve cooperation?" This notion is captured in the least core and least core value of a cooperative game. In this talk, we consider the computational complexity and approximation of the least core value of supermodular cost cooperative games, and uncover some structural properties of the least core of these games along the way.

The problem of finding a shortest path in a network, subject to a single additive resource constraint, is the simplest case of a constrained network shortest path problem. Resource constrained shortest path problems abound as subproblems, for example, in column generation for airline planning problems. This talk will review recent progress interleaving Lagrangian relaxation, preprocessing and enumeration, to accelerate solution of such problems. Application to paths in Euclidean space will be discussed, and a network discretization of space presented that can be proved to give paths that converge to globally optimal solutions, even for highly non-convex objectives.

We consider various properties of a parity domination problem: given a graph $G$, one is looking for a subset $S$ of the vertex set such that the open/closed neighborhood of each vertex contains an even/odd number of vertices in $S$ (it is prescribed individually for each vertex which of these applies). We define the parameter $s(G)$ to be the number of solvable instances out of $4^n$ possibilities and study the properties of this parameter. Upper and lower bounds for general graphs and trees are given as well as a recurrence formula for rooted trees. Furthermore, we give explicit formulas in several special cases and investigate random graphs.

A key issue for high integration circuit design in the semiconductor industry are power constraints that stem from the eed for heat removal and reliability or battery lifetime limitations. As the power consumption depends heavily on the capacitances between adjacent wires, determining the optimal ordering and spacing of parallel wires is an mportant issue in the design of low power chips. As it turns out, optimal wire spacing is a convex optimization problem while the combined optimal wire spacing and ordering is a special class of the minimal Hamilton-path problem. While the latter is NP-hard in general, the present paper provides an $O{N \log N}$ algorithm that solves the underlying coupled ordering and spacing problem for $N$ parallel wires to optimality. Joint work with Michael Ritter and Paul Zuber

We study the class of mixed-integer sets defined by a totally unimodular constraint matrix with at most two nonzero entries per row. We present a technique to construct an extended formulation for any set $M$ in the family, and we give sufficient conditions for the formulation to be compact. Our technique is based on the explicit enumeration of all possible fractional parts that the continuous variables take over the set of vertices of the convex hull of $M$. We also illustrate practical applications of our results. (Joint work with M. Conforti, F. Eisenbrand and L.A. Wolsey.)

(joint with Fabio Tardella, Frieda Granot, and Maurice Queyranne) We consider the min cut problem when capacities depend on a parameter $\lam$. There are some classes of this parametric min cut problem that are known to have the nice structural property that min cuts are nested in $\lam$, and the nice algorithmic property that all min cuts can be computed in the same asymptotic time as one call to Push-Relabel. We extend these results in several directions: we find three much more general classes of problems for which these two nice properties continue to hold, and we extend other results with the same flavor as well.

For each major airport, a new long-term flight schedule is created every six months using a lengthy process and a lot of manual work. A flight schedule is subject to a set of regulations, the most important being bounds on the number of flights within certain overlapping time windows. The structure of these time windows leads to flight schedules that, although not optimal, cannot accomodate additional flights. In the talk, we present a MIP model for the flight scheduling problem that takes into account all relevevant regulations and demands of the airlines and use a Branch-and-Bound approach to obtain optimal flight schedules. Based on the model, we will also investigate the combinatorics of the rules governing a flight schedule to answer the question why suboptimal flight schedules frequently occur in practice and how the regulations could be modified to obtain better and more robust solutions. (joint work with Andreas Brieden and Peter Gritzmann)

We consider a complex nurse scheduling problem where a set of more than ten different and overlapping shifts are available, some of them with breaks. Their start and end times do not coincide with given periods of different demand. Beside the legal and contractual constraints on a feasible schedule the individual preferences of different nurses have a high priority. In particular, a block structure of working days and days off is highly desirable. Two solution procedures are compared: The first one considers the days of the planning horizon iteratively and computes locally optimal daily schedules by solving assignment problems. The second approach models the block structure by a multi-commodity flow problem and solves a simplified model to optimality with CPLEX 11. Neglected constraints are fulfilled by postprocessing. Tests on real-world instances show that the ILP based solutions are highly satisfactory and dominate the solutions generated by the assignment based algorithm.