Report on the 3ème Cycle Romand de Recherche Opérationnelle (Zinal, March 4-6,2001)

Optimisation robuste et problèmes de complémentarité non linéraire

The seminar organized each year by the "3ème Cycle Romand de Recherche Opérationnelle" took place in the village of Zinal. The 25 participants coming from EPFs Lausanne and Zürich, University of Zürich (IOR), Fribourg (DIUF) and Genève (HEC/Logilab) attended this spring seminar. Two invited speakers have presented recent research results. These speakers were :

Prof. Aharon Ben-Tal, William Davidson Faculty of Industrial Engineering and Management Technion - Israel Institute of Technology
Modern Convex Optimization in Engineering Design

Prof. Michael C. Ferris, Computer Sciences Department University of Wisconsin, Madison, Wisconsin
Formulation, Modeling and Solution: a Nonlinear Perspective

Aharon Ben-Tal started with one of the basic problems of engineering which reads as follows: for a given set of boundary conditions and a given set of loads, find the stiffest structure of a given volume that is able to carry the loads. The desired optimal structure under consideration may be a two- or three-dimensional continuum elastic body or a truss structure, and the design variables may be the shape variables (set of nodes obtained by discretizing the body on one hand, connectivity pattern on the other hand) and/or the sizing variables (e.g., thickness of bars in a truss or material density). The most general formulation is refered to as layout optimization and leads to very large-scale nonlinear nonconvex problems. The speaker showed that under reasonable assumptions, the general structural design problem can be posed as a semi-definite program. This conclusion was the opportunity to present modern convex optimization based on a conic approach. Duality theory for linear programming can be expressed in a nicely similar way for nonlinear programming provided that nonlinearity is described by a cone to which variables belong.

Aharon Ben-Tal mentioned incidentally to what extent semi-definite programming bridges the gap between mathematical programming and combinatorial optimization: the SDP relaxation yields for knapsack programs a much better lower bound than LP relaxation, as shown by Wiliamson et al. Other lectures were devoted to robust convex optimization. Our speaker showed that the robust counterpart of an uncertain linear program can be formulated as a conic quadratic program, and that the robust counterpart of an uncertain quadratically constrained quadratic program can be formulated as a SDP. The scope of application of robust programming is very broad. Some examples related to multi-loaded truss topology design as well as to the antenna synthesis problems showed its practical interest, as well at the modeling level (uncertainty of data) as at the user level (inaccuracy of solutions implementation): it allows one to find and implement solutions which are not too much sensitive to perturbations. The speaker observed that, after his experience, optimal objective values of robust formulations were often pretty close to optimal values of nonrobust formulations: this is clearly an incentive to apply robust optimization techniques.

Lastly, to convince us definitively of the interest of robust optimization, Aharon Ben-tal mentioned published results about the poor behavior of CPLEX for linear problem of the NETLIB collection once those problems were slightly perturbated, whereas the application of a "robust optimizer" to those perturbated problems yielded much better solutions.

As an introduction to complementarity problems, Michael Ferris began with presenting a simple linear transportation model. The first order optimality conditions of this problem can be written as complementarity conditions in a natural way. Without loss of generality, the speaker nonetheless demonstrated on the basis of this model that the complementarity format encompasses a wider scope of models than optimization models. Indeed, dual variables can explicitly be handled so that they can be entered, in a fancy way, in equations which involve primal variables. This proves useful in a number of economic applications whenever taxes are made endogenous for example. More generally, applications of mixed complementarity problems include options pricing, contact problems with friction, general equilibirum with incomplete market, markets deregulation etc... Michael Ferris then presented with some details an original implementation of the Newton method in PATH, a solver dedicated to solving nonlinear complementarity problems. PATH is hooked to GAMS and AMPL modeling languages, through which complementarity problems can be formulated in an explicit way or derived from first order optimality conditions. This modeling framework makes the use of PATH quite easy, as demonstrated by the speaker for a number of applications arising in economics, such as the modeling of the world dairy market for example.

More generally, the speaker highlighted the fact that the increase in computation power and the exploitation of problems structure open new areas of application. An interesting example was given in real-time applications such as the automatization of the treatment planning process in radiosurgery on one hand, or the separation problem over sixty millions of data sets on the other hand. Lastly, Michael Ferris presented CONDOR, a management tool based on the premise that most workstations are severely under-utilized, in order to show that the ability to perform optimization in parallel is within reach of the scientific community by using modeling languages in a simple way. We had the opportunity to get an insight into some of our colleagues' research fields. Olivier Epelly, from UniGE, talked about its Implementation of an interior point method for smooth convex programming with an application to large-scale economic economic and engineering problems. Carlos Azmat, from UniFr, talked about Scheduling a workforce under annualized hours taking into account holidays weeks.

As always, the dinners were privileged moments of discussion in a relaxed atmosphere. We were pretty lucky since we could enjoy the sunny weather on the ski slopes.

Lastly, we would like to thank the President of the 3e Cycle Romand de Recherche Opérationnelle, Monsieur Alain Prodon, for organizing the meeting.

Olivier Epelly
olivier.epelly@hec.unige.ch