Mixed integer programming and local search have experienced only a few chance meetings over the past 20 years, despite a clear overlap in the problem classes to which they are applied. This situation has changed recently, with notions from local search being successfully applied in the solution of a fairly broad class of MIP models. This talk will consider several approaches to integrating the technologies, presenting computational results for these approaches on a set of practical problems.

Conflict analysis for infeasible subproblems is one of the key ingredients in modern SAT solvers to cope with large real-world instances. In contrast, it is common practice for today's mixed integer programming solvers to just discard infeasible subproblems and the information they reveal.

In this talk we try to remedy this situation by generalizing SAT infeasibility analysis to mixed integer programming. We present heuristics for branch-and-cut solvers to generate valid inequalities from the current infeasible subproblem and the associated branching information. SAT techniques can then be used to strengthen the resulting cuts. We performed computational experiments which show the potential of our method: On feasible MIP instances, the number of required branching nodes was reduced by 50% in the geometric mean. However, the total solving time increased by 20%. On infeasible MIPs arising in the context of chip verification, the number of nodes was reduced by 90%,thereby reducing the solving time by 60%.

In the MaxFS problem, given an infeasible linear system Ax>=b, one wishes to find a feasible subsystem containing a maximum number of inequalities. This NP-hard problem has interesting applications in a variety of fields. In some challenging applications in telecommunications and computational biology one faces very large MaxFS instances with up to millions of inequalities in thousands of variables. We propose to tackle large-scale instances of MaxFS using randomized and thermal variants of the classical relaxation method for solving systems of linear inequalities. We establish lower bounds on the probability that these methods identify an optimal solution within a given number of iterations. These bounds, which are expressed as a function of a condition number of the input data, imply that with probability 1 these randomized methods identify an optimal solution after finitely many iterations. Computational results obtained for medium- to large-scale instances arising in the design of linear classifiers, in the planning of digital video broadcasts and in the modelling of the energy functions driving protein folding, indicate that an efficient implementation of such a method perform very well in practice.

Joint work with P. Belotti and R. Hauser.

Joint work with Yves Pochet.

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 a recent joint paper with Michael Perregaard a precise correspondence was established between lift-and-project cuts for mixed 0-1 programs, simple disjunctive cuts (intersection cuts) and mixed-integer Gomory cuts. The correspondence maps members of one family onto members of the others. It also establishes a many-to-one mapping between bases of the higher-dimensional cut generating linear program (CGLP) and bases of the linear programming relaxation of the given mixed integer program. As a result, an algorithm is developed that solves (CGLP) without explicitly constructing it, by mimicking the pivoting steps of the higher dimensional (CGLP) simplex tableau by certain pivoting steps in the lower dimensional LP simplex tableau. Due to the smaller problem size and the vastly reduced number of pivots needed by the new algorithm, it finds a deepest lift-and-project cut typically in a fraction of the time needed by the original (CGLP)-based algorithm.

The new cut generating procedure can also be interpreted as an algorithm for systematically strengthening mixed integer Gomory (MIG) cuts. Starting with a MIG cut from a given source row k of the optimal LP simplex tableau, a certain sequence of pivots is performed, each of which results in a new simplex tableau, generally neither primal nor dual feasible, such that the MIG cut from the same source row k is guaranteed to be stronger (in terms of the amount by which it cuts off the LP optimum) then the previous MIG cut. In other words, if S is the set of all bases (feasible or not) of the LP relaxation, this procedure finds a member B of S such that the MIG cut from row k of the simplex tableau associated with B is strongest over all bases in S.

After extensive computational testing, the new procedure has been incorporated in the MIP module of the commercial code XPRESS, where it serves as the default cut generating routine.

1. Funding issues Is IP research still fundable? Differences between US and Europe 2. Raising IP's profile Does the profile need to be raised? If so, how? New application areas? 3. Cultivating a research community How to increase collaboration Differences between US and Europe 4. IP research directions--What are "the next big ideas?" 5. IP education 6. The next conference? Does this conference have its own niche? (IPCO/MPS/etc.) When? Where?

