COIN-OR

COIN-OR Exhibits: Sunday, October 24, 2004, through Tuesday, October 26, 2004

Session: Sunday October 24, 08:00 - 9:30

Abstracts

• Title: An XML-Based Standard Form for Linear Programming Problem Instances
  

  Lead: Kipp Martin, University of Chicago, kipp.martin@gsb.uchicago.edu
  Co-author: Robert Fourer, Northwestern University, 4er@iems.northwestern.edu
  Leo Lopes, Leo Lopes, leo@sie.arizona.edu
  Abstract: One way to encourage modeling language and solver compatibility is to use a standard representation of a problem instance. We present LPFML Schema, a W3C Schema for representing linear programming problem instances in XML. We describe a library of open-source C++ classes that facilitate the exchange of information between modeling languages and solvers. We show how these classes are used to provide previously unavailable modeling language-solver connections.

• Title: Network and Graph Markup Language (NaGML)
  

  Lead: Gordon Bradley, Naval Postgraduate School, gbradley@nps.edu
  Abstract: The Network and Graph Markup Language (NaGML) is a family of xml languages for network and graph data files. The topology, node properties, and arc properties are validated against the user's specification for the data values. NaGML is a part of a component architecture that reads, validates, processes, displays, and writes network and graph data.

• Title: Panel Discussion: Optimization Web Services Panel: Next Steps
  

  Lead: Leo Lopes, Leo Lopes, leo@sie.arizona.edu
  Co-author: Gordon Bradley, Naval Postgraduate School, gbradley@nps.edu
  Obi Ezechukwu, United Kingdom, oce@doc.ic.ac.uk
  Robert Fourer, Northwestern University, 4er@iems.northwestern.edu
  Kipp Martin, University of Chicago, kipp.martin@gsb.uchicago.edu
  Matthew Saltzman, Clemson University, mjs@math.clemson.edu
  Abstract: This panel will briefly summarize progress and new developments since the first discussions on Standards and Web Services at INFORMS Miami Beach 2001. It will then open the floor for discussions about next steps in Standardization and Development, and provide a forum for user feedback.

Discussion: XML Standards for LP Representation: Sunday, October 24, 2004, 11:30 AM

Reception: IOL Welcomes COIN-OR to the INFORMS Server: Sunday, October 24, 2004, 6-7 PM

COIN-OR Users Group Meeting: Monday October 25, 2004, 12:15-1:15 PM

Session: Tuesday October 26, 08:00 - 09:30

Abstracts

• Title: The COIN-OR Foundation, Inc: A nonprofit corporation for OR software resources
  

  Lead: Matthew Saltzman, Clemson University, mjs@math.clemson.edu
  Co-author: Robin Lougee-Heimer, IBM Research, robinlh@us.ibm.com
  Abstract: The COIN-OR Foundation, Inc (est. 2004) is a nonprofit corporation dedicated to the development, maintenance, and distribution of open-source resources for the computational OR community (e.g., data, models, open interfaces, algorithmic frameworks, component libraries). The COIN-OR Foundation builds on the accomplishments of the COIN-OR project (est. 2000), and is hosted by INFORMS at www.coin-or.org. We will present a status report on the COIN-OR resources and describe the new organization.

• Title: Linking GAMS to Solvers using the COIN-OR Open Solver Interface
  

  Lead: Steven Dirkse, GAMS Development Corp., steve@gams.com
  Co-author: Michael Bussieck, GAMS Development Corp, mbussieck@gams.com
  Abstract: The General Algebraic Modeling System (GAMS) is a commercial modeling system for mathematical programming problems. In this talk, we describe our experience developing the GAMS/COIN-OR link. This recently developed link allows GAMS users to connect their customized algorithms to a variety of solvers using one interface the COIN-OR Open Solver Interface (OSI). This work illustrates the potential of open-source software and open standards to speed the deployment of research into practice.

 
• Title: Mixed-Integer Rounding Inequalities for COIN-OR

Lead: Joao Goncalves, Lehigh University, jog7@lehigh.edu
Co-author: Laszlo Ladanyi, IBM Research, ladanyi@us.ibm.com
Abstract: Mixed-Integer Rounding (MIR) inequalities play a central role in the development of strong cutting planes for mixed-integer programs. In this talk, we present our experience in developing a reference implementation of MIR Inequalities for the COIN-OR Cut Generation Library. The new implementation is available for reuse, research, and enhancements under an open-source license at www.coin-or.org.

