← Search

On the Consistent Path Problem

Leonardo Lozano¹; David Bergman²; J. Cole Smith³

¹ Operations, Business Analytics & Information Systems, University of Cincinnati, Cincinnati, Ohio 45221; · ² Operations and Information Management, University of Connecticut, Storrs, Connecticut 06260; · ³ Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, New York 13210

This paper studies a novel decomposition scheme, utilizing decision diagrams for modeling elements of a problem where typical linear relaxations fail to provide sufficiently tight bounds. Given a collection of decision diagrams, each representing a portion of the problem, together with linear inequalities modeling other portions of the problem, how can one efficiently optimize over such a representation? In this paper, we model the problem as a consistent path problem, where a path in each diagram has to be identified, all of which agree on the value assignments to variables. We establish complexity results and propose a branch-and-cut framework for solving the decomposition. Through application to binary cubic optimization and a variant of the market split problem, we show that the decomposition approach provides significant improvement gains over standard linear models.

DOI

10.1287/opre.2020.1979

Volume

68 (6)

Pages

1913-1931

Language

en

Export

BibTeX

Sources

crossref openalex