Journées de l'optimisation 2018

HEC Montréal, Québec, Canada, 7 — 9 mai 2018

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

MB3 Linear programming

7 mai 2018 15h30 – 17h10

Salle: EY (69)

Présidée par Andre Augusto Cire

4 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h30 - 15h55

    LP-based sparse solutions revisited

    • John Chinneck, prés., Carleton University

    Finding sparse solutions for underdetermined linear systems is the key step in compressive sensing and a number of other important problems. One category of solutions uses linear programming, e.g. Basis Pursuit. However there are other ways to formulate the LP which have not been explored and which lead to different algorithms with different characteristics. The talk presents a variety of new LP-based formulations and associated algorithms, along with numerical evaluation and comparisons.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h55 - 16h20

    On integrating mixed-integer programming and decision diagrams for optimization

    • Jaime Gonzalez, prés., Polytecnique Montréal
    • Andre Augusto Cire, University of Toronto
    • Andrea Lodi, Polytechnique Montréal
    • Louis-Martin Rousseau, Polytechnique Montréal

    In this talk, we propose an optimization framework which combines mixed-integer linear programming and decision diagrams to solve combinatorial optimization problems. We address the classical maximum independent set problem where the proposed hybrid approach integrates complementary strengths to exploit a suitable structure and solve the problem.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h20 - 16h45

    A local search framework for compiling relaxed decision diagrams

    • Michael Roemer, prés., CIRRELT
    • Andre Augusto Cire, University of Toronto
    • Louis-Martin Rousseau, Polytechnique Montréal

    We present a local search framework for constructing and improving relaxed decision diagrams (DDs). The framework consists of a set of elementary DD manipulation operations including a redirect operation introduced in this paper and a general algorithmic scheme. We show that the framework can be used to reproduce several standard DD compilation schemes and to create new compilation and improvement strategies. In computational experiments for the 0-1 knapsack problem, the multidimensional knapsack problem and the set covering problem we compare different compilation methods. It turns out that a new strategy based on the local search framework consistently yields better bounds, in many cases far better bounds, for limited-width DDs than previously published heuristic strategies.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h45 - 17h10

    Network-based approximate linear programming for discrete optimization

    • Andre Augusto Cire, prés., University of Toronto
    • Selvaprabu Nadarajah, University of Illinois at Chicago

    We present a new hierarchy of approximate linear programming methods for a general class of discrete optimization problems. In particular, our hierarchy considers network-based relaxations as basis functions. A numerical evaluation is discussed on challenging discrete optimization problems arising in practice.