Journées de l'optimisation 2016
HEC Montréal, Québec, Canada, 2 — 4 mai 2016
TB3 Decomposition Methods in Optimization
3 mai 2016 15h30 – 17h10
Salle: EY
Présidée par Jean Bertrand Gauthier
4 présentations

15h30  15h55
A contractionexpansion algorithm for network flow problems
With respect to network flow problems, the order in which negative cycles are canceled defines the algorithm used for the resolution. It apparently also plays a role in dictating the time complexity of the latter. The minimum mean cyclecanceling algorithm and CancelandTighten are prime examples of strongly polynomial algorithms. We discuss facets of the analysis and extract fundamental aspects that explain this behavior. A ContractionExpansion algorithm is proposed alongside comparative results.

15h55  16h20
A column generation postoptimization heuristic for the integrated aircraft and passenger recovery problem
The joint aircraft and passenger recovery problem is modeled as a mixed integer program and a column generation postoptimization heuristic is proposed. We show how the model and the heuristic can be modified to consider passenger recovery only. The resulting heuristic improves the best known solutions for all instances of the 2009 ROADEF Challenge, within reasonable computing times.

16h20  16h45
2Dphase unwrapping and operations research
Phase unwrapping is the problem of recovering a continuousphase signal from an original signal wrapped in the ]Pi,Pi] interval. We formulate this problem as the search for a minimumcost balanced spanning forest in a graph where the vertices represent the residues of the wrapped phase, and introduce branchandcut, column generation and metaheuristic approaches.

16h45  17h10
Projection methods and nonlinear constraint shape
Projection methods for seeking feasibility are normally applied to convex sets of constraints, or as heuristics when the convexity is unknown. We develop ways to estimate the shapes (linear, convex, nonconvex, both) of nonlinear constraints as the projection algorithm runs and use this information to accelerate the solution.