During the past decade several major power blackouts affected North America, Europe and South America. It is quite likely (in fact, expected) that more serious events will take place in the future, with potentially very damaging consequences to economies and public health. Rather than being the result of particular economic or operational factors, the blackouts can be seen as caused by the inherent complexity entailed by modern transmission networks, which comprise thousands of nodes and links and span very large geographical areas.

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).

In this talk we discuss the polyhedral structure of the convex hull of the integer single node flow set with two possible values for the upper bounds on the arc flows. These mixed integer sets may arise as substructure of more complex mixed integer sets that model the feasible solutions of real application problems such as network design, location and lotsizing. We give a complete description of this special integer single node flow polyhedron based on the generalization of the description of the integer single node flow polyhedron with two arcs. All the coefficients of the facet-defining inequalities can be computed in polynomial time adapting a known algorithm from Hirschberg and Wong (1976) for the two integer knapsack problem. We report on computational experience.

Joint work with Agostinho Agra.

This poster describes a heuristic method for mixed integer programming (MIP), and its incorporation into PICO, a highly parallel branch-and-bound MIP solver. The heuristic performs pivot-based rounding with the help of a concave integrality merit function. The surrounding branch-and-bound environment begins with a synchronous "ramp-up" phase, and then transitions to asynchronous tree-parallel search. During ramp-up, there are several ways of inducing parallelism: using multiple alternative merit functions, and partitioning the search space by prospective branching. I discuss how to combine these two approaches and how to prospectively branch on multiple layers of variables, along with implementation and computational results for the PICO MIP solver.

Edmonds showed in 1965 that the convex hull of all matchings of a graph can be obtained by applying one round of Gomory-Chv'atal cutting planes to the fractional matching polytope. More precisely, he showed that this convex hull can be described by non-negativity, degree and odd-set constraints.

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 first part of the talk, we use facets of simple mixed-integer sets with three variables to derive a parametric family of valid inequalities for general mixed-integer sets. We call these inequalities "two-step MIR inequalities" as they can be derived by applying the simple mixed-integer rounding (MIR) principle of Wolsey (1998) twice.

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.

Given a complete graph G=(V,E) with edge weight on each edge, we consider the problem of partitioning the vertices of graph G into subcliques that have at least S vertices, so as to minimize the total weight of the edges that have both endpoints in the same subclique. In this poster, we consider using branch-and-price method to solve the problem. We demonstrated the necessity of cutting planes for this problem and suggested effective ways of adding cutting planes in the branch-and-price framework. The NP hard pricing problem is solved as an integer programming problem. We present some preliminary computational results on large randomly generated problems.

Joint work with Gerard Cornuejols.

This paper considers a modification of the branch-and-cut algorithm for Mixed Integer Linear Programming problems where branching is performed on general disjunctions rather than on variables. We introduce a procedure for selecting promising disjunctions based on a heuristic measure of disjunction quality. This measure exploits the relation between branching disjunctions and intersection cuts. In this work, we focus on disjunctions defining mixed integer Gomory cuts. The procedure is tested on instances from the literature. Experiments show that the proposed procedure is more efficient than branching on variables for a majority of the instances. The metrics we consider are solution time and tree size for the instances that could be solved to optimality within a given time limit, and integrality gap closed for the remaining instances.

