2016 Optimization Days

HEC Montréal, Québec, Canada, May 2 — 4, 2016

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TB3 Decomposition Methods in Optimization

May 3, 2016 03:30 PM – 05:10 PM

Location: EY

Chaired by Jean Bertrand Gauthier

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    03:30 PM - 03:55 PM

    A contraction-expansion algorithm for network flow problems

    • Jean-Bertrand Gauthier, presenter, GERAD - HEC Montréal
    • Jacques Desrosiers, GERAD, HEC Montréal

    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 cycle-canceling algorithm and Cancel-and-Tighten are prime examples of strongly polynomial algorithms. We discuss facets of the analysis and extract fundamental aspects that explain this behavior. A Contraction-Expansion algorithm is proposed alongside comparative results.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    03:55 PM - 04:20 PM

    A column generation post-optimization heuristic for the integrated aircraft and passenger recovery problem

    • Karine Sinclair, presenter, HEC Montréal
    • Gilbert Laporte, HEC Montréal
    • Jean-François Cordeau, GERAD - HEC Montréal

    The joint aircraft and passenger recovery problem is modeled as a mixed integer program and a column generation post-optimization 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    04:20 PM - 04:45 PM

    2D-phase unwrapping and operations research

    • Thibaut Vidal, presenter, PUC-Rio - Pontifical Catholic University of Rio de Janeiro
    • Ian Herszterg, Pontifical Catholic University of Rio de Janeiro
    • Marcus Poggi, Pontifical Catholic University of Rio de Janeiro

    Phase unwrapping is the problem of recovering a continuous-phase signal from an original signal wrapped in the ]-Pi,Pi] interval. We formulate this problem as the search for a minimum-cost balanced spanning forest in a graph where the vertices represent the residues of the wrapped phase, and introduce branch-and-cut, column generation and metaheuristic approaches.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    04:45 PM - 05:10 PM

    Projection methods and nonlinear constraint shape

    • John Chinneck, presenter, Carleton University

    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.

Back