Optimization Online


On the Consistent Path Problem

Leonardo Lozano(leolozano***at***uc.edu)
David Bergman(david.bergman***at***uconn.edu)
Cole Smith(jcsmith***at***clemson.edu)

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 utilize 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 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 a state-of-the-art algorithm for both.

Keywords: Flow algorithms; Generalized networks; Integer Programming

Category 1: Combinatorial Optimization (Other )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Integer Programming (0-1 Programming )

Citation: Institution: Clemson University, Department of Industrial Engineering, 100B Freeman Hall, Clemson, SC 29634

Download: [PDF]

Entry Submitted: 03/24/2018
Entry Accepted: 03/25/2018
Entry Last Modified: 03/24/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society