CIM PROGRAMS AND ACTIVITIES

Fields Industrial Optimization Seminar
2008-09

Ross Mitchell, University of Calgary

and

Andrew Hope, Princess Margaret Hospital Toronto

Matheus Grasselli, McMaster University

and

Helmut Mausser, Algorithmics Toronto

Audio and Slides of Talk

Michel X. Goemans, MIT
Approximating Submodular Functions Everywhere
Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. We consider the problem of approximating a non-negative, monotone, submodular function f everywhere, after only poly(n) oracle queries (where n is the size of the ground set). Our main result is a deterministic algorithm that makes poly(n) oracle queries and derives a function such that, for *every* set S, g(S) approximates f(S) within a factor a(n), where a(n)=sqrt(n+1) for rank functions of matroids and a(n)=O(sqrt(n) log(n)) for general monotone submodular functions. Our result is based on approximately finding a maximum volume inscribed ellipsoid in a symmetrized polymatroid, and the analysis involves various properties of submodular functions and polymatroids. Our algorithm is tight up to logarithmic factors, even for rank functions of a matroid.
Our approximation result allows to approximate optimization problems involving submodular functions, such as the submodular max-min fair allocation problem.
This is based on joint work with Nick Harvey, Satoru Iwata and Vahab Mirrokni.

Jon Lee, IBM TJ Watson Research Center
Nonlinear Combinatorial Optimization
I will discuss algorithms for solving problems of the form max { f(Wx) : x in F }, where f is a nonlinear function, the rows of the matrix W can be thought of as describing several linear objectives, and F is a discrete set of feasible solutions. The nonlinear function f can be though of as balancing the various linear objectives.We look at various combinatorial settings for the choices of F. So this can be seen to fit somewhere on the landscape between multicriteria optimization and nonlinear combinatorial optimization.
In the most general setting, the model is intractable, so we look at cases that yield polynomial-time algorithms and approximation schemes. Our specific results involve broad special cases. E.g., regarding F, we consider multi-knapsacks, matchings, matroids and polymatroids, Regarding f, we consider minimization of concave and convex functions, generalization of norms, etc. Regarding W, to get positive results, we usually need to assume that it has a fixed number of rows and the entries are encoded in unary.
I will describe an interesting application to fitting polynomial models to multivariate data.
Most of our algorithms were mainly designed for theoretical efficiency. Nonetheless, there is a good argument
for trying to implememt some of these methods on modern high-performance platforms. We describe such a successful effort for the model fitting application, using ultra-high precision solution of linear systems on the BlueGene supercomputer.
All of this is joint work, difererent parts with Berstein, Gunnels, Margulies, Maruri-Aguilar, Onn, Riccomagno, Weismantel, Wynn.

Audio and Slides of Talk

Endre Boros, Rutgers University
Quadratic binary optimization and its applications

Quadratic binary optimization (QUBO) is a natural mathematical model for numerous practical problems. In this overview lecture we recall the origins of this model, and some of the numerous results providing efficient solutions in some case, or efficient bounds and persistencies in some other cases. We shall also discuss connections to the very popular "graph-cut" approach of Computer vision, and provide extensive computational experiments with various applications.

Gabriel Tavares, Fair Isaac Corporation
Linear Programming Plus Branch-and-cut for Solving Certain Difficult QUBO Problems
A linear optimization framework is proposed to solve the Quadratic Unconstrained Binary Optimization (QUBO) problem. It consists of 3 stages: stage (i) calculates an incumbent solution by using QUBO heuristics (a Multi-Start Tabu-Search approach is considered); stage (ii) calculates an optimal Basic Feasible Solution (BFS) to the relaxation of the Linearization Model (LM) for QUBO plus some valid cuts; and stage (iii) solves the mixed integer program LM by using the incumbent solution and by enhancing it with the subset of cuts binding at the BFS. The effectiveness of the approach, implemented using Xpress-Mosel, is shown when solving: minimum 3-partition, MAX-CUT and nMAX-SAT.

Audio and Slides of Talk

Philip E. Gill, University of California, San Diego
What's new in SQP methods?
In his 1963 PhD thesis, Wilson proposed the first sequential quadratic programming (SQP) method for the solution of constrained nonlinear optimization problems. In the intervening 45 years, SQP methods have evolved into a powerful and effective class of methods for a wide range of optimization problems. We review some of the most prominent developments in SQP methods since 1963 and discuss the relationship of SQP methods to other popular methods, including augmented Lagrangian methods and interior methods.
Given the scope and utility of nonlinear optimization, it is not surprising that SQP methods are still a subject of active research. Recent developments in methods for mixed integer nonlinear programming and the minimization of functions subject to differential equation constraints has led to a heightened interest in methods that may be ``hot started'' from a good approximate solution. We discuss the role of SQP methods in this context, with particular reference to some recent enhancements to our large-scale SQP package SNOPT. We end with some discussion of the challenges associated with formulating algorithms that can exploit multicore and GPU-based computer architectures.

and

Bohdan Kaluzny, Centre for Operational Research & Analysis, Defence Research & Development Canada.
Combinatorial Optimization in Canadian Forces Airlift Modeling
The Canadian Forces make extensive use of strategic and tactical airlift assets to deploy and sustain overseas forces. Various-sized cargo aircraft are employed for missions to deliver equipment, supplies, and passengers. Maximizing the payload delivered per flight while maintaining a safe load balance is of high importance. This talk presents Genetic Annealing for Loading of Aircraft: a Heuristic Aiding Deployment (GALAHAD). This loading module uses a genetic algorithm based on a bin packing heuristic and a convex hull fitness function to generate realistic estimates of the number of airlift assets required to transport a given manifest of items. The generated load plans are subject to load balancing constraints which are modeled by Mixed Integer Linear Programming.