New Techniques for Discrete Optimization

Author: 

David Bergman

School: 

Tepper School of Business, Carnegie Mellon University

Supervisors: 

J.N. Hooker
Willem-Jan van Hoeve

Abstract: 

Objective function bounds are critical to solving discrete optimization problems. In this thesis, we explore several new techniques for obtaining bounds, and also describe a new branch-and-bound algorithm for discrete optimization problems.

The first area explored is the application of decision diagrams (DDs) to binary optimization problems. In recent years, DDs have been applied to various problems in operations research. These include sequential pattern data mining, cut generation, product configuration, and post-optimality analysis in integer programming, to name a few. Through these applications and others, DDs have proven to be a useful tool for a variety of tasks. Unfortunately, DDs may grow exponentially large, prohibiting their use.

To overcome this difficulty, we introduce the notion of limited-width approximate decision diagrams for discrete optimization problems. By limiting the width of a decision diagram, the size of the data structure can be controlled to the level of accuracy desired.

Discussed in this dissertation is the use of approximate DDs as problem relaxations and restrictions of the feasible set. We introduce top-down compilation algorithms for approximate DDs and discuss how they can be used to generate both upper and lower bounds on the optimal value for any separable objective function.

We then discuss how relaxed and restricted DDs can be used together to create a DD-based branch-and-bound algorithm. The algorithm differs substantially from traditional branch-and-bound algorithms on this class of problems in several important ways. First, relaxed DDs provide a discrete relaxation, as opposed to a continuous relaxation (for example a linear programming relaxation), which is typically employed. In addition, subproblems are generated by branching on several partial solutions taken at once, thereby eliminating certain symmetry from the search. We discuss the application of the algorithm to the classical maximum independent set problem. Computational results show that the algorithm is competitive with state-of-the-art integer programming technology.

The next area explored is the idea of obtaining valid inequalities for a 0-1 model from a constraint programming formulation of the problem. In particular, we formulate a graph coloring problem as a system of all-different constraints. By analyzing the polyhedral structure of all-different systems, we obtain facet-defining inequalities that can be mapped to valid cuts in the classical 0-1 model of the problem.

We employ a common strategy for generating problem-specific cuts: the identification of facet-defining cuts for special types of induced subgraphs, such as odd-holes, webs, and paths. We identify cuts that bound the objective function as well as cuts that exclude infeasible solutions.

One structure that we focus on is cyclic structures and show that the cuts we obtain are stronger than previously known cuts. For example, when an existing separation algorithm identifies odd-hole cuts, we can supply stronger cuts with no additional calculation. In addition, we generalize odd-hole cuts to odd-cycle cuts that are stronger than any collection of odd-hole cuts. We also identify cuts associated with intersecting systems, for which there are no previously known 0-1 cuts, to the best of our knowledge.

Graduated: 

Tuesday, May 19, 2015

PDF of thesis: