4 Presentations

• 
  03:30 PM - 03:55 PM

  LP-based sparse solutions revisited

  • John Chinneck, presenter, 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.

• 
  03:55 PM - 04:20 PM

  On integrating mixed-integer programming and decision diagrams for optimization

  • Jaime Gonzalez, presenter, Polytecnique Montréal
  • Andre Augusto Cire, University of Toronto
  • Andrea Lodi, Polytechnique Montreal
  • 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.

• 
  04:20 PM - 04:45 PM

  A local search framework for compiling relaxed decision diagrams

  • Michael Roemer, presenter, 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.

• 
  04:45 PM - 05:10 PM

  Network-based approximate linear programming for discrete optimization

  • Andre Augusto Cire, presenter, 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.