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, tkralphs@lehigh.edu
Abstracts
- Title: Collaborative Research and the COIN-OR resource
- Title: Simple Interface for Stochastic Programming (SISP)
- Title: The COIN-OR Open Solver Interface: Design Issues for a Portable Solver API
Lead: Leonardo Lopes, Northwestern University, leo@iems.nwu.edu
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.
Lead: Alan King, IBM Research, kingaj@us.ibm.com
Co-author: Christian Condevaux-Lanloy, University of Geneva christian.condevaux-lanloy@hec.unige.ch
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.
Lead: Matthew Saltzman, Clemson University, mjs@clemson.edu
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 ProcessingChair: Ted Ralphs, Lehigh University, tkralphs@lehigh.edu
Abstracts
- Title: Optimization on the Computational Grid
- Title: A Library Hierarchy for Implementing Scalable Parallel Search Algorithms
- Title: Object-Oriented Tools for Easy Development of Parallel Branch-and-Bound
- Title: The PICO Package for Parallel Branch and Bound: Recent Developments
Lead: Jeffrey Linderoth, Lehigh University, jtl3@lehigh.edu
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.
Lead: Ted Ralphs, Lehigh University, tkralphs@lehigh.edu
Co-author: Laszlo Ladanyi , IBM Research, ladanyi@watson.ibm.com
Matthew Saltzman, Clemson University, mjs@clemson.edu
Abstract: We describe our framework, available from www.coin-or.org, 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.
Lead: Bernard Gendron, DIRO-CRT, Universite de Montreal, gendron@iro.umontreal.ca
Co-author: Teodor Gabriel Crainic, U.Q.A.M, theo@crt.umontreal.ca
Antonio Frangioni, Universita di Pisa, frangio@di.unipi.it
François Guertin, Universite de Montreal, guertin@crt.umontreal.ca
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.
Lead: Jonathan Eckstein, Rutgers University, jeckstei@rutcor.rutgers.edu
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 MethodologyChair: Leonardo Lopes, Northwestern University, leo@iems.nwu.edu
Abstracts
- Title: Advances in an XML-based Representation for Instances of Mathematical Programs.
- Title: On Stages and Consistency Checks in Stochastic Programming
- Title: A Superadditive Dual Approach to Two-Stage Stochastic Integer Programming
Lead: Leonardo Lopes, Northwestern University, leo@iems.nwu.edu
Co-Author: Robert Fourer, Northwestern University, 4er@iems.nwu.edu
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.
Lead: Horand Gassmann, horand.gassmann@dal.ca
Co-Author: Andras Prekopa, Rutgers University, prekopa@rutcor.rutgers.edu
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.
Lead: Nan Kong, University of Pittsburgh, nak11@pitt.edu
Co-Author: Andrew J. Schaefer, University of Pittsburgh, schaefer@ie.pitt.edu
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 IIChair: Karla Hoffman , George Mason University, khoffman@gmu.edu
Abstracts
- Title: A Spectrum Auction for Deregulation without Confiscation or Unjust Ennrichment
- Title: FCC Spectrum Auctions
- Title: Bid Evaluation for FCC Auction 31 Using Column Generation
Lead: Michael Rothkopf, Rutgers University, rothkopf@rutcor.rutgers.edu
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.
Lead: Janos Csirik, AT&T Labs -- Research, janos@research.att.com
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.)
Lead: Marta Eso, IBM Research, martaeso@us.ibm.com
Co-Author: David Jenson, IBM Research, djenson@us.ibm.com
Laszlo Ladanyi, IBM Research, LaszloLadanyi@us.ibm.com
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, robinlh@us.ibm.comLocation: 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 http://www.coin-or.org.
Session: Monday Nov 18, 08:00 - 09:30
Title: Integer Programming IIIChair: Jon Lee, IBM Research, jonlee@us.ibm.com
Abstracts
- Title: Packing T-joins
- Title: Solving Lexicographic Multiobjective MIP with Column Generation
- Title: An Exact Solution Approach to the Cutting-stock Problem
Lead: Francisco Barahona, IBM Reserach, barahon@us.ibm.com
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.
Lead: Laszlo Ladanyi, IBM Research, ladanyi@us.ibm.com
Co-Author: Marta Eso, Hotchkiss School, meso@hotchkiss.org
David Jensen, IBM Research, djenson@us.ibm.com
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.
Lead: Robin Lougee-Heimer, IBM Research robinlh@us.ibm.com
Co-Authors: Laszlo Ladanyi, IBM Research, ladanyi@us.ibm.com
Jon Lee , IBM Research, jonlee@us.ibm.com
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 www.coin-or.org.
Session: Monday Nov 18, 13:30 - 15:00
Title: Open Source Optimization SoftwareChair: Brian Borchers, New Mexico Tech, borchers@nmt.edu
Abstracts
- Title: The DIRECT Algorithm for Global Optimization
- Title: BonsaiG: Blending LP and Constraint Propagation
- Title: lp_solve
- Title: SOSTOOLS - Sum of Squares Optimization Toolbox for MATLAB
Lead: Joerg Gablonsky, The Boeing Company, joerg.m.gablonsky@boeing.com
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.
Lead: Lou Hafer, Simon Fraser University, lou@cs.sfu.ca
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.
Lead: Michel Berkelaar, Magma Design Automation, michel@magma-da.com
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.
Lead: Stephen Prajna, California Institute of Technology, prajna@cds.caltech.edu
Co-Author: Antonis Papachristodoulou, California Institute of Technology, antonis@cds.caltech.edu
Pablo A. Parrilo, Swiss Federal Institute of Technology, parrilo@aut.ee.ethz.ch
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 professionalsLead: Robin Lougee-Heimer, IBM Research, robinlh@us.ibm.com
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 http://www.coin-or.org - - a simplex solver, and nonlinear program solver.
The contributors are the COIN-OR "core-team": Tobias Achterberg, ZIB, achterberg@zib.de; Francisco Barahona, IBM Research, barahon@us.ibm.com; JP Fasano, IBM Research, jpfasano@us.ibm.com; John Forrest (benevolent dictator), IBM Research, jforre@us.ibm.com; Lou Hafer, Simon Fraser University, lou@cs.sfu.ca; Robert Harder, Pentagon, Robert.Harder@pentagon.af.mil; Brady Hunsaker, Georgia Institute of Technology, hunsaker@isye.gatech.edu; Laszlo Ladanyi, IBM Research, ladanyi@us.ibm.com; Robin Lougee-Heimer, IBM Research, robinlh@us.ibm.com; Ted Ralphs, Lehigh University, tkralphs@lehigh.edu; Matthew Saltzman, Clemson University, mjs@math.clemson.edu; Katya Scheinberg, IBM Research, katyas@shtirlitz.watson.ibm.com; and Andreas Waetcher, IBM Research, andreasw@watson.ibm.com; and the active group on the coin-discuss, coin-ipopt, and coin-lpsolver mailing lists, available at http://list.coin-or.org/mailman/listinfo/
Standards Meeting: Monday, Nov 18, 20:45 - 21:45
Coordinator: Leo Lopes, Northwestern University, leo@iems.nwu.eduLocation: 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 http://www.coin-or.org.
Session: Tuesday Nov 19, 10:00 - 11:30
Title: Integer Programming SoftwareChair: Alper Atamturk, University of California, atamturk@ieor.berkeley.edu
Abstracts
- Title: The Progress of IP Software
- Title: Recent Developments in the LINDO MIP Solver
- Title: Recent Developments in CPLEX MIP
- Title: Progress in Xpress-MP's MIP Solver
Lead: Martin Savelsbergh, George Institute of Technology, mwps@isye.gatech.edu
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.
Lead: Linus Schrage, University of Chicago, linus.schrage@gsb.uchicago.edu
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.
Lead: Ed Rothberg, ILOG, erothberg@ilog.com
Abstract: This talk will discuss recent improvements in the CPLEX MIP solver.
Lead: Richard Laundy, Dash Optimization, richard.laundy@dashoptimization.com
Co-Author: Bob Daniel, Dash Optimization, bob.daniel@dashoptimization.com
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 AlgorithmsChair: Ted Ralphs, Lehigh University, tkralphs@lehigh.edu
Abstracts
Title: Workshop: Software Tools for Implementing Branch, Cut, and Price AlgorithmsLead: Ted Ralphs, Lehigh University, tkralphs@lehigh.edu
Co-Authors: Laszlo Ladanyi, IBM Research, ladanyi@watson.ibm.com
Matthew Saltzman, Clemson University, mjs@clemson.edu
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 (www.coin-or.org) to implement a state-of-the-art, parallel BCP algorithm.