Session: Tuesday October 26, 10:00 - 11:30

Abstracts

• Title: Implementing a Generalized Dual Pivoting Scheme
  

  Lead: Lou Hafer, Simon Fraser University, lou@cs.sfu.ca
  Abstract: Generalized dual pivoting attempts to use primal bound-to-bound flips to increase the allowable dual motion for a pivot. This talk will describe the implementation of this idea in dylp: what worked, what didn't, and some serendipitous benefits. Computational experience with netlib and miplib problems will be provided.

• Title: The LP Dual Active Set Algorithm
  

  Lead: William Hager, University of Florida, hager@math.ufl.edu
  Co-author: Timothy Davis, University of Florida, davis@cise.ufl.edu
  Abstract: We present a factorization-based implementation of the LP Dual Active Set Algorithm. This implementation exploits a proximal approximation to the dual function, a strategy for dropping inactive equations from the constraints, and recently developed algorithms for updating a sparse Cholesky factorization after a small rank change. We compare solution times to those of simplex and barrier algorithms, as implemented in CPLEX, using the Netlib LP Test Problems.

• Title: A Solver for Dense LP Problems
  

  Lead: Richard Van Slyke, Polytechnic University, rvslyke@poly.edu
  Co-author: Gavriel Yarmish, Brooklyn College, gyarmish@sci.brooklyn.cuny.edu
  Abstract: We discuss a LP solver, retroLP, based on the standard form of the simplex method that is freely available for non-commercial research applications. It is effective for dense problems and can easily be modified to make a scalable, coarse grained, distributed solver using clusters. We will address at a high level: (1) How dense does a problem need to be for retroLP to offer benefits; (2) what applications tend to lead to dense LPs; and (3) how scalable can the distributed extension be?

• Title: An Independent Evaluation of Continuous LP Codes
  

  Lead: Hans Mittelmann, Arizona State University, beck@plato.asu.edu
  Abstract: We will report on the performance of continuous LP programs for medium and larger size problems. Both simplex-based and interior point codes will be considered. The comparison includes several free codes and contrasts their performance with that of a few commercial products.

Session: Tuesday October 26, 10:00 - 11:30

Abstracts

• Title: DECOMP: A Framework for Decomposition and Dynamic Cut Generation in Integer Programming
  

  Lead: Matthew Galati, SAS Institute, matthew.galati@sas.com
  Co-author: Ted Ralphs, Lehigh University, tkr2@lehigh.edu
  Abstract: Decomposition techniques such as Lagrangian Relaxation and Dantzig-Wolfe decomposition are well-known methods of developing bounds for discrete optimization problems. We draw connections between these classical approaches and techniques based on dynamic cut generation. We discuss methods for integrating cut generation and decomposition in a number of different contexts and present DECOMP, an open-source framework that provides a uniform interface for implementation of these various techniques.

• Title: A Framework for Implementing Parallel Tree Search Algorithms
  Lead: Yan Xu, SAS Institute Inc., Yan.Xu@sas.com
  Co-author: Laszlo Ladanyi, IBM Research, ladanyi@us.ibm.com
  Ted Ralphs, Lehigh University, tkr2@lehigh.edu
  Matthew Saltzman, Clemson University, mjs@math.clemson.edu
  Abstract: ALPS is a framework for implementing and parallelizing tree search algorithms. It employs a number of features to improve scalability and support the implementation of data intensive algorithms. Implementing such algorithms in a scalable manner is challenging. We describe the design of ALPS and how the design addresses these challenges. We present two sample applications built with ALPS and preliminary computational results.

• Title: The New COIN-OR Open Solver Interface
  

  Lead: Matthew Saltzman, Clemson University, mjs@clemson.edu
  Abstract: The new COIN-OR Open Solver Interface (OSI) is a flexible, extensible C++ class library for building and managing optimization models and for using callable solver libraries. We will describe the new OSI architecture, user calls for building and solving models, and solver interface construction.

Session: Wednesday October 27, 08:00 - 09:30

IPOPT, A software package for nonlinear optimization

Chair: Robin Lougee-Heimer, IBM Research, robinlh@us.ibm.com