Formulations and Valid Inequalities for Network Interdiction Problems and Reverse Convex Sets

Download or read book Formulations and Valid Inequalities for Network Interdiction Problems and Reverse Convex Sets written by Eli Towle and published by . This book was released on 2019 with total page 165 pages. Available in PDF, EPUB and Kindle. Book excerpt: We consider two research projects related to mixed-integer and nonconvex programming. We begin by presenting new solution approaches for the maximum-reliability stochastic network interdiction problem (SNIP). In SNIP, a defender interdicts arcs on a directed graph, reducing the probability of an attacker's undetected traversal through those arcs. The attacker's origin and destination are unknown to the defender. The attacker then selects the maximum-reliability path through the network. The defender seeks to minimize the expected reliability of this path. SNIP can be formulated as a deterministic mixed-integer linear program. Current approaches to solving SNIP rely on modifications of Benders decomposition. We reformulate the existing extensive formulation to be significantly more compact. We then present a new path-based formulation of SNIP. We introduce valid inequalities to embed in a branch-and-cut (BC) algorithm to solve this path-based formulation. Directly solving the compact SNIP formulation and this BC algorithm demonstrate improvement over a state-of-the-art Benders implementation for SNIP. Next, we present new approaches to obtain valid inequalities for a reverse convex set, which is defined as the set of points in a polyhedron that lie outside a given open convex set. We are motivated by cases where the closure of the convex set is either non-polyhedral, or is defined by too many inequalities to directly apply disjunctive programming. Reverse convex sets arise in many models, including bilevel optimization and polynomial optimization. Intersection cuts are a well-known method for generating valid inequalities for a reverse convex set. Intersection cuts are generated from a basic solution that lies within the convex set. Our contribution is a framework for deriving valid inequalities for the reverse convex set from basic solutions that lie outside the convex set. We begin by proposing an extension to intersection cuts that defines a two-term disjunction for a reverse convex set. We refer to such a disjunction as an intersection disjunction. Next, we generalize this analysis to a multi-term disjunction by considering the convex set's recession directions. These disjunctions can be used in a cut-generating linear program to obtain valid inequalities for the reverse convex set. We continue investigating valid inequalities for optimization problems containing a reverse convex structure. So far, we have only considered methods for generating valid inequalities for such problems that rely on pointed relaxations of the polyhedron defining the reverse convex set that are formed by exactly n constraints. We present a framework to obtain valid inequalities for these problems from non-pointed relaxations of the polyhedron. We start by deriving a two-term disjunction for the reverse convex set using non-pointed relaxations formed by n constraints. We then generalize this and a previously presented two-term disjunction to relaxations of the polyhedron that are formed by more than n constraints. Finally, we present a two-term disjunction for the reverse convex set that is generated by a relaxation of the polyhedron formed by less than n constraints. We present a valid inequality for each disjunctive term and show that it defines the convex hull of the disjunctive term. We conclude by briefly investigating topics related to the convergence of intersection cuts for reverse convex sets. It is currently unknown whether cutting plane algorithms that are based purely on standard intersection cuts can be guaranteed to converge in a finite number of iterations to optimal solutions of optimization problems defined by reverse convex sets. Such a result has practical algorithmic consequences. If the result does hold, certain cutting plane algorithms could be proven to finitely converge to an optimal solution for problems with a reverse convex structure. We show that cutting plane algorithms based on standard intersection cuts can converge to the optimal solution of reverse convex optimization problems set in two dimensions. We then show that this does not hold in general for problems in three dimensions. To conclude, we conjecture that cutting plane algorithms for reverse convex optimization that add all possible intersection cuts at each iteration converge to the optimal solution of the problem in the limit. We show that this conjecture holds if the sequence of relaxations produced by such cutting plane algorithms converges to a polyhedron.