We consider the general integer program P: max {c'x : Ax=b; x nonnegative integer} which has a well-known abstract dual optimization problem stated in terms of superadditive functions. Using a linear program equivalent to P, introduced recently, we show that its dual can be interpreted as a simplified and more tractable form of the abstract dual, and identifies a subclass of superadditive functions, sufficient to consider in the abstract dual. This class of superadditive functions is also used to characterize the integer hull of the convex polytope {x : Ax=b; x nonnegative}.

In recent years a lot of work has been devoted to general-purpose methods for finding good heuristic solutions to Integer and Mixed Integer Linear Programs (MIPs). Some of these methods are now successfully integrated in commercial and non commercial MIP solvers. We review these results, compare some of the techniques, discuss advantages and drawbacks and we try to give a flavor of what has still to be done in the area.

Industrial switching involves moving materials on rail cars within or between industrial complexes and connecting with other rail carriers. Planning tasks include the making up of trains with a minimum shunting effort, the feasible and timely routing through an in-plant rail network on short paths, and assigning and scheduling of locomotives under safety and network capacity aspects. A human planner must often resort to routine and simple heuristics, not least for the reason of unavailability of computer aided suggestions. In this project we propose mixed integer programming models to capture the whole process at once in order to obtain optimal or provably good solutions. Column generation allows us to work with linear programming relaxations with a huge number of variables. This popular technique has almost attained an industry standard level and usually enables one to set up appropriate models quickly. The challenge hides in the actual implementation which still needs tailoring to the particular application. Our work is based on practical data from a German in-plant railroad.

This talk is an overview of techniques used to handle problems with symmetries. For problems modeled as integer linear programs (ILP), three essentially different and mutually exclusive approaches have been used: Reformulations, symmetry-breaking inequalities, and isomorphism pruning.

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 present a restructuring of the computations in Lenstra's methods for solving mixed integer linear programs. A concept of Adjoint lattices is introduced and used for this purpose. This allows us to develop branching on hyperplane algorithms in the space of original variables, without requiring any dimension reduction for pure or mixed integer programs. Reduced lattice basis are also computed in the space of original variables. Based on these results we give a new natural heuristic way of generating branching hyperplanes, and discuss its relationship with recent reformulation techniques of Aardal and Lenstra. We show that the reduced basis available at the root node has useful information on the branching hyperplanes for the generalized branch-and-bound tree. Our development allows us to give algorithms for mixed convex integer programs with properties similar to those for the mixed integer linear programs. Implementation of this algorithm in a prototype software system "IMPACT" is described. Computational results are presented on difficult knapsack and market split problems using this approach.

We propose a very simple preconditioning method for integer programming feasibility problems: applying basis reduction to the constraint matrix, to make its columns shorter in euclidean norm, and more orthogonal. Our approach -- termed column basis reduction, and abbreviated as CBR -- simplifies and generalizes the reformulation technique proposed for equality constrained IPs by Aardal, Hurkens, Lenstra and others.

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.

Several disjunctive cuts for mixed integer programs are (directly or indirectly) based on imposing a simple disjunction where a single fractional variable is required to be rounded either up or down to its nearest integer value. Two well-known cut families based on such a disjunction is Gomory's mixed integer cut and the lift-and-project cuts from the 1990s. Both cut classes involves strengthening by considering the integrality of other variables. This strengthening can be interpreted as a modification of the underlying simple disjunction. Later research into disjunctive cuts have taken this idea of strengthening the underlying disjunction even further.

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.

National Statistical Agencies needs automatic tools for detecting errors in records not satisfying a set of consistency rules. The topic is known as Statistical Data Editing, and a very interesting Optimization Problem is the so-called Error Localization Problem. It concerns finding the minimum number of fields in an invalid record such that by modifying these values the new record satisfies all the rules. It is an NP-hard problem because the "Minimum Weight Solution to Linear Equations" is a particular case. Also the Error Localization Problem is very important in Signal Processing (the problem is then called "Basis Selection Problem"),

where information must be encoded and sent, or received and decoded, through a Telecommunication Network.

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.

Almost 3,000 businesses in the United States provide on-demand air charter services. The on-demand air charter industry provides a vital transportation link for medical services, important cargo needed to promote commerce, and personal travel supporting the growth of the economy. The companies use smaller aircraft to meet the customized needs of the traveling public for greater flexibility in scheduling and access to almost every airport in the country. Flights are planned according to the customer's schedule, not the operator's.

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.

The polyhedron defined by all the split cuts obtainable directly (i.e. without iterated cut generation) from the LP-relaxation of a mixed integer program (MIP) is termed the split closure of the MIP. This paper deals with the problem of optimizing over the split closure. By the equivalence of optimization and separation, we can restrict our attention to the following separation problem: given a fractional point, say x, find a split cut violated by x or show that none exists. We show that this separation problem can be formulated as a parametric mixed integer linear program (PMILP) with a single parameter in the objective function and the right hand side. We discuss a branch and bound algorithm for PMILP, based on solving a parametric linear program at every node of the search tree, while using warm-start basis information. Further, we recast the PMILP as the problem of minimizing a function that is the infimum of a family of convex functions. As a result, for several sub-classes of split cuts, the PMILP can be deparameterized. Implementation and experimentation is under way.

A terminating algorithm is developed for the problem of finding the point of smallest norm in the convex hull of a given finite point set in a finite dimensional space. The proposed algorithm mimics Ph. Wolfe's algorithm (Wolfe'76) developed for the Euclidean norm and shares all of its basic properties. The proposed algorithm has great potential as a numerical mechanism to generating consecutive deepest disjunctive cuts in integer programming.

