We 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 a coefficient in the formulation that can be strengthened. 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 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 a large number of cutting planes (in terms of amount of integrality gap closed). For instance, on one MIPLIB instance, all of the integrality gap is closed by strengthening the coefficients in the initial formulation while optimizing over the first Chvatal closure only closes 61% of the integrality gap. We also solve another "hard" instance to optimality by strengthening coefficients in every round of a cutting plane algorithm based on mixed integer Gomory cuts and split cuts. The same cutting plane algorithm was unable to solve this instance without including the strengthening step. The instance was only recently solved with an approach based on the first Chvatal closure.

We finish by demonstrating how coefficient strengthening can be used to design a model for a production scheduling 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 strengthened coefficient. The result is a new understanding of how to build a tight formulation of the problem. We believe this suggests that it might be of interest to construct a tool for strengthening coefficients.

In this talk we will describe ongoing work on solving a number of optimization models related to the design, maintenance and operation of electrical power transmission networks. This is joint work with Sara Mattia (Rome).

15 years later, Minty and Sbihi showed that a maximum-cardinality stable set in a claw-free graph can be computed in polynomial time, thereby generalizing Edmonds' algorithm for maximum cardinality matching. Since then, it is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs.

In this talk we show that the convex hull of stable sets of quasi-line graphs is obtainable by applying one round of split cuts. The class of quasi-line 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. The necessary split-cuts are a generalization of Edmonds' odd-set inequalities, called clique family inequalities.

Joint work with G. Oriolo, P. Ventura and G. Stauffer.

In the second part, we study the shooting experiment of Gomory which computationally identifies "important" facets of the cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We present computational results that suggest that MIR and two-step MIR inequalities are important.

In the last part of the talk, we present computational experience with general mixed-integer programs. Joint work with Sanjeeb Dash at IBM Research.

Reformulation is mostly used to handle problems where the symmetries come from the set of all permutations of a set of objects, inducing a permutation group on the variables. Some (or most) symmetries are removed from the formulations and additional branching strategies become available. The price to pay is that the reformulation has an exponential number of variables that must be handled by column generation techniques.

Adding symmetry breaking inequalities is probably the most natural way to try to handle symmetries. Several papers report strong improvements when using the best possible symmetry breaking set of inequalities. Methods for deriving such sets have been devised, but little is known about finding the most efficient set.

Isomorphism pruning is based on the theory of isomorphism-free backtracking procedure for enumeration problems. When coupled with a Branch-and-Cut algorithm, additional options for generating isomorphism-related cuts and setting variables are available. Improvements of several orders of magnitude for running time and enumeration tree size have been observed on highly symmetric 0-1 problems. Extensions of the techniques to ILP with variables bounded to a small set and to ILP corresponding to coloring problems are also available.

We describe a family of IP instances, called decomposable knapsack problems, that generalize the ones proposed by Jeroslow, Chvatal and Todd, Avis, Aardal and Lenstra, and Wolsey. We prove that 1) they need an exponential number of nodes to solve, when branch-and-bound branching on individual variables is applied; 2) after the application of column basis reduction, a constant number of nodes suffice.

A subclass of decomposable knapsack problems is called cascade problems. They were created to illustrate the surprising fact, that in hard IPs a "thin" direction is sometimes not the best to branch on. Besides having this structure, the cascade problems —despite having only one dense constraint—are as difficult for commercial MIP solvers, as the well-known marketshare problems.

Our computational study shows that most difficult IPs recently used to test nontraditional IP algorithms—subset sum, strongly correlated knapsack problems, the marketshare problems, and our cascade problems—become easy for a commercial IP solver after our preconditioning is applied. Joint work with Bala Krishnamoorthy at Washington State University.

The most common method for solving a mixed integer program is by branch-and-bound. Almost all such available codes branch on a single variable at a time. For general mixed integer programs, where the integer variables are allowed a wider range than simple 0-1 variables, such a simple branching scheme can often lead to an explosion in the number of nodes the code has to search. In this talk I examine the feasibility of applying the ideas for strengthening cuts to the simple branching disjunctions for the purpose of creating better mixed integer branches. Results from computational tests on a variety of public benchmark problems, using an implementation based on the Xpress-MP solver, will be used to demonstrate the effects of such strengthened branches.

We present an exact method, based on a Benders' decomposition approach, solving instances with up to 100 fields and 40 edits. We also produce a variant of this approach to solve heuristically larger instances. Some procedures of this descending search make use of the Farkas' Lemma in Linear Programming. Computational experience on randomly generated instances shows that the approach can deal with instances of up to 1000 fields and 400 edits.

The generality of the consistency rules makes the Error Localization Problem very close to a general Mixed Integer Programming. Still, there is some structure. Therefore, we will open a discussion to the audience on how new results in Mixed Integer Programming could help solving Error Localization Problems, and viceversa!

