COIN-OR

COIN-OR INFORMS Cup Celebration Sunday November 13, 8:30pm

COIN-OR Exhibits: Sunday, November 12, 2005, through Tuesday, November 15, 2005

COIN-OR Members and Users Group Meeting: Monday, 12:15 - 1:15 PM.

Cluster: INFORMS Computing Society / Optimization Services and Open Source Software

Chair: Robert Fourer, Northwestern University, 4er@iems.northwestern.edu
Co-Chair: John Chinneck, Carleton, chinneck@sce.carleton.ca
Co-Chair: Robin Lougee-Heimer, IBM Research, robinlh@us.ibm.com
Co-Chair: Kipp Martin, University of Chicago, kmartin@gsb.uchicago.edu
Co-Chair: Ted Ralphs, Lehigh University, tkralphs@lehigh.edu
Co-Chair: Matthew Saltzman, Clemson University, mjs@clemson.edu

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

Abstracts

• Panel Discussion: Creating an Testbed of Industry Problems for OR Model and Algorithm Development
  

  Moderator: Robin Lougee-Heimer, IBM Research, robinlh@us.ibm.com
  Panelist: David Heltne, Lakeside Associates, David.Heltne@lakesideassociates.com
  Panelist: Debasis Mitra, Bell Labs, mitra@research.bell-labs.edu
  Panelist: Suvrajeet Sen, NSF, ssen@nsf.gov
  Abstract: Many OR researchers are challenged with developing algorithms and models for industrial problems...without industry data. Data access can influence the applicability and impact of research. This panel session will analyze the challenges of sharing industry data and explore viable paths to creating a test bed of industry problems for OR.

Session: Monday Nov 14, 10:00 - 11:30

Abstracts

• Title: Model Representation and an Open Solver Interface
  

  Lead: Kipp Martin, University of Chicago, kipp.martin@gsb.uchicago.edu
  Co-author:Robert Fourer, Northwestern University, 4er@iems.nwu.edu
  Co-author:Jun Ma, Northwestern University, mjs@clemson.edu
  Abstract: In order to solve optimization models it is necessary to put them in a solver-compatible format. This is a problem due to the large number of solvers. We present a C++ open-source solver interface (or API) that can be used to communicate model instances to a solver.

• Title: Automated Tuning of Solver Parameters
  

  Lead: Brady Hunsaker, Univeristy of Pittsburgh, hunsaker@engr.pitt.edu
  Co-author: Abhijit Gosavi, University at Buffalo, SUNY, agosavi@buffalo.edu
  Abstract: We explore several methods for automated tuning of parameters for software solvers. A user specifies a test set of instances and a set of parameters. Our implementations attempt to identify good settings for the parameters without exhaustively trying every combination. We present experiments with several open-source and proprietary MIP solvers. Our implementations are available under an open-source license.

• Title: Optimization Services (OS) Library and Server
  

  Lead: Jun Ma, Northwestern University, maj@northwestern.edu
  Co-author: Robert Fourer, Northwestern University, 4er@iems.northwestern.edu
  Co-author: Kipp Martin, University of Chicago, kmartin@gsb.uchicago.edu
  Abstract: The OS library is an open source library based on a set of Optimization Services Protocols (OSP). The library supports the solution of a wide variety of optimization problem types in a loosely coupled distributed environment. Besides the OS library, we provide OS server software for users to host their own Optimization Services. We also mention a general-purpose Optimization Services modeling Language (OSmL).

• Title: A Permutation that Maximizes the Block Structure of a Symmetric Matrix
  

  Lead: Joseph Young, josyoun@nmt.edu
  Co-author: Miguel Anjos, University of Waterloo, anjos@cheetah.vlsi.uwaterloo.ca
  Abstract: This talk describes a permutation that maximizes the block structure of a symmetric matrix. Then we present a new code that allows any primal-dual interior point solver for semidefinite programming to take advantage of this permutation without modifying its source. Finally we present computational results illustrating the impact this permutation has on the performance of these codes.

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

Abstracts

• Title: OSiL: Optimization Services Instance Language
  

  Lead: Kipp Martin, University of Chicago kmartin@gsb.uchicago.edu
  Co-author: Robert Fourer, Northwestern University, 4er@iems.northwestern.edu
  Co-author: Jun Ma, Northwestern University, maj@northwestern.edu
  Abstract: In the area of mathematical optimization, it is becoming increasingly common to separate modeling languages from optimization solvers. This makes it critical to have an open standard for exchanging model instances. We present OSiL (Optimization Services Instance Language), an XML Schema for representing optimization instances. We also describe open-source Java libraries that simplify the exchange of problem-instance and solution information between modeling languages and solvers.

