COIN-OR and Open-Source Events
INFORMS San Jose 2002 Meeting

Presentations, workshops, user-group meetings, and posters on open source software at the San Jose 2002 INFORMS meeting. To facilitate session hopping, all talks in a session are listed. The non-open-source talks in listed in grey.

The COIN-OR User Group Meeting will be Sunday night, 6:30 - 7:30 pm in Ballroom A8 of the Convention Center (aka near the Welcome Reception location).

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

Session: Sunday Nov 17, 08:00 - 09:30

Title: Standards and Interfaces in Mathematical Programming
Chair: Ted Ralphs, Lehigh University,
  • Title: Collaborative Research and the COIN-OR resource

  • Lead: Leonardo Lopes, Northwestern University,
    Abstract: When research projects involve the interests of many partners, it becomes necessary to explicitly address additional communication, time, and resource problems. Our XML standard for optimization illustrates how COIN-OR can help address those problems, provide visibility, and facilitate access to talent and knowledge across different specialties.
  • Title: Simple Interface for Stochastic Programming (SISP)

  • Lead: Alan King, IBM Research,
    Co-author: Christian Condevaux-Lanloy, University of Geneva
    Abstract: We propose a general approach to link a stochastic programming enabler to an Algebraic Modeling Language: SISP, the Simplified Interface for Stochastic Programming, to mediate a simple interface between Algebraic Modeling Languages and solvers that use the Stochastic Mathematical Programming System (SMPS) format.
  • Title: The COIN-OR Open Solver Interface: Design Issues for a Portable Solver API

  • Lead: Matthew Saltzman, Clemson University,
    Abstract: The Open Solver Interface (OSI) component of COIN-OR provides a uniform application program interface to several different commercial and non-commercial LP solver libraries. This presentation describes features of the OSI and design issues for providing access to a useful standard feature set for embedded solvers.

Session: Sunday Nov 17, 10:00 - 11:30

Title: Software Tools for Parallel Processing
Chair: Ted Ralphs, Lehigh University,
  • Title: Optimization on the Computational Grid

  • Lead: Jeffrey Linderoth, Lehigh University,
    Abstract: The CPU power offered by collections of loosely coupled, heterogeneous, non-dedicated computing resources opens new doors for users of optimization technology. We introduce the Computational Grid, describe software tools for using the Grid, highlight successful applications of the Grid in solving numerical optimization problems, and mention possible future directions.
  • Title: A Library Hierarchy for Implementing Scalable Parallel Search Algorithms

  • Lead: Ted Ralphs, Lehigh University,
    Co-author: Laszlo Ladanyi , IBM Research,
    Matthew Saltzman, Clemson University,
    Abstract: We describe our framework, available from, for building parallel tree search algorithms. The framework includes general parallel search handling, a layer for implementing parallel branch and bound, and a mechanism for "data-intensive" applications (such as branch-and-cut), in which a large number of global data objects are needed to describe search nodes.  
  • Title: Object-Oriented Tools for Easy Development of Parallel Branch-and-Bound

  • Lead: Bernard Gendron, DIRO-CRT, Universite de Montreal,
    Co-author: Teodor Gabriel Crainic, U.Q.A.M,
    Antonio Frangioni, Universita di Pisa,
    François Guertin, Universite de Montreal,
    Abstract: We present and compare several parallel branch-and-bound approaches, which exploit various degrees of search control and memory management. Our implementations are designed for both shared-memory and message-passing environments. Because they are based on object-oriented programming tools, our implementations are generic and allow easy development of parallel branch-and-bound algorithms for any class of problems. We illustrate their use on classical combinatorial optimization problems.
  • Title: The PICO Package for Parallel Branch and Bound: Recent Developments

  • Lead: Jonathan Eckstein, Rutgers University,
    Abstract: PICO is a C++ class library for scalably implementing a variety of branch-and-bound algorithms on a range of parallel rchitectures. I will describe the enhancements to the design and implementation over the past few years, and present the most recent computational results for MIP problems.

Session: Sunday Nov 17, 16:30 - 18:00

