- map -

Alexander Bockmayr -FU Berlin and DFG Research Center Matheon

Discrete optimization problems in structural biology

Abstract: Structural biology is concerned with the three-dimensional structure of biological macromolecules (in particular proteins and nucleic acids). In the first part of the talk, I will give an overview of discrete optimization problems in structural biology, related to structure prediction, structure comparison or to interactions between macromolecular structures.

In the second part, I will present an integer programming approach to the phase problem in X-ray crystallography (joint work with V. Lunin and A. Urshumtsev).

Colloquium - 16:00

José Neto -INT Évry

Acceleration of cutting plane algorithms

Abstract: When solving linear programs with a large number of constraints, constraint generation procedures are often used. Basically these techniques consist in first solving a relaxation containing a subset of constraints of a complete formulation. Then a separation oracle is called in order to add to the relaxation any inequality of the formulation that is violated by the current solution. This process is iterated until no violated inequality can be found.

Since the algorithm introduced by Dantzig, Fulkerson and Johnson in the mid-1950's, many research efforts have been made to improve their efficiency, leading to the resolution of larger and larger scale problems. After a survey on constraint generation procedures developped so far, we focus on two algorithms investigated recently.

The first one, entitled In-Out algorithm, is a simple modification of the basic scheme decribed above. Assuming a feasible solution x_feas is known, and that the current optimal solution of the relaxation is x^*, it basically consists in using a point that is defined as a convex combination of x_feas and x^*, to generate constraints. The performance of such procedures is illustrated on some specific families of linear programs: survivable network design, multicommodity flow problems and LPs randomly generated, namely.

Another approach to be presented involves multiple-points separation, which somewhat generalizes classical procedures since it basically consists in using several points to generate constraints, in lieu of a single one. Some theoretical features (algorithmic structure, complexity) regarding the latter approach are discussed and preliminary computational results are reported.