Main navigation | Main content

HOME » SCIENTIFIC RESOURCES » Volumes

Abstracts and Talk Materials

July 28, 2005 2:45 pm - 3:30 pm

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.

July 28, 2005 4:45 pm - 5:30 pm

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

July 25, 2005 4:00 pm - 5:00 pm

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 P. Belotti and R. Hauser.

July 28, 2005 9:30 am - 10:15 am

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.

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.

July 25, 2005 10:30 am - 11:15 am

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.

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.

http://web.mit.edu/dbertsim/www/

http://www.lancs.ac.uk/staff/letchfoa/

http://www.ifor.math.ethz.ch/staff/weismant

July 26, 2005 4:00 pm - 5:00 pm

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?

July 27, 2005 2:00 pm - 2:45 pm

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

July 25, 2005 11:15 am - 12:00 pm

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.

Joint work with Agostinho Agra.

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.

Joint work with Ming Zhao.

July 26, 2005 9:30 am - 10:15 am

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|^{2}|E|+|V|^{3}log |V|)
separation
algorithm
for the nonsimple 1-wheel inequalities
(Cheng and Cunningham, 1995), which is faster than the
previously known
O(|V|^{4}) algorithm. In particular this is faster
for
the sparse instances coming from the conflict graphs of
general
integer programs.

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|

July 25, 2005 4:00 pm - 5:00 pm

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.

July 26, 2005 10:15 am - 11:00 am

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.

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.

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.

July 25, 2005 4:00 pm - 5:00 pm

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.

July 25, 2005 4:00 pm - 5:00 pm

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.

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.

July 29, 2005 10:45 am - 11:30 am

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

July 28, 2005 2:00 pm - 2:45 pm

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.

July 25, 2005 4:00 pm - 5:00 pm

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.

July 27, 2005 9:30 am - 10:15 am

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.

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.

July 29, 2005 9:00 am - 8:45 pm

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.

July 28, 2005 4:00 pm - 4:45 pm

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.

We describe a family of IP instances, called

A subclass of decomposable knapsack problems is called

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.

July 28, 2005 10:15 am - 11:00 am

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.

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.

July 27, 2005 2:45 pm - 3:30 pm

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.

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.

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.

July 25, 2005 4:00 pm - 5:00 pm

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.

July 25, 2005 4:00 pm - 5:00 pm

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.

July 27, 2005 4:00 pm - 4:45 pm

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.

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

July 25, 2005 3:15 pm - 4:00 pm

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.

http://www.ifor.math.ethz.ch/staff/weismant

July 29, 2005 9:45 am - 10:30 am

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.

July 26, 2005 2:45 pm - 3:30 pm

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

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

July 25, 2005 4:00 pm - 5:00 pm

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