東華大學圖書館 |

Interdiction and discrete bilevel linear programming.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Interdiction and discrete bilevel linear programming./
作者:	DeNegre, Scott.
面頁冊數:	1 online resource (184 pages)
附註:	Source: Dissertations Abstracts International, Volume: 72-12, Section: B.
Contained By:	Dissertations Abstracts International72-12B.
標題:	Industrial engineering. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3456385click for full text (PQDT)
ISBN:	9781124657288

Interdiction and discrete bilevel linear programming.
DeNegre, Scott.

Interdiction and discrete bilevel linear programming. - 1 online resource (184 pages)

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

Thesis (Ph.D.)--Lehigh University, 2011.

Includes bibliographical references

The primary focus of this dissertation is on hierarchical decision problems, a general problem class that allows incorporation of multiple decision-makers (DMs). A variety of real-world problems involve DMs with potentially conflicting objectives, and the assumption of a single DM limits the utility of standard models for such applications. In particular, we study problems with two levels for which a subset of the variables is required to take on integer values. In mathematical programming terminology, this problem is formalized as mixed integer bilevel program (MIBLP), and the variables are divided into groups defined by their controlling DM. A key component of these models is the dependence of the lower-level DM's feasible region on the upper-level solution. From this perspective, an MIBLP can be viewed as a mixed integer linear program (MILP) into which a second parametric MILP has been embedded. We focus our study on the theoretical properties of MIBLPs, in order to determine how its structure can be exploited for algorithm design. In addition, because of the computational challenges the general problem presents, we examine special cases that are more amenable to algorithmic development. The first such case is that of the pure integer bilevel linear program (IBLP). In the first portion of this work, we develop a branch-and-cut framework and an accompanying open source solver, MibS, for this problem class. Our algorithm can be seen as a generalization of the well-known branch-and-cut algorithm for MILP, but invokes specialized cutting planes to separate solutions that satisfy integrality constraints, but are bilevel infeasible. After developing our pure integer framework, we return to the general case and examine its computational complexity and place it within the so-called polynomial hierarchy. Next, we examine the extent to which methods developed for the well-studied continuous version of the problem (BLP) can be extended to MIBLP. The majority of BLP solution methods rely on the assumption that all decision variables are continuous and, thus, cannot be readily applied to the mixed integer case. However, in an effort to bridge this gap, we use intuition gained from studying the relationship between linear programs (LPs) and MILPs. In particular, we draw heavily on the recently-developed mixed integer extensions of LP duality theory to develop single-level reformulations of MIBLP. For some particular special cases, these methods yield problems to which known methods can be applied, but the general reformulation requires the application of the subadditive dual, and cannot solved directly. In order to overcome this, we use approximations of the lower-level value function to derive an exact algorithm reminiscent of Benders' decomposition and the integer L-shaped method. The inherent difficulty of these problem means that finding exact solutions to large instances will likely be prohibitively expensive. Thus, we provide two heuristic methods, each of which attempts to balance upper- and lower-level optimality, that can be used to be find good solutions to general problems with little computational effort. In the final section of this dissertation, we study an application in critical infrastructure protection, namely that of designing an early warning system to monitor the structural integrity of a municipal water system. The Steiner arborescence problem used to determine the optimal placement of acoustic sensors within the system is described, and a novel cutting plane algorithm is presented. Then, using this model as illustrative example, we demonstrate the utility of interdiction problems in performing a type of systematic sensitivity analysis of our optimal design to the underlying graph structure. Interdiction problems, a class of MIBLPs used to model the effect that can be exerted on an MILP through variable bound altercation are of particular interest in our work for a number of reasons, most notably their applicability for problems in homeland security and unique problem structure. We describe several methods based on this special structure and show how one might develop a problem-specific customization for MibS.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2023

Mode of access: World Wide Web

ISBN: 9781124657288Subjects--Topical Terms:

526216
Industrial engineering.
Subjects--Index Terms:

Algorithmic game theoryIndex Terms--Genre/Form:

542853
Electronic books.

Interdiction and discrete bilevel linear programming.
LDR:05621nmm a2200409K 4500 001 2363704
005 20231127093625.5
006 m o d
007 cr mn ---uuuuu
008 241011s2011 xx obm 000 0 eng d
020 $a 9781124657288
035 $a (MiAaPQ)AAI3456385
035 $a (MiAaPQ)lehigh:10513
035 $a AAI3456385
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a DeNegre, Scott. $3 3704481
245 1 0 $a Interdiction and discrete bilevel linear programming.
264 0 $c 2011
300 $a 1 online resource (184 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 72-12, Section: B.
500 $a Publisher info.: Dissertation/Thesis.
500 $a Advisor: Ralphs, Ted.
502 $a Thesis (Ph.D.)--Lehigh University, 2011.
504 $a Includes bibliographical references
520 $a The primary focus of this dissertation is on hierarchical decision problems, a general problem class that allows incorporation of multiple decision-makers (DMs). A variety of real-world problems involve DMs with potentially conflicting objectives, and the assumption of a single DM limits the utility of standard models for such applications. In particular, we study problems with two levels for which a subset of the variables is required to take on integer values. In mathematical programming terminology, this problem is formalized as mixed integer bilevel program (MIBLP), and the variables are divided into groups defined by their controlling DM. A key component of these models is the dependence of the lower-level DM's feasible region on the upper-level solution. From this perspective, an MIBLP can be viewed as a mixed integer linear program (MILP) into which a second parametric MILP has been embedded. We focus our study on the theoretical properties of MIBLPs, in order to determine how its structure can be exploited for algorithm design. In addition, because of the computational challenges the general problem presents, we examine special cases that are more amenable to algorithmic development. The first such case is that of the pure integer bilevel linear program (IBLP). In the first portion of this work, we develop a branch-and-cut framework and an accompanying open source solver, MibS, for this problem class. Our algorithm can be seen as a generalization of the well-known branch-and-cut algorithm for MILP, but invokes specialized cutting planes to separate solutions that satisfy integrality constraints, but are bilevel infeasible. After developing our pure integer framework, we return to the general case and examine its computational complexity and place it within the so-called polynomial hierarchy. Next, we examine the extent to which methods developed for the well-studied continuous version of the problem (BLP) can be extended to MIBLP. The majority of BLP solution methods rely on the assumption that all decision variables are continuous and, thus, cannot be readily applied to the mixed integer case. However, in an effort to bridge this gap, we use intuition gained from studying the relationship between linear programs (LPs) and MILPs. In particular, we draw heavily on the recently-developed mixed integer extensions of LP duality theory to develop single-level reformulations of MIBLP. For some particular special cases, these methods yield problems to which known methods can be applied, but the general reformulation requires the application of the subadditive dual, and cannot solved directly. In order to overcome this, we use approximations of the lower-level value function to derive an exact algorithm reminiscent of Benders' decomposition and the integer L-shaped method. The inherent difficulty of these problem means that finding exact solutions to large instances will likely be prohibitively expensive. Thus, we provide two heuristic methods, each of which attempts to balance upper- and lower-level optimality, that can be used to be find good solutions to general problems with little computational effort. In the final section of this dissertation, we study an application in critical infrastructure protection, namely that of designing an early warning system to monitor the structural integrity of a municipal water system. The Steiner arborescence problem used to determine the optimal placement of acoustic sensors within the system is described, and a novel cutting plane algorithm is presented. Then, using this model as illustrative example, we demonstrate the utility of interdiction problems in performing a type of systematic sensitivity analysis of our optimal design to the underlying graph structure. Interdiction problems, a class of MIBLPs used to model the effect that can be exerted on an MILP through variable bound altercation are of particular interest in our work for a number of reasons, most notably their applicability for problems in homeland security and unique problem structure. We describe several methods based on this special structure and show how one might develop a problem-specific customization for MibS.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2023
538 $a Mode of access: World Wide Web
650 4 $a Industrial engineering. $3 526216
650 4 $a Systems science. $3 3168411
653 $a Algorithmic game theory
653 $a Bilevel programming
653 $a Comptutational optimization
653 $a Integer programming
655 7 $a Electronic books. $2 lcsh $3 542853
690 $a 0546
690 $a 0790
690 $a 0796
710 2 $a ProQuest Information and Learning Co. $3 783688
710 2 $a Lehigh University. $b Industrial Engineering. $3 2092122
773 0 $t Dissertations Abstracts International $g 72-12B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3456385 $z click for full text (PQDT)