• Title: OSiL - Sotchastic Extensions
  

  Lead: Horand I. Gassmann, Dalhousie University, horand.gassmann@dal.ca
  Co-author: Robert Fourer, Northwestern University, 4er@iems.northwestern.edu
  Co-author: Jun Ma, Northwestern University, maj@northwestern.edu
  Co-author: Kipp Martin, University of Chicago kmartin@gsb.uchicago.edu
  Abstract: This talk presents extensions to an XML schema to allow instance representations of a wide variety of stochastic programs. Included are multistage recourse problems with discrete and continuous distributions, different risk measures (such as VaR and CVaR), robust optimization models, etc. Also included are various means of modelling stochastic processes, including ARMA(p,q) processes.

• Title: OptML: A New XML Standard for Representing Optimization Model Instances
  

  Lead: Bjarni Kristjansson, Maximal Software, bjarni@maximalsoftware.com
  Abstract: With optimization projects, there is often need to store model instances, e.g., for building model libraries, providing technical support, and optimization services over the Internet. With OptML, we propose a new portable, non-solver specific standard, based on XML, which supports multiple problem types, linear, mixed-integer, quadratic, nonlinear, and stochastic.

• Title: Panel Discussion: Standards for Optimization Problem Instances
  

  Lead: Robert Fourer, Northwestern University, 4er@iems.northwestern.edu
  Co-author: Jun Ma, Northwestern University, maj@northwestern.edu
  Co-author: Kipp Martin, University of Chicago kmartin@gsb.uchicago.edu
  Abstract: N/A

Session: Tuesday Nov 15, 13:30 - 15:00

Abstracts

• Title: Impact Solver for Optimization Services
  

  Lead: Huanyuan(Wayne) Sheng, Northwestern University, h-sheng@northwestern.edu
  Co-author: Jun Ma, Northwestern University, maj@northwestern.edu
  Co-author: Sanjay Mehrotra, Northwestern University, mehrotra@iems.northwestern.edu
  Abstract: IMPACT is a new Integrated Math Programming Advanced Computational Tool. It is the first optimization solver that natively supports the Optimization Services (OS) protocols. It integrates state-of-the-art optimization algorithms with the OS framework to provide a robust solver service.

• Title: A Problem Instance Analyzer for Optimization Services
  

  Lead: Robert Fourer, Northwestern University, 4er@iems.northwestern.edu
  Co-author: Dominique Orban, Ecole Polytechnique de Montréal, Dominique.Orban@polymtl.ca
  Abstract: We describe new developments in the design and testing of Dr. AMPL, a collection of utilities for determining properties of optimization problem instances generated from the AMPL modeling language. Dr. AMPL's problem analyzer checks properties ranging from size and sparsity to linearity and convexity, then compares the results to a database of solver characteristics to produce a list of recommended solvers. This information can then be fed to optimization services such as NEOS and OSxL.

• Title: POAMS and Web Services
  

  Lead: Victor Foulk, University of Arizona, vfoulk@email.arizona.edu
  Co-author: Leonardo Lopes, University of Arizona, leo@sie.arizona.edu
  Abstract: POAMS is an object-algebraic modeling system designed to serve as a test bed for several modularization ideas proposed by Fourer and Lopes. Like PULP, POAMS is implemented within the versatile Python scripting language. In this talk, we will demonstrate several web services and systems integration features of the POAMS system.

• Title: OSmL: Optimization Services Modeling Language
  

  Lead: Kipp Martin, University of Chicago, kmartin@gsb.uchicago.edu
  Co-author: Jun Ma, Northwestern University, maj@northwestern.edu
  Abstract: We describe Optimization Services modeling Language (OSmL), an open source algebraic modeling language for mathematical optimization. OSmL is designed to convert raw data in XML format into problem instances that conform to the Optimization Services instance language (OSiL) standard. There is support for sets, indexing, and loops. An optimization model represented in OSiL can be solved with any solver that is Optimization Services compatible.

Session: Tuesday Nov 15, 16:30 - 18:00

Abstracts

• Title: Optimization Services (OS) Framework
  

  Lead: Jun Ma, Northwestern University, maj@northwestern.edu
  Co-author: Robert Fourer, Northwestern University, 4er@iems.northwestern.edu
  Co-author: Kipp Martin, University of Chicago, kmartin@gsb.uchicago.edu
  Abstract: Optimization Services is an XML-based, service-oriented decentralized optimization architecture. It is a unified framework for the next generation distributed optimization systems. The corresponding Optimization Services Protocol (OSP) is intended to be a standard. Through standardization of representation and communication, OS provides an open infrastructure for all system components including modeling languages, servers, registries, agents, interfaces, analyzers, solvers and simulations.

