東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

New Techniques for Discrete Optimiza...

Bergman, David.

Linked to FindBook

Google Book

Amazon

博客來

New Techniques for Discrete Optimization.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	New Techniques for Discrete Optimization./
Author:	Bergman, David.
Description:	230 p.
Notes:	Source: Dissertation Abstracts International, Volume: 74-12(E), Section: B.
Contained By:	Dissertation Abstracts International74-12B(E).
Subject:	Operations Research. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3573511
ISBN:	9781303437083

New Techniques for Discrete Optimization.
Bergman, David.

New Techniques for Discrete Optimization. - 230 p.

Source: Dissertation Abstracts International, Volume: 74-12(E), Section: B.

Thesis (Ph.D.)--Carnegie Mellon University, 2013.

Objective function bounds are critical to solving discrete optimization problems. In this thesis, we explore several new techniques for obtaining bounds, and also describe a new branch-and-bound algorithm for discrete optimization problems.

ISBN: 9781303437083Subjects--Topical Terms:

626629
Operations Research.

New Techniques for Discrete Optimization.
LDR:04318nam a2200373 4500 001 1958938
005 20140512081854.5
008 150210s2013 ||||||||||||||||| ||eng d
020 $a 9781303437083
035 $a (MiAaPQ)AAI3573511
035 $a AAI3573511
040 $a MiAaPQ $c MiAaPQ
100 1 $a Bergman, David. $3 2094190
245 1 0 $a New Techniques for Discrete Optimization.
300 $a 230 p.
500 $a Source: Dissertation Abstracts International, Volume: 74-12(E), Section: B.
500 $a Advisers: J.N. Hooker; Willen-Jan van Hoeve.
502 $a Thesis (Ph.D.)--Carnegie Mellon University, 2013.
520 $a Objective function bounds are critical to solving discrete optimization problems. In this thesis, we explore several new techniques for obtaining bounds, and also describe a new branch-and-bound algorithm for discrete optimization problems.
520 $a The first area explored is the application of decision diagrams (DDs) to binary optimization problems. In recent years, DDs have been applied to various problems in operations research. These include sequential pattern data mining, cut generation, product configuration, and post-optimality analysis in integer programming, to name a few. Through these applications and others, DDs have proven to be a useful tool for a variety of tasks. Unfortunately, DDs may grow exponentially large, prohibiting their use.
520 $a To overcome this difficulty, we introduce the notion of limited-width approximate decision diagrams for discrete optimization problems. By limiting the width of a decision diagram, the size of the data structure can be controlled to the level of accuracy desired.
520 $a Discussed in this dissertation is the use of approximate DDs as problem relaxations and restrictions of the feasible set. We introduce top-down compilation algorithms for approximate DDs and discuss how they can be used to generate both upper and lower bounds on the optimal value for any separable objective function.
520 $a We then discuss how relaxed and restricted DDs can be used together to create a DD-based branch-and-bound algorithm. The algorithm differs substantially from traditional branch-and-bound algorithms on this class of problems in several important ways. First, relaxed DDs provide a discrete relaxation, as opposed to a continuous relaxation (for example a linear programming relaxation), which is typically employed. In addition, subproblems are generated by branching on several partial solutions taken at once, thereby eliminating certain symmetry from the search. We discuss the application of the algorithm to the classical maximum independent set problem. Computational results show that the algorithm is competitive with state-of-the-art integer programming technology.
520 $a The next area explored is the idea of obtaining valid inequalities for a 0-1 model from a constraint programming formulation of the problem. In particular, we formulate a graph coloring problem as a system of all-different constraints. By analyzing the polyhedral structure of all-different systems, we obtain facet-defining inequalities that can be mapped to valid cuts in the classical 0-1 model of the problem.
520 $a We employ a common strategy for generating problem-specific cuts: the identification of facet-defining cuts for special types of induced subgraphs, such as odd-holes, webs, and paths. We identify cuts that bound the objective function as well as cuts that exclude infeasible solutions.
520 $a One structure that we focus on is cyclic structures and show that the cuts we obtain are stronger than previously known cuts. For example, when an existing separation algorithm identifies odd-hole cuts, we can supply stronger cuts with no additional calculation. In addition, we generalize odd-hole cuts to odd-cycle cuts that are stronger than any collection of odd-hole cuts. We also identify cuts associated with intersecting systems, for which there are no previously known 0-1 cuts, to the best of our knowledge.
590 $a School code: 0041.
650 4 $a Operations Research. $3 626629
650 4 $a Computer Science. $3 626642
650 4 $a Applied Mathematics. $3 1669109
690 $a 0796
690 $a 0984
690 $a 0364
710 2 $a Carnegie Mellon University. $3 1018096
773 0 $t Dissertation Abstracts International $g 74-12B(E).
790 $a 0041
791 $a Ph.D.
792 $a 2013
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3573511