COIN-OR and Open-Source Events
18th International Symposium on Mathematical Programming
ISMP 2003


Presentations, workshops, and user-group meetings on open source software.


COIN-OR Users Group Meeting: Weds Aug 20, 12:00 - 13:00, Building 101, Room Grupperegnings-lokale 1 (first floor)

Coordinator: Robin Lougee-Heimer, IBM Research
Food: Bring your ISMP-provided bag lunch
Agenda:
  • Status reports from project leads
  • Demo of connecting AMPL to CPL using OSI by Leo Lopes
  • Incorporation status from Matthew Saltzman
  • Open Q & A
To propose a discussion item, send a posting to the coin-discuss mailing list available at http://www.coin-or.org.


Workshop: Weds Aug 20, 09:00 - 10:30, Room 306/35

Title:  COIN-OR: Software Tools for Implementing Custom Solvers
Lead: Ted Ralphs, Lehigh University
Co-authors: Laszlo Ladanyi, IBM Research
Matthew Saltzman, Clemson University
Abstract: Branch, cut and price is a proven, effective technique for solving difficult, large-scale discrete optimization problems. Implementing such algorithms is difficult due to the complexity of dynamic generation of both variables and constraints. This workshop is aimed towards practitioners and researchers in need of more powerful solution techniques than current commercial software can provide. We will describe how to use the tools available in the COIN-OR repository (www.coin-or.org) to implement a state-of-the-art, parallel BCP algorithm.

Sessions: All talks in a session are listed. To facilitate session hopping, the non-open-source talks arelisted in grey without abstracts.


Session 38: Monday 16:30 - 18:00, Room 306/35


Title: Recent Developments in Filter Methods II
Chair: Luís N. Vicente
Abstracts
  • Title: On the superlinear local convergence of a filter-SQP method
    Lead: Stefan Ulbrich
    Abstract:

  • Title: An interior-point filter line-search method for large-scale nonlinear programming
    Lead: Andreas Waechter, IBM Research
    Co-author: Lorenz Biegler, Carnegie-Mellon University
    Abstract 854: Recent improvements of a barrier method for large-scale continuous nonlinear nonconvex optimization will be presented. The algorithm computes search directions from a linearization of the primal-dual equations, and global convergence is guaranteed by a filter line-search procedure. Some details of the implementation, particularly of a new feasibility restoration phase, will be discussed. Numerical results on a large set of test problems, as well as real-life applications (such as tuning of transistors in integrated digital circuits) with problem sizes with up to several hundred thousand variables, will be presented. The code is released as open source under the name IPOPT at www.coin-or.org.

  • Title: On the convergence of a filter algorithm with independent feasibility and optimality phases
    Lead: Elizabeth Karas
    Abstract: 

Session 66: Weds 13:15 - 14:45, Room 302/49


Title: Decomposition algorithms and dynamic cut generation
Chair: Ted Ralphs, Lehigh University
Abstracts
  • Title: Decomposition and Dynamic Cut Generation in Integer Programming
    Lead: Matthew Galati,Lehigh University
    Co-author: Ted Ralphs, Lehigh University
    Abstract 528: Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to develop bounds for integer programming problems. We draw connections between these classical approaches and techniques based on generating strong valid inequalities. We also discuss several methods for integrating dynamic cut generation with decomposition and present a decomposition-based separation algorithm called decompose and cut. The algorithm takes advantage of the fact that separation of an integer solution is often much easier than separation of an arbitrary fractional solution.

  • Title: Optimal Rectangular Partitions
    Lead: Abilio Lucena
    Co-author: Felipe Calheiros, Cid C. de Souza
    Abstract:

  • Title: Solving lexicographic multiobjective MIPs with Branch-Cut-Price
    Lead: Laszlo Ladanyi, IBM Research
    Co-authors: Marta Eso, David L. Jensen
    Abstract: In this talk we will first describe an application, the FCC Auction 31, and its two formulation: one with a compact representation solvable via branch-and-cut, and one with column generation using branch-and-price. We will show how the second formulation can be interpreted as a Dantzig-Wolfe decomposition and that this interpretation leads to a branch-cut-price algorithm. Then we will demonstrate how to apply the same principle to a general Mixed Integer Programming problem. Finally, we extend the applicability of linear complementarity to integer programming to solve problems with multiple (lexicographic) objective.

Session 154: Thursday Aug 21, 13:15 - 14:45, Room 306/31


Title: Open-Source Software for Mathematical Programming
Chair: Robin Lougee-Heimer, IBM Research
Abstracts
  • Title: The COIN-OR Initative: open-source tools for mathematical programmers
    Lead: Robin Lougee-Heimer, IBM Research
    Abstract: Much of the mathematical programming research and application relies on software. And yet, there is relative low number of reference implementations, common interfaces, re-usable frameworks, and open standards for the specific software needs of the mathematical programming community. Open source is an alternative style of software development with some attractive benefits. Three years ago at ISMP 2000, the COIN-OR project was launched as an experiment with the mission of promoting open-source software for the mathematical programming community. In this talk, we report on the progress of COIN-OR and its future direction. We will announce the winners of the COIN-OR Open Source Coding Contest. The contest was a joint effort of INFORMS, MPS, and COIN-OR with prizes donated by IBM.

  • Title: The COIN-OR Open Solver Interface: A Progress Report
    Lead: Matthew Saltzman, Clemson University
    Abstract: When the COIN-OR project debuted at ISMP 2000, a key component of the project was the Open Solver Interface (OSI). The OSI is intended to be a common application program interface (API) for calling any of a variety of embedded solvers in an algorithm. The current version includes support for CPLEX, XPRESS-MP, Soplex, the GNU LP Kit, Hafer's DyLP, and COIN-OR native solvers CLP (the COIN-OR LP solver), SBB (Simple Branch and Bound), and Vol (an implementation of Barahona and Anbil's volume algorithm). A user can write a single implementation of an algorithm calling any of these solvers through the same interface. This presentation describes features of the OSI and an outline of the design of a new version of the OSI (under development). The new design will improve flexibility and efficiency and simplify the process of embedding new solvers. It will offer a consistent (solver-independent) problem representation and access to a broad set of solver capabilities through an efficient, open, standard, portable API.

  • Title: Prox-Accpm: A Cutting Plane Solver for Convex Optimization
    Lead: Claude Martin Tadonki, University of Geneva
    Co-authors: Jean-Philippe Vial , Frédéric Babonneau , Cesar Beltran , Olivier du Merle Abstract: {\em Prox-Accpm} is an extension of the analytic center cutting plane method to solve general (nondifferentiable) convex optimization problems, whose components (objective and constraints) are described by first order oracles. The addition of a proximal term allows a better control of the algorithm behavior. Prox-Accpm applies to problems arising from decomposition approaches (Benders, Lagrangian, Column generation) or to equilibrium problems, or to cutting plane approaches to difficult mathematical programming problems (e.g., some SDP's). In view of the wide range of applications, Prox-Accpm is conceived as a parametizable solver. It is written in {\sc matlab}, but some routines are written in {\sc C}. All developments are tested against families of benchmark problems: Column generation (cutting stock, linear separation in data mining), Lagrangian relaxations (p-median, unit commitment, nonlinear multi-commodity flow), equilibria (two-person games, traffic equilibria), nonlinear convex problems (optimization on positive polynomials, quadratically constrained problems) etc. Prox-Accpm can be used as a standalone binary version to be included in any standard program for user-specific purposes.


To update the information on this page, send a note.