• Title: Web enabled optimisation tools and models
  

  Lead: Gautam Mitra, Brunel University, Gautam.Mitra@brunel.ac.uk
  Co-author: Sachin Patkar, Indian Institute of Technology, patkar@math.iitb.ac.in
  Co-author: Chandra Poojari, CARISMA, Brunel University, chandra.poojari@brunel.ac.uk
  Abstract: We have developed a webservice frame-work called "Web enabled optimisation tools and models for research, professional training and industrial deployment"(WEBOPT). We discuss the use of session based approach wherein the information are re-used and advanced features such as warm-restart of the solver. SOAP is used as message protocol as it firewall friendly and supports complex datatypes for remote procedure calls.

• Title: Advances in Version 5 of the NEOS Server for Optimization
  

  Lead: Robert Fourer, Northwestern University, 4er@iems.northwestern.edu
  Co-author: Jorge Moré, Argonne National Laboratory, more@mcs.anl.gov
  Co-author: Todd Munson, Argonne National Laboratory,tmunson@mcs.anl.gov
  Co-author: Jason Sarich, Argonne National Laboratory,sarich@mcs.anl.gov
  Abstract: The NEOS Server makes over 40 optimization packages freely available for experimentation and evaluation over the Internet. The recently released version 5 has been rewritten using the XML-RPC, an XML-based remote procedure call protocol, to greatly simplify the work of submitting and managing requests from local client programs. Other improvements to be described include an express queue for short jobs and improved procedures for installing new solvers.

• Title: Simulation Embedding Optimization Web ServicesBR>

  Lead: Leonardo Lopes, University of Arizona, leo@sie.arizona.edu
  Co-author: Young-Jun Son, University of Arizona, son@sie.arizona.edu
  Abstract: Simulation embedding optimization uses mathematical programming to describe decisions taken within a simulation model, such as rerouting of jobs in response to a resource failure event. This research describes the web services framework to enable efficient integration of optimization within simulation. Operational control for manufacturing systems is used for illustration.

Session Wednesday Nov 16 10:00 - 11:30

Abstracts

• Title: OSU's Open Source Lab: How we got to open source
  

  Lead: Scott Kveton, OSU Open Source Lab, scott@osuosl.org
  Abstract: OSU's Open Source Lab (OSL) has leveraged open source like no other University to help solve its IT problems and attract talent. Come learn how OSU "got to open source" and how it is changing how we do business more and more everyday. The OSL is doing software development on projects such as Kuali (http://kuali.org) and also provides hosting for projects such as the Mozilla Foundation, Gentoo Linux and the Freenode IRC Letwork.

• Title: How to Publish your Code on COIN-OR
  

  Lead: Robin Lougee-Heimer, IBM Research, robinlh@us.ibm.com
  Abstract: We review the processes and decisions involved in contributing to a COIN-OR project or "publishing" your own open-source code, data, and models in the COIN-OR repository. Common misconceptions regarding licenses, code ownership, and open-source will be discussed and your questions discussed.

• Title: CoinMP: Simple C-API Windows DLL implementation of CLP, CBC, and CGL
  

  Lead: Bjarni Kristjansson, Maximal Software, bjarni@maximalsoftware.com
  Abstract: The COIN Open Source Initiative has become very popular in the recent years. To make life easier for users that simply want to solve models and not compile C++ applications, we have developed standard C-API Windows DLL CoinMP.DLL that implements most of the functionality of CLP, CBC, and CGL.

Session: Wednesday Nov 16, 13:30-15:00

Abstracts

• Title: Latest Developments in the SYMPHONY Callable Library
  

  Lead: Ted Ralphs, Lehigh University tkralphs@lehigh.edu
  Co-author: Menal Guzelsoy, Lehigh University, megb@lehigh.edu
  Abstract: We will describe the latest developments in the SYMPHONY callable library for solving lixed-integer programs, focusing in particular on new procedures for warm starting and sensitivity analysis.

• Title: A Library Hierarchy for Implementing Scalable Parallel Search Algorithms
  

  Lead: Yan Xu, SAS Institute Inc., yan.xu@sas.com
  Co-author: Laszlo Ladanyi, IBM Research, ladanyi@us.ibm.com
  Co-author: Ted Ralphs, Lehigh University tkralphs@lehigh.edu
  Co-author: Matthew Saltzman, Clemson University, mjs@clemson.edu
  Abstract: We discuss a library hierarchy for implementing scalable parallel search algorithms: ALPS, BiCePS and BLIS. ALPS forms the base layer, which is also the search handling layer, BiCePS is the data handling layer, and BLIS implements LP-based branch and bound algorithms. We present computational results for solving large integer programs.