This is part of a joint research work with Jorge Riera-Ledesma, University of La Laguna, Tenerife, Spain.

DayJet Inc. is a startup company in this space that will soon provide air taxi services. There are obvious advantages to an air taxi system. More than 1.5 million people board commercial airliners each day. Most fly with hundreds of other passengers to and from a limited number of major "hub" airports that are heavily congested and often located many miles from their homes and final destinations. Missed connections and flight delays add to their frustrations. An air-taxi system gives travelers the option of using small jets that fly to and from less-congested outlying airports, without packed parking lots, long lines at security checkpoints, flight delays, and lost luggage, that are closer to where they live and where they want to go. While commercial flight service now exists at only about 550 airports in the United States, air taxis will be able to land at 5,000 of the nation's 14,000 public and private runways. And all that at comparable fares.

A key challenge in setting up an air taxi system is the development of a scheduling engine that takes requests for transportation and schedules planes and pilots in a cost effective way to satisfy these requests. The dial-a-flight problem captures the essential characteristics of the scheduling problems encountered by an air taxi service.

The dial-a-flight problem is concerned with the scheduling of a set of passenger reservations for air transportation during a single day. A reservation specifies an origin airport, an earliest acceptable departure time at the origin, a destination airport, and a latest acceptable arrival time at the destination. A fleet of airplanes operable by a single pilot is available to provide the requested air transportation. Each airplane has a home base, is available for a certain period during the day, and returns home at the end of the day. A set of pilots, stationed at the home bases of the airplanes, is available to fly the airplanes. A pilot departs from the home base where he is domiciled at the start of his duty and returns to the home base where he is domiciled at the end of his duty. A pilot schedule has to satisfy FAA regulations governing flying hours and duty period, i.e., a single pilot cannot fly more than 8 hours in a day and his duty period cannot be more than 14 hours. To ensure acceptable service a passenger itinerary will involve at most two flights, i.e., a single intermediate stop is allowed. A turnaround time at an airport, i.e., the minimum time between an arrival at an airport and the next departure, is given. The objective is to minimize the costs, while satisfying all requests. A dispatcher has to decide which planes and pilots to use to satisfy the reservations and what the plane and pilots itineraries will be, i.e., the flight legs and associated departure times.

We present a variety of optimization approaches for the solution of the dial-a-flight problem.

In our time-discretized integer multicommodity network flow model, the key events from the perspective an airplane are modeled, e.g., arrival at an airport, dropping off passengers at the airport, preparing for the next flight (which one depends on whether there were "indirect" passengers on board), loading new direct flight passengers, and loading new indirect flight passengers. To keep the size of the model within acceptable limits a flexible concept of time-discretization has been designed and implemented. Each airplane has its own time-discretization and the number of time instants as well as their values are completely flexible. This flexibility is crucial, because we extensively employ dominance relations between itineraries to reduce the network size. In our column generation formulation, reservations are represented by rows and plane itineraries are represented by columns. The multicommodity flow model is modified to solve the pricing problem. A customer constrained shortest path algorithm is developed for its solution. Specialized branching schemes are employed in a branch-and-price approach to identify high quality schedules.

Joint work with... Mo Bazaraa, Daniel Espinoza, Renan Garcia, Marcos Goycoolea, George Nemhauser : Georgia Tech Emilie Danna and Zonghau Gu : ILOG, Inc. Alex Khmelnitsky and Eugene Taits : DayJet, Inc.

Joint work with D.Andrade, R.Fukasawa, J.Lysgaard and M.Poggi de Aragao.

In this talk we pursue this effort at abstraction by considering two "abstract sets" that are generalizations of the mixing set. We show that, modulo a slight restriction, the convex hulls of both sets are obtained with mixing inequalities. This is joint work with Michele Conforti and Marco Saturni.

Turning back to lot-sizing, we show that a constant capacity problem with production time windows, and surprisingly both a multi-item problem with a joint set-up variable, and a class of single item problems with varying capacities can also be solved by mixing. The latter is joint work with Yves Pochet.

(PDF file with formulations is available).

Joint work with Ming Zhao.

A stable set in a graph G=(V,E) is a set of pairwise nonadjacent vertices. A common approach for finding a maximum weight stable set of G is to optimize over the convex hull STAB(G) of the incidence vectors of stable sets; this approach requires knowledge of strong valid inequalities and algorithms to separate them. We present an O(|V|²|E|+|V|³log |V|) separation algorithm for the nonsimple 1-wheel inequalities (Cheng and Cunningham, 1995), which is faster than the previously known O(|V|⁴) algorithm. In particular this is faster for the sparse instances coming from the conflict graphs of general integer programs.