COIN-OR

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

Abstracts

• Title: Collaborative Research and the COIN-OR resource

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.
• Title: Simple Interface for Stochastic Programming (SISP)

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.
• Title: The COIN-OR Open Solver Interface: Design Issues for a Portable Solver API

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

Abstracts

• Title: Optimization on the Computational Grid

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.
• Title: A Library Hierarchy for Implementing Scalable Parallel Search Algorithms

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.  
• Title: Object-Oriented Tools for Easy Development of Parallel Branch-and-Bound

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.
• Title: The PICO Package for Parallel Branch and Bound: Recent Developments

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

Abstracts

• Title: Advances in an XML-based Representation for Instances of Mathematical Programs.

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.  
• Title: On Stages and Consistency Checks in Stochastic Programming

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. 
• Title: A Superadditive Dual Approach to Two-Stage Stochastic Integer Programming

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

Abstracts

• Title: A Spectrum Auction for Deregulation without Confiscation or Unjust Ennrichment

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.    
• Title: FCC Spectrum Auctions

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.)    
• Title: Bid Evaluation for FCC Auction 31 Using Column Generation

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

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

Abstracts

• Title: Packing T-joins

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.

• Title: Solving Lexicographic Multiobjective MIP with Column Generation

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.    
• Title: An Exact Solution Approach to the Cutting-stock Problem

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

Abstracts

• Title: The DIRECT Algorithm for Global Optimization

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.   
• Title: BonsaiG: Blending LP and Constraint Propagation

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.    
• Title: lp_solve

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.
• Title: SOSTOOLS - Sum of Squares Optimization Toolbox for MATLAB

 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)

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

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

Abstracts

• Title: The Progress of IP Software

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.
• Title: Recent Developments in the LINDO MIP Solver

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.    
• Title: Recent Developments in CPLEX MIP

Lead: Ed Rothberg, ILOG, erothberg@ilog.com
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, 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

Abstracts