Title: Stochastic Optimization II - Solution Methodology
Chair: Leonardo Lopes, Northwestern University,
  • Title: Advances in an XML-based Representation for Instances of Mathematical Programs.

  • Lead: Leonardo Lopes, Northwestern University,
    Co-Author: Robert Fourer, Northwestern University,
    Abstract: We report progress over the last year on an XML-based dialect for conveying instances of mathematical programs belonging to a wide range of categories. Amongst the advances, we emphasize: better definitions of all components an AMPL drive for basic linear programming problems; and a problem server solvers can connect to.  
  • Title: On Stages and Consistency Checks in Stochastic Programming

  • Lead: Horand Gassmann,
    Co-Author: Andras Prekopa, Rutgers University,
    Abstract: Different branches of stochastic programming use different definitions of stages. This talk proposes a unified approach, necessary to permit automatic problem generation from user input. This affects the construction of input formats (SMPS) and the design of algebraic modelling languages (such as AMPL). It also allows automatically generated consistency checks. 
  • Title: A Superadditive Dual Approach to Two-Stage Stochastic Integer Programming

  • Lead: Nan Kong, University of Pittsburgh,
    Co-Author: Andrew J. Schaefer, University of Pittsburgh,
    Abstract: We consider a class of stochastic programs with integer recourse and reformulate them using superadditive duality. This allows us to solve instances that are several orders of magnitude larger than problems found in the literature. We provide theoretical and computational results and give directions for future research.

Session: Sunday Nov 17, 16:30 - 18:00

Title:  Spectrum Auctions II
Chair: Karla Hoffman , George Mason University,
  • Title: A Spectrum Auction for Deregulation without Confiscation or Unjust Ennrichment

  • Lead: Michael Rothkopf, Rutgers University,
    Abstract: We propose a series of market-clearing-price auctions for residual spectrum rights. Adapting McGuire's "inter-tract" bidding idea, we make bidders for different spectrum bands compete with each other. Only those offering the highest bids per MHz-Pop will win. Combinatorial bids can be allowed while maintaining a polynomial winner determination process.    
  • Title: FCC Spectrum Auctions

  • Lead: Janos Csirik, AT&T Labs -- Research,
    Abstract: Some of the biggest auctions that occured to date were auctions where governments sold licences for wireless phone use. We have implemented a simulator for FCC spectrum auctions and used it to study strategies for a recent FCC spectrum auction (No. 35) where approximately $17 billion was raised. This talk will report on the work done, some of our conclusions, and a discussion of their applicability to other auctions. (Joint work of S Baveja, JAC, ML Littman, PSA Reitsma, P Stone.)
  • Title: Bid Evaluation for FCC Auction 31 Using Column Generation

  • Lead: Marta Eso, IBM Research,
    Co-Author: David Jenson, IBM Research,
    Laszlo Ladanyi, IBM Research,
    Abstract: We report on implementing a shadow solver to verify results obtained by the FCC in-house solver. We use branch-and-price(COIN/BCP with OSL) for bid evaluation, avoiding most numerical difficulties associated with the natural formulation. Computational aspects of both the bid evaluation and pricing problems are addressed and tested on FCC simulated data.

COIN-OR Users Group Meeting: Sunday Nov 17, 18:30 - 19:30

Coordinator: Robin Lougee-Heimer, IBM Research,
Location: Ballroom A8 of the Convention Center (near the Welcome Reception location)
Agenda: Report on progress, hosting status, and Open Q & A time. If you would like to talk or propose a discussion item, just bring it up on the coin-discuss mailing list available at

Session: Monday Nov 18, 08:00 - 09:30

Title:  Integer Programming III
Chair:  Jon Lee, IBM Research,
  • Title: Packing T-joins

  • Lead: Francisco Barahona, IBM Reserach,
    Abstract: Given a graph G=(V,E), a set of nodes labelled by T, and a set of edge-weights, it is known that the weight of a maximum packing of T-joins is equal to the weight of a minimum T-cut. However Padberg-Rao's algorithm for minimum T-cuts does not give a T-join packing. We present a combinatorial algorithm to find an optimal packing of T-joins.
  • Title: Solving Lexicographic Multiobjective MIP with Column Generation

  • Lead: Laszlo Ladanyi, IBM Research,
    Co-Author: Marta Eso, Hotchkiss School,
    David Jensen, IBM Research,
    Abstract: We present a method to solve lexicographic multiobjective MIPs (find the solution among the ones optimal wrt. a primary objective that is the best wrt. a secondary objective) using column generation without combining the two objective functions. Limited computational results on auction related data will be presented.    
  • Title: An Exact Solution Approach to the Cutting-stock Problem

  • Lead: Robin Lougee-Heimer, IBM Research
    Co-Authors: Laszlo Ladanyi, IBM Research,
    Jon Lee , IBM Research,
    Abstract: We present a new approach for solving the cutting-stock problem to optimality and report on our computational experience. Our method utilizes open-source software components available in the COIN-OR repository at

Session: Monday Nov 18, 13:30 - 15:00

