On the Consistent Path Problem

Leonardo Lozano (), David Bergman () and J. Cole Smith ()
Additional contact information
Leonardo Lozano: Operations, Business Analytics & Information Systems, University of Cincinnati, Cincinnati, Ohio 45221
David Bergman: Operations and Information Management, University of Connecticut, Storrs, Connecticut 06260
J. Cole Smith: Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, New York 13210

Operations Research, 2020, vol. 68, issue 6, 1913-1931

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.

Keywords: networks/graphs: flow algorithms; networks/graphs: generalized networks; programming: integer; algorithms (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/opre.2020.1979 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:6:p:1913-1931

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().