Name
Abstract | ||
|---|---|---|
The application of decision diagrams in combinatorial optimization has proliferated in the last decade. In recent years, authors have begun to investigate how to use not one, but a set of diagrams, to model constraints and objective function terms. Optimizing over a collection of decision diagrams, the problem we refer to as the consistent path problem (CPP) can be addressed by associating a network-flow model with each decision diagram, jointly linked through channeling constraints. A direct application of integer programming to the ensuing model has already been shown to result in algorithms that provide orders-of-magnitude performance gains over classical methods. Lacking, however, is a careful study of dedicated solution methods designed to solve the CPP. This paper provides a detailed study of the CPP, including a discussion on complexity results and a complete polyhedral analysis. We propose a cut-generation algorithm, which, under a structured ordering property, finds a cut, if one exists, through an application of the classical maximum flow problem, albeit in an exponentially sized network. We use this procedure to fuel a cutting-plane algorithm that is applied to unconstrained binary cubic optimization and a variant of the market split problem, resulting in an algorithm that compares favorably with CPLEX, using standard integer programming formulations for both problems. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1287/opre.2020.1979 | OPERATIONS RESEARCH |
Keywords | DocType | Volume |
networks/graphs: flow algorithms,networks/graphs: generalized networks,programming: integer,algorithms | Journal | 68 |
Issue | ISSN | Citations |
6 | 0030-364X | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Leonardo Lozano | 1 | 0 | 1.69 |
| David Bergman | 2 | 37 | 7.54 |
| J. Cole Smith | 3 | 610 | 43.34 |