On the consistent path problem

Leonardo Lozano, David Bergman, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1913-1931
Number of pages19
JournalOperations Research
Volume68
Issue number6
DOIs
StatePublished - Nov 2020

Keywords

  • Algorithms
  • Networks/graphs: flow algorithms
  • Networks/graphs: generalized networks
  • Programming: integer

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'On the consistent path problem'. Together they form a unique fingerprint.

Cite this