We propose a new formulation for the capacitated minimum spanning tree problem that leads to a robust branch-and- cut-and-price algorithm. The formulation allows the use of cuts expressed over a very large set of variables, without changing the pricing subproblem or increasing the size of LPs that are actually solved. Cuts over those variables can be quite strong, and generalize many previous know families of cuts, including capacity, root cutsets and multistars. Computation results on benchmark instances from the OR-Library show very significant improvements over previously known algorithms, specially on non-unitary weight instances.

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

In Branch-and-Price algorithms, implementing the branching scheme can be challenging. Branching constraints may imply modifications to the pricing problem. This is a main concern for the development of a generic branch-and-price code that should run using only the pricing oracle provided by the user. The issue has not stop people from using Branch-and-Price. Firstly, branching is straightforward for many applications (we shall characterize the class of problem for which this is the case). Then, Ryan and Foster (1981) proposed a scheme for applications that can be reformulated as a set covering problem. Beyond that, a general scheme was presented by Vanderbeck (2000) but it may result in significant modifications to the pricing problem. An alternative is the scheme of Villeneuve et al. (2003) that consists in applying branching in the original formulation, but this introduces symmetry in the Dantzig-Wolfe reformulation when the problem structure involves several identical blocks. The branching scheme presented here builds on the aboves. It can be can be implemented using only the oracle provided for the original pricing problem. Branching constraints are not dualized in a Lagrangian way but are convexified in the subproblem.

This talk deals with mixed integer optimization problems defined by linear constraints and a polynomial function as the objective function. We present motivating examples, illustrate techniques that reduce the problem to a mixed integer linear program and discuss complexity results. An algorithm is prersented that is based on Barvinok's rational function theory, i.e., lattice points in polyhedra are encoded through rational functions. It turns out that under the assumption that the number of variables is fixed, our algorithm leads to a fully polynomial time approximation scheme. The results of this talk are based on joint work with Raymond Hemmecke, Matthias Koeppe and Jesus De Loera.

Very little is known about the polyhedral structure of even simple mixed integer programs. Here we study a very simple set, called the mixing set. This set and valid inequalities for it were proposed by Gunluk and Pochet in an effort to explain and understand why the same procedure of "mixing mixed integer rounding (MIR) inequalities" gave valid inequalities for many different variants of the constant capacity lot-sizing problem, and subsequently Miller and Wolsey took this abstraction a little further by considering the intersection of mixing sets plus certain additional constraints.

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 di Summa.

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

We give necessary and sufficient conditions for the local optimal solutions of the minimum sum-of-squares clustering problem and its continuous relaxation. Especially, we show that the objective function of the mixed integer program is concave and each local solution of its continuous relaxation is integer. We then adapt Tuy's concavity cuts to the continuous relaxation to search for a global optimal solution of the clustering problem. Numerical results show that our algorithm general gives a better solution than the popular k-means method starting from the same point without increasing computation time too much. (In the proceedings of the 5th SIAM international conference on data mining. http://optlab.mcmaster.ca/~xiay/papers/ssqeproced.pdf Presentation slides available at http://optlab.mcmater.ca/~xiay/papers/ssqeslides.pdf

Given a set of continuous variables and for each variable a constant, a cardinality constraint requires that no less than a specified number of variables is equal to their corresponding constants. Cardinality constraints appear in several applications, such as feature selection in data mining. I will present a polyhedral study of problems with cardinality constraints and a branch-and-cut approach to solve them. In particular, I will present a few unusual properties of these polyhedra.

Joint work with Ming Zhao.

For the solution of hard integer programs with branch-and-cut algorithms it is a necessity to check during the separation phase for violated inequalities of the stable set relaxation of the instances conflict graph. These conflict graphs turn out to be sparse. For instance the majority (39/60) of the new and difficult MIPLIB2003 integer programs contain large substructures with constraints of type x_i 1 for binary variables.

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.