[Coin-announce] COIN-OR Events at ISMP 2003

[Matthew Saltzman]

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

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


COIN-OR Users Group Meeting: Weds Aug 20, 12:00 - 13:00, Room TBA

	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 are listed without abstracts.

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

Title: Recent Developments in Filter Methods II
Chair: Lus 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
      Co-authors: Lazlo Ladanyi, Ted Ralphs
      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, Frederic 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.

-- 
		Matthew Saltzman

Clemson University Math Sciences
mjs at clemson.edu
http://www.math.clemson.edu/~mjs