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


    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. Presentation slides
    available at
  • 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
    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

    Joint work with P. Belotti and R. Hauser.