Title: Open Source Optimization Software
Chair: Brian Borchers, New Mexico Tech,
  • Title: The DIRECT Algorithm for Global Optimization

  • Lead: Joerg Gablonsky, The Boeing Company,
    Abstract: We will describe the DIRECT algorithm for global optimization, and some extensions to it. These extensions either improve the applicability of the method, or its performance. We will then describe our implementation, and give performance results both for common test problems, and on some industrial problems.   
  • Title: BonsaiG: Blending LP and Constraint Propagation

  • Lead: Lou Hafer, Simon Fraser University,
    Abstract: bonsaiG is an open-source MIP code which integrates constraint propagation with standard LP-based branch-and-bound. The talk will discuss implementation and performance, and also provide some comments on open-source development.    
  • Title: lp_solve

  • Lead: Michel Berkelaar, Magma Design Automation,
    Abstract: Lp_solve is a free (Mixed Integer) Linear Program solver, released under the Lesser GNU Public License. This presentation will touch the history and planned future development of lp_solve, its capabilies and limitations.
  • Title: SOSTOOLS - Sum of Squares Optimization Toolbox for MATLAB

  •  Lead: Stephen Prajna, California Institute of Technology,
     Co-Author: Antonis Papachristodoulou, California Institute of Technology,
     Pablo A. Parrilo, Swiss Federal Institute of Technology,
    Abstract: SOSTOOLS is a free MATLAB toolbox for solving sum of squares optimization programs. It can be used to solve various continuous and combinatorial optimization problems. We present the features of SOSTOOLS and illustrate its usage with some examples. Hands-on experiences with developing and maintaining SOSTOOLS are also addressed.

The Practice Poster Session: Monday, Nov 18th 16:00 - 17:30 (Q&A at poster)

Title: The Computation Infrastructure for Operations Research: a free software library for operations research professionals
Lead: Robin Lougee-Heimer, IBM Research,
Abstract: The time needed to implement algorithms for testing theory and delivering applications can be dramatically shortened when existing source code is reused. The COIN-OR initiative is a community effort, developing free software for the needs of operations researchers. Newly available at - - a simplex solver, and nonlinear program solver.

The contributors are the COIN-OR "core-team": Tobias Achterberg, ZIB,; Francisco Barahona, IBM Research,; JP Fasano, IBM Research,; John Forrest (benevolent dictator), IBM Research,; Lou Hafer, Simon Fraser University,; Robert Harder, Pentagon,; Brady Hunsaker, Georgia Institute of Technology,; Laszlo Ladanyi, IBM Research,; Robin Lougee-Heimer, IBM Research,; Ted Ralphs, Lehigh University,; Matthew Saltzman, Clemson University,; Katya Scheinberg, IBM Research,; and Andreas Waetcher, IBM Research,; and the active group on the coin-discuss, coin-ipopt, and coin-lpsolver mailing lists, available at

Standards Meeting: Monday, Nov 18, 20:45 - 21:45

Coordinator: Leo Lopes, Northwestern University,
Location: The Plaza Room of the Fairmont Hotel (across the street from the General Reception)
Agenda: Report on progress, both theoretical and practical, Software demonstrations of mathematical software using XML today, and Open Q & A time. If you would like to talk or propose a discussion item, just bring it up on the coin-standards mailing list available at

Session: Tuesday Nov 19, 10:00 - 11:30

Title:  Integer Programming Software
Chair: Alper Atamturk, University of California,
  • Title: The Progress of IP Software

  • Lead: Martin Savelsbergh, George Institute of Technology,
    Abstract: In the past decade we have witnessed significant changes in the commercially available integer programming technology. In this talk, we briefly highlight some of these changes, such as improved linear programming technology, better integer preprocessing, and the incorporation of cutting planes. Next, we provide a personal perspective on what we can expect in the years to come.
  • Title: Recent Developments in the LINDO MIP Solver

  • Lead: Linus Schrage, University of Chicago,
    Abstract: We describe recent enhancements to the LINDO MIP solver in the area of exploiting problem structure, especially structures that arise when trying to represent nonlinearities.  
  • Title: Recent Developments in CPLEX MIP

  • Lead: Ed Rothberg, ILOG,
    Abstract: This talk will discuss recent improvements in the CPLEX MIP solver.
  • Title: Progress in Xpress-MP's MIP Solver

  • Lead: Richard Laundy, Dash Optimization,
    Co-Author: Bob Daniel, Dash Optimization,
    Abstract: In this talk we describe progress in cutting plane generation within Xpress-MP. We show the performance improvements that can be achieved and give computational results showing the effectivenes of cutting plane generation when combined with branch-and-bound.

Session: Wednesday Nov 20, 08:00 - 09:30

Title:  Workshop: Software Tools for Implementing Branch, Cut, and Price Algorithms
Chair: Ted Ralphs, Lehigh University,
Title: Workshop: Software Tools for Implementing Branch, Cut, and Price Algorithms
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 simultaneous dynamic generation of 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 ( to implement a state-of-the-art, parallel BCP algorithm.