• Title: DECOMP: A Framework for Decomposition in Integer Programming
  

  Lead: Matthew Galati, SAS Institute, matthew.galati@sas.com
  Co-author: Ted Ralphs, Lehigh University, tkralphs@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: Open-source branch-and-bound Tree Size Prediction
  

  Lead: Brady Hunsaker, Univeristy of Pittsburgh, hunsaker@engr.pitt.edu
  Co-author: Joseph Gallo, University of Pittsburgh, jsg8@pitt.edu
  Abstract: We present open-source implementations of the technique proposed by Cornuejols, Karamanov, and Li for predicting the eventual size of a branch-and-bound tree. We explore the ease of implementation in two open-source solvers, GLPK and CLP, and report on the effectiveness of the technique for these solvers.

Title: Open-source branch-and-bound Tree Size Prediction Abstract: We present open-source implementations of the technique proposed by Cornuejols, Karamanov, and Li for predicting the eventual size of a branch-and-bound tree. We explore the ease of implementation in two open-source solvers, GLPK and CLP, and report on the effectiveness of the technique for these solvers.

Session: Wednesday Nov 16, 15:30 - 17:00

Abstracts

• Title: Recent Improvements in CSDP
  

  Chair: Brian Borchers, New Mexico Tech, borchers@nmt.edu
  Abstract: CSDP is an open-source package for semidefinite programming that has been under development since 1997. In this presentation we will describe CSDP and some of its recent enhancements.

• Title: SDPA (SemiDefinite Programming Algorithm) and its Parallel/Completion versions
  

  Lead: Makoto Yamashita, Kanagawa University, Makoto.Yamashita@ie.kanagawa-u.ac.jp
  Co-author: Katsuki Fujisawa, Tokyo Denki University, fujisawa@rnc.r.dendai.ac.jp
  Mituhiro Fukuda, Tokyo Institute of Technology, mituhiro@is.titech.ac.jp
  Masakazu Kojima, Tokyo Institute of Techonology, kojima@is.titech.ac.jp
  Kazuhide Nakata, Tokyo Institute of Technology, knakata@me.titech.ac.jp
  Abstract: We have developed the SDPA, a sophisticated software for solving general SDPs based on a primal-dual interior-point method, since 1995. On the basis of its outstanding achievements, we have implemented its parallel version which solves extremely large-scale SDPs on multiple processors. We have also combined with the completion method to exploit efficiently structural sparsities of SDPs. In this talk, we outline the features of each software and introduce their online interface.

• Title: New Features and Improvements in SeDuMi
  

  Lead: Imre Polik, McMaster University, poliki@mcmaster.ca
  Co-author: Robert Fourer, McMaster University, terlaky@mcmaster.ca
  Abstract: Following the tragic death of Jos Sturm, the Advanced Optimization Lab at McMaster University took over the development of the SeDuMi package in 2004 and the first new version was released in May 2005. This talk summarizes the new features and improvements as well as our future plans. Our major topics are preprocessing, starting-point selection, sparse/dense issues and adaptive heuristics. Numerical experiments showing the effect of these techniques are also presented.

• Title: A Permutation that Maximizes the Block Structure of a Symmetric Matrix
  

  Lead: Joseph Young, josyoun@nmt.edu
  Co-author: Miguel Anjos, University of Waterloo, anjos@cheetah.vlsi.uwaterloo.ca
  Abstract: This talk describes a permutation that maximizes the block structure of a symmetric matrix. Then we present a new code that allows any primal-dual interior point solver for semidefinite programming to take advantage of this permutation without modifying its source. Finally we present computational results illustrating the impact this permutation has on the performance of these codes.

• Title: Inexact Path-following Algorithms for Some Convex Quadratic SDP Problems
  

  Lead: Mike Todd, Cornell University miketodd@cs.cornell.edu
  Co-author: Kim Toh, National University of Singapore, mattohkc@nus.edu.sg
  Co-author: Reha Tutuncu, Carnegie Mellon University, reha@cmu.edu
  Abstract: We propose a primal-dual path-following interior-point method for solving certain convex quadratic semidefinite programming (QSDP) problems, using a preconditioned iterative method to solve the Schur complement equation. Numerical experiments on a variety of QSDPs with matrices of dimensions up to 2000 are described.

Session: Wednesday Nov 16, 13:30 - 15:00

Tutorial: COIN-OR Branch and Cut (CBC) Solver

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

• Tutorial: CBC, the COIN-OR Branch and Cut Solver
  

  Presenter:   Robin Lougee-Heimer, IBM Research,robinlh@us.ibm.com
  Author: John Forrest, IBM Research jjforre@us.ibm.com
  Abstract: The Computational Infrastructure for Operations Research (COIN-OR) Branch and Cut solver (CBC) is an open-source mixed-integer program solver. CBC provides operations research professionals with a well-tested, robust, re-useable code base for experimenting with advanced customizations of branch-and-cut algorithms. This tutorial introduces CBC, and illustrates how to implement a variety of common branch-and-cut customizations in CBC.