Brad Bell, University of Washington

Title: An Introduction by Example to Algorithmic Differentiation

Preface -- Algorithmic Differentiation (often referred to as Automatic Differentiation or just AD) uses the software representation of a function to obtain an efficient method for calculating its derivatives. These derivatives can be of arbitrary order and are analytic in nature (do not have any truncation error). A forward mode sweep computes the partial derivative of all the dependent variables with respect to one independent variable. A reverse mode sweep computes the derivative of one dependent variables with respect to all the independent variables. The number of floating point operations for either of these sweeps is a small multiple of the number required to evaluate the original function. Thus, you can evaluate the derivative of a scalar valued function with respect to thousands of variables in a small multiple of the work to evaluate the original function. In addition, AD automatically takes advantage of the speed of your algorithmic representation of a function. For example, if you calculate a determinant using LU factorization, AD will use the LU representation for the derivative of the determinant (which is faster than using the definition of the determinant).

Purpose -- This is an introduction by example to Algorithmic Differentiation. Its purpose is to aid in understand what AD calculates, how the calculations are preformed, and the amount of computation and memory required for a forward or reverse sweep. We define an algorithm that approximates the exponential function. We then write out the floating point operation sequence that corresponds to a specific input to the algorithm. We then use the operation sequence, and a forward mode sweep, to calculate a derivative of the corresponding function. This is followed by calculation of the same derivative using a reverse mode sweep.

Reference

An in-depth review of AD theory and methods can be found in the book Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation , Andreas Griewank, SIAM Frontiers in Applied Mathematics, 2000.

Pierre Bonami, Carnegie Mellon University

Tutorial: BONMIN: A New Solver for Mixed Integer NonLinear Programming

BONMIN (Basic Open-source Nonlinear Mixed INteger programming) is an open-source solver for Mixed Integer NonLinear Programming (MINLP). It has been developed in the last two years as part of a joint effort by researchers at IBM and Carnegie Mellon University to build methods and software for MINLP. The code uses software from several other COIN-OR project as building blocks: Cbc or BCP for the branch-and-bounds and branch-and-cuts, Cgl for cut generation, Clp for solving linear programming relaxations and IPOPT for solving non-linear programming relaxation.

The aim of this tutorial is to provide an understanding of how the different COIN-OR components work together in BONMIN and to model and solve an MINLP using the C++ interface using different algorithms. The practical part of the tutorial can be carried out individually or in small groups with the help and support of the presenter.

Particular topics of interest for attendants (such as modeling a specific problem, modifying more profoundly some parts of the algorithms, interfacing another nonlinear solver, ...) can also be covered in the practical part of the tutorial. Please submit any such particular topics of interest or questions to pbonami@andrew.cmu.edu in advance.

Note that for people interested in getting a complete background on how the code solve MINLP's and on advanced techniques to tune it to their needs, the tutorials on Ipopt, CBC and BCP should be of particular interest.

Title: The Ongoing Development of CSDP

CSDP is a subroutine library and stand-alone solver for semidefinite programming problems that has been under development since 1997. The software is now being made available as an open source project through the COIN-OR repository. The current status of CSDP and future development plans will be described.

Title: Challenges and Opportunities Generated by the Increasing Importance of Optimization in Supply Chain Management

Over the past 10 years IBM has demonstrated sustained due diligence in bringing the benefits of optimization to the area of supply chain management particularly within its offering called "Operational Framework for Advanced Supply Chain Planning". This work has generated substantial benefits within IBM and to IBM customers. To achieve these benefits, significant challenges in model formulation, model solving, and "production ready" status are consistently being met. This presentation will review our current solution using IBM's Optimization Subroutine Library (OSL) and the migration to CLP and CBC both from a technical and administrative perspective.

Title: Overview of the PEBBL and PICO Projects: Massively Parallel Branch and Bound

PEBBL is an open source, massively parallel branch-and-bound search framework developed at Rutgers and Sandia National Labs. PEBBL is the basis for PICO, a mixed integer optimizer currently under development. Several Sandia applications are based on either PEBBL or PICO. This talk will provide an overview of the PEBBL and PICO software architecture, applications, and implementation status. We will discuss how PICO draws on COIN software components, and discuss some special implementation challenges in PEBBL, such as parallel termination detection, checkpointing, enumeration of multiple near-optimal solutions, and solution output.

Joint work with Cynthia Phillip, William Hart, and numerous other researchers at or connected with Sandia National Labs.

Title: Getting and Building COIN-OR

In this talk we will discuss how to obtain the source code and build the modules available on the COIN-OR web site, www.coin-or.org. The goal of this session is to provide a hands-on opportunity for all attendees bringing wireless-enabled laptops to download and build the COIN-OR Linear Program Solver (CLP) and the COIN-OR Branch and Cut Solver (CBC).

Because of the wide variety of platforms expected at the workshop, attendees are encouraged to try to download and build their favorite projects prior to the workshop. For assistance with individual issues or to suggest a topic for this talk, please contact the speaker prior to the workshop at jpfasano@us.ibm.com

John Forrest, IBM

Tutorial: CLP: COIN-OR Linear Program solver

The COIN LP Solver is a free, open-source, linear program solver, with emphasis on Simplex based algorithms. This tutorial will present some of the ideas behind CLP and will explain some of the options which can be used to improve performance using the stand-alone solver. The tutorial will include walking through one or two examples written in C++ (suggestions for such examples may be submitted before the workshop). There will be time for answers to questions on using CLP, future developments and ways users can help. The source code to CLP and the examples are available at www.coin-or.org

John Forrest, IBM

Tutorial: COIN-OR Branch and Cut (CBC)

The COIN LP Solver is a free, open-source, mixed-integer program solver. This tutorial will present some of the ideas behind CBC and will explain some of the options which can be used to improve performance using the stand-alone solver. The tutorial will include walking through one or two examples written in C++ (suggestions for such examples may be submitted before the workshop). There will also be some discussion of linking CBC to AMPL. There will be time for answers to questions on using CBC, future developments and ways users can help. The source code to CBC and the examples are available at www.coin-or.org

Title: Mixed-Integer Rounding Inequalities for COIN-OR

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.

This is joint work with Laszlo Ladanyi.

Title: Tightening `Big M' Disjunctions

One way to linearise a pair of disjunctive constraints on continuous variables is to use a binary variable with a `big M' coefficient. The original constraints are augmented so that setting the binary variable to 0 or 1 renders one constraint ineffectual. This form has some attractive modelling capabilities, but the computational behaviour of the linear relaxation is notoriously bad. This talk will describe an approach that may offer improved behaviour, using cutting planes that must be constantly updated by tightening bounds on continuous variables. The talk will mix theory and implementation; the proportion will depend on progress.

Title: Branch-and-Bound Algorithms for Solving the Quadratic Assignment

The Quadratic Assignment Problem (QAP) has been an object of OR research since 1968. While heuristic methods give near optimum and often optimum objective function values in reasonable time, exact methods are needed for verification and evaluation of heuristic methods. We have developed two branch-and-bound algorithms based upon Reformulation Linearization Technique (RLT) representations of the QAP that are in most cases the fastest for finding exact solutions on single processor platforms. The first of these algorithms works well on small to moderate test cases and on large test cases that were designed to be difficult for heuristic solution methods. The second works well on larger test cases that are difficult to solve exactly. We present here results from experiments with these codes on recognized QAP test cases and compare them with the only known competitive exact solution method. We then describe the structure of the FORTRAN code for the first of these two algorithms. We are seriously considering open-source for this code and welcome suggestions.

Title: Building a Tabu Search with the Java Engine OpenTS

OpenTS provides logical building blocks for creating your own tabu search metaheuristic. We will introduce tabu search to those who are unfamiliar with it and break down a search into its component pieces. The classes and objects in OpenTS will help us focus our design efforts. In this workshop we will look at everything from moving around our "neighborhood" to building reactive "tabu lists."

Title: A Subroutine Interface to Nonlinear Programming Problems -- NLPAPI

I will give an overview of the NLPAPI (NonLinear Problem Application Programming Interface) project on COIN. NLPAPI provides tools for defining optimization problems with nonlinear objective, equality and inequality constraints. These problems may then be "solved" by a solver (currently interfaces to LANCELOT and Ipopt are included). The advantage of the problem representation used by NLPAPI over representations of the objective and constraints as functions of all the problem variables is that the user may define functions (and their derivatives) of smaller subsets of the variables, and combine them into functions defining the objective and constraints. This allows for some degree of automatic differentiation (i.e. the derivatives of the combinations can be expressed in terms of the smaller functions), and also allows for a sparsity structure to be determined. In addition, if the derivatives of the small functions are not known they can be differenced much more cheaply than the entire objective or constraint function.

The current implementation uses the same representation as LANCELOT, but future planned enhancements include allowing more general combinations.

Title: Automated Tuning of Solver Parameters

We explore methods for automated tuning of parameters for softwaresolvers. A user specifies a test set of instances and a set of parameters. Our implementation attempts to identify good settings for the parameters without exhaustively trying every combination, using ideas from software testing and machine learning.

This research is motivated by the need for automated ways to determine default parameter settings for open-source solvers in COIN-OR, though our implementation includes a flexible interface. We intend to submit our code to COIN-OR in the near future.

This is joint work with Mustafa Baz, Paul Brooks, and Abhijit Gosavi.

Title: SMI: Stochastic Modeling Interface for COIN-OR

The Stochastic Modeling Interface is a COIN-OR project that enables modelers to incorporate stochastic information into optimization models. The Stochastic Modeling Interfaces is built entirely from COIN-OR native components (e.g., OSI, CLP, coin-utilities). In this talk, we discuss the progress on architecting and implementing a modeling interface for stochastic programming in the COIN system.

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

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.

Laszlo Ladanyi, IBM and Francois Margot, Carnegie Mellon University

BCP: Branch-Cut-Price Framework

In this 2.5 hour tutorial, we give an introduction on how to use BCP, a branch-cut-price framework. This tutorial mixes presentations of specific features of BCP with practical examples of their use. The aim of the tutorial is to provide a basic understanding of the code and to allow a new user to develop a relatively simple application using the Cgl cut generators, customized branching and customized column generation. The practical part of the tutorial is done individually or in small groups with help from the presenters.

More advanced users have the opportunity to work on more advanced topics, such as heuristics, user data, or any particular question they might have. Please submit questions or topics of interest to ladany@us.ibm.com as soon as possible.

Title: Modeling with COIN-OR Tools

In this demo and tutorial session, we will explore several approaches for creating Mathematical Programming Models involving COIN-OR tools. We will show how COIN-OR solvers can be accessed from commercial modeling languages, using the Mathprog component of GLPK, using the COIN-OR modeling library FlopC++, and as a Web Service.

Title: Cyber infrastructure: Initiatives at the National Science Foundation

The US National Science Foundation has established an Office of Cyberinfrastructure to coordinate and support the acquisition, development and provision of state-of-the-art cyber infrastructure resources, tools and services essential to the conduct of 21st century science and engineering research and education. The speaker will outline the activities of this office, related activities in the Engineering directorate, and their relevance to Operations Research and related fields.

Title: An Open Interface for Hooking Solvers to Modeling Systems

Every optimization modeling system has developed its own way of representing problem instances. Hence each solver package for optimization problems must have a separate "driver" for every modeling system that it supports. We describe a new open standard that, once adopted by modeling systems, will require each solver to have only one driver. The components of our proposal include OsiL, a new XML-based representation for optimization problem instances, and OSInstance, a corresponding in-memory representation. An open source library provides application programming interfaces for reading and writing OSiL and OSInstance and for converting between them. Related languages and libraries handle the passing of options to solvers and the retrieval of results, as well as protocols for facilitating solver registration, client and scheduler discovery, and communication between the various components of the optimization process. This session will emphasize the practical aspects of using our tools to hook solvers to modeling systems, focusing on our overall Optimization Services framework (Ma), the modeling system interface to our library (Fourer), and the solver interface to our library (Martin).

Title: Optimizing PICO's CLP Interface

PICO, the massively Parallel Integer and Combinatorial Optimization engine being developed at Sandia National Labs, includes a generic LP solver interface, PicoLPInterface, that is derived from OSI. We will discuss ways in whichPicoLPInterface differs from OSI as well as performance issues encountered in optimizing PicoLPInterface's CLP interface module.

Title: Experience with CGL in the PICO Mixed-integer Programming Solver

PICO (Parallel Integer and Combinatorial Optimizer) is a parallel branch-and-bound optimization framework with a mixed-integer program (MIP) solver. We describe our experience using COIN's Cut Generation Library (CGL) in PICO's branch and cut MIP solver. The PICO cut finder and row cut classes build on the CGL cut generator classes and the OsiRowCut classes. The PICO classes add functionality necessary for our cut management strategy. We will also discuss cut-management-related enhancements to PICO's solver interface, which is derived from COIN's Open Solver Interface (OSI). We will discuss algorithmic aspects of PICO's branch-and-cut solver as necesssary to provide context for software issues.

This is joint work with Jonathan Eckstein (Rutgers), and William Hart (Sandia National Labs)

Tutorial: The SYMPHONY Callable Library for Mixed-integer Linear Programming

This tutorial will be an introduction to the use of the SYMPHONY callable library, the SYMPHONY interactive solver, and the SYMPHONY solver framework. The tutorial will be hands-on, and the goal is for each participant to successfully configure and compile SYMPHONY in their chosen development environment and to get some practical experience using it. The tutorial will begin with an overview of the various configurations in which SYMPHONY can be built and used, an overview of the configuration and build process, and examples of the use of both the interactive solver and the callable library. Because there are so many different configuration options, participants are encouraged to consider before the workshop how they intend to use it and to try to build SYMPHONY on their computers in the desired configuration, so that we can quickly resolve any build problems. Information on downloading and building SYMPHONY can be obtained at http://www.branchandcut.org/SYMPHONY.

Since most users of SYMPHONY are interested in the features of SYMPHONY that differentiate it from other solvers, we will spend the second part of the tutorial discussing such topics as using the solver in parallel, using it to solve biobjective integer programs, using its warm starting capabilities, using it to perform basic sensitivity analyses, and customizing it using callbacks. This part of the workshop can be customized according to audience interest, so participants are encouraged to provide feedback on desired topics ahead of time.

Title: COIN-OR Open Solver Interface

The COIN-OR Open Solver Interface provides C++ classes for accessing a variety of LP and MIP solvers using a single API. Calls are provided to read models from files or construct them in memory, modify them, invoke solvers, recover solution information, and write problems to files. We will describe features of the API and provide examples of its use. The long-term objective of the OSI project is to provide a portable, extensible prototype standard API for solvers for a variety of optimization problems

Andreas Waechter, IBM

Tutorial: Ipopt -- A Large-scale Nonlinear Optimization Solver

Ipopt is an open-source software package for large-scale nonlinear optimization. This tutorial will give users a practical introduction to effective usage of Ipopt.

We will start with a summary of the algorithm implemented in Ipopt, which is based on a primal-dual interior point method and uses a line search filter method to ensure convergence from a given starting point. Turning then to practical usage issues, we will discuss the installation, configuration and compilation process to obtain the Ipopt library and AMPL solver executable. Using a number of examples, we will demonstrate different ways to pose a nonlinear optimization problem (using the AMPL modeling language or using programming code). We will also go into the purpose of various options available in the code and discuss modeling issues, such as the effect of using different, but mathematically equivalent model formulations.

The tutorial will be hands-on, and the goal is to have each participant leave with a working installation of the package and some practical experience with Ipopt. Participants are strongly encouraged to try to install the package on their computer before the workshop (ideally with a recent version of the code), so that only installation difficulties and special options need to be discussed regarding the installation procedure, and more time can be spent on using the code. Also, if participants have already used Ipopt and have question regarding the solution of a particular optimization problem, they are encouraged to bring their model code.

Information about the Ipopt package, including download and installation instructions, is available at http://projects.coin-or.org/Ipopt . If you have a specific question you would like addressed during the tutorial, please send an email to andreasw@us.ibm.com (as early as possible).