03:30 PM - 03:55 PM
LP-based sparse solutions revisited
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
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
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
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.