2022/06/26 by Lozano, Leonardo, Bergman, David, Cire, Andre A. · 1 citation
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2206.12962
Many discrete optimization problems are amenable to constrained shortest-path reformulations in an extended network space, a technique that has been key in convexification, bound strengthening, and search. In this paper, we propose a constrained variant of these models for two challenging classes of discrete two-stage optimization problems, where traditional methods (e.g., dualize-and-combine) are not applicable compared to their continuous counterparts. Specifically, we propose a framework that models problems as decision diagrams and introduces side constraints either as linear inequalities in the underlying polyhedral representation, or as state variables in shortest-path dynamic programming models. For our first structured class, we investigate two-stage problems with interdiction constraints. We show that such constraints can be formulated as indicator functions in the arcs of the diagram, providing an alternative single-level reformulation of the problem via a network-flow representation. Our second structured class is classical robust optimization, where we leverage the decision diagram network to iteratively identify label variables, akin to an L-shaped method. We evaluate these strategies on a competitive project selection problem and the robust traveling salesperson with time windows, observing considerable improvements in computational efficiency as compared to general methods in the respective areas.