東華大學圖書館 |

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

Record Type:	Electronic resources : Monograph/item
Title/Author:	Formulations and Valid Inequalities for Network Interdiction Problems and Reverse Convex Sets./
Author:	Towle, Eli.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2019,
Description:	179 p.
Notes:	Source: Dissertations Abstracts International, Volume: 80-12, Section: B.
Contained By:	Dissertations Abstracts International80-12B.
Subject:	Applied Mathematics. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=13897375
ISBN:	9781392243060

Formulations and Valid Inequalities for Network Interdiction Problems and Reverse Convex Sets.
Towle, Eli.

Formulations and Valid Inequalities for Network Interdiction Problems and Reverse Convex Sets. - Ann Arbor : ProQuest Dissertations & Theses, 2019 - 179 p.

Source: Dissertations Abstracts International, Volume: 80-12, Section: B.

Thesis (Ph.D.)--The University of Wisconsin - Madison, 2019.

This item must not be sold to any third party vendors.

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.

ISBN: 9781392243060Subjects--Topical Terms:

1669109
Applied Mathematics.

Formulations and Valid Inequalities for Network Interdiction Problems and Reverse Convex Sets.
LDR:05627nmm a2200337 4500 001 2210855
005 20191121124322.5
008 201008s2019 ||||||||||||||||| ||eng d
020 $a 9781392243060
035 $a (MiAaPQ)AAI13897375
035 $a (MiAaPQ)wisc:16226
035 $a AAI13897375
040 $a MiAaPQ $c MiAaPQ
100 1 $a Towle, Eli. $3 3437997
245 1 0 $a Formulations and Valid Inequalities for Network Interdiction Problems and Reverse Convex Sets.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2019
300 $a 179 p.
500 $a Source: Dissertations Abstracts International, Volume: 80-12, Section: B.
500 $a Publisher info.: Dissertation/Thesis.
500 $a Advisor: Luedtke, James.
502 $a Thesis (Ph.D.)--The University of Wisconsin - Madison, 2019.
506 $a This item must not be sold to any third party vendors.
520 $a 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.
590 $a School code: 0262.
650 4 $a Applied Mathematics. $3 1669109
650 4 $a Industrial engineering. $3 526216
650 4 $a Computer science. $3 523869
690 $a 0364
690 $a 0546
690 $a 0984
710 2 $a The University of Wisconsin - Madison. $b Industrial Engineering. $3 2093809
773 0 $t Dissertations Abstracts International $g 80-12B.
790 $a 0262
791 $a Ph.D.
792 $a 2019
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=13897375