國立虎尾科技大學 |

Infinite-Dimensional Relaxations of Mixed-Integer Optimization Problems.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Infinite-Dimensional Relaxations of Mixed-Integer Optimization Problems./
Author:	Zhou, Yuan.
Description:	1 online resource (205 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 79-01(E), Section: B.
Contained By:	Dissertation Abstracts International79-01B(E).
Subject:	Applied mathematics. -
Online resource:	click for full text (PQDT)
ISBN:	9780355152005

Infinite-Dimensional Relaxations of Mixed-Integer Optimization Problems.
Zhou, Yuan.

Infinite-Dimensional Relaxations of Mixed-Integer Optimization Problems. - 1 online resource (205 pages)

Source: Dissertation Abstracts International, Volume: 79-01(E), Section: B.

Thesis (Ph.D.)

Includes bibliographical references

Optimization problems with integer variables form a class of mathematical models that are widely used in Operations Research and Mathematical Analytics. They provide a great modeling power, but it comes at a high price: Integer optimization problems are typically very hard to solve, both in theory and practice.

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

Mode of access: World Wide Web

ISBN: 9780355152005Subjects--Topical Terms:

1069907
Applied mathematics.
Index Terms--Genre/Form:

554714
Electronic books.

Infinite-Dimensional Relaxations of Mixed-Integer Optimization Problems.
LDR:03512ntm a2200397Ki 4500 001 910775
005 20180517112610.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9780355152005
035 $a (MiAaPQ)AAI10286353
035 $a (MiAaPQ)ucdavis:17118
035 $a AAI10286353
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Zhou, Yuan. $3 1182229
245 1 0 $a Infinite-Dimensional Relaxations of Mixed-Integer Optimization Problems.
264 0 $c 2017
300 $a 1 online resource (205 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: Dissertation Abstracts International, Volume: 79-01(E), Section: B.
500 $a Adviser: Matthias Koppe.
502 $a Thesis (Ph.D.) $c University of California, Davis $d 2017.
504 $a Includes bibliographical references
520 $a Optimization problems with integer variables form a class of mathematical models that are widely used in Operations Research and Mathematical Analytics. They provide a great modeling power, but it comes at a high price: Integer optimization problems are typically very hard to solve, both in theory and practice.
520 $a A key ingredient in state-of-the-art solvers for integer optimization problems are cutting-plane algorithms. The need for next-generation cutting planes, prompted by ever-larger applications and models, has led to a recent trend, which revisits and extends foundational work in integer optimization by Ralph Gomory in the 1960s and Gomory--Johnson in the early 1970s, under the name of cut-generating functions. In this dissertation, we focus on the cut-generating functions in the single row Gomory--Johnson infinite group relaxation model for integer optimization problems.
520 $a The proofs of cutting planes theorems in the literature were hand-written, and were dominated by tedious and error-prone case analysis. We ask how much of this process can be automated: In particular, can we use algorithms to discover and prove theorems about cutting planes?
520 $a We develop a software for investigations with cut-generating functions, which implements a grid-free algorithmic extremality test. We conduct a computer-based search that leads to the discovery of new cut-generating functions, whose existence settles several open questions. Using a metaprogramming technique and semialgebraic computations, we provide computer-based proofs for old and new cutting-plane theorems.
520 $a This dissertation also addresses the theoretical aspects of cut-generating functions. We improve the general theory of effective perturbations of minimal valid functions, which enables the grid-free algorithmic extremality test. We investigate the fine structure of a space of cut-generating functions, underlining the exceptional place that two-sided discontinuous functions take in the theory of the Gomory--Johnson functions. We establish a clear relation of three competing notions of facets in the infinite-dimensional Gomory--Johnson model, resolving a longstanding mystery.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Applied mathematics. $3 1069907
650 4 $a Operations research. $3 573517
655 7 $a Electronic books. $2 local $3 554714
690 $a 0364
690 $a 0796
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of California, Davis. $b Applied Mathematics. $3 1180524
773 0 $t Dissertation Abstracts International $g 79-01B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10286353 $z click for full text (PQDT)