# Reception and poster session

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

Lind 409

**Locomotives and rail cars: Switching, routing, and scheduling**

Marco Luebbecke (TU Berlin)

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.**Optimizing over the split closure - Modeling and theoretical analysis**

Anureet Saxena (Carnegie-Mellon University)

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 cutting algorithm for the minimum sum-of-squared error**

clustering

Yu Xia (The Institute of Statistical Mathematics)

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**Rounding heuristics and ramp-up procedures for parallel MIP**

Jonathan Eckstein (Rutgers, The State University Of New Jersey )

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.**Branch-and-Price-and-Cut on Clique Partition Problem with Minimum Clique Size Requirement**

Xiaoyun Ji (Rensselaer Polytechnic Institute)

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.**Branching on general disjunctions**

Miroslav Karamanov (Carnegie-Mellon University)

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.**Finding the nearest point in a polytope according to any metric**

Joao Luis Cardoso Soares (University of Coimbra)

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.**Randomized relaxation methods for the Maximum**

Feasible Subsystem problem

Edoardo Amaldi (Politecnico di Milano)

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.