東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Subadditivity of Piecewise Linear Fu...

Wang, Jiawei.

Linked to FindBook

Google Book

Amazon

博客來

Subadditivity of Piecewise Linear Functions.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Subadditivity of Piecewise Linear Functions./
Author:	Wang, Jiawei.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2020,
Description:	146 p.
Notes:	Source: Dissertations Abstracts International, Volume: 82-05, Section: B.
Contained By:	Dissertations Abstracts International82-05B.
Subject:	Mathematics. -
Online resource:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28093438
ISBN:	9798691214356

Subadditivity of Piecewise Linear Functions.
Wang, Jiawei.

Subadditivity of Piecewise Linear Functions. - Ann Arbor : ProQuest Dissertations & Theses, 2020 - 146 p.

Source: Dissertations Abstracts International, Volume: 82-05, Section: B.

Thesis (Ph.D.)--University of California, Davis, 2020.

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

An optimization problem is trying to minimize or maximize a real objective function such that the input variables satisfies certain constraints. The simplest optimization problem is the linear program (LP), which has been proved to be in the P class and are usually solved by the simplex method or interior point methods. However, imposing integral constraints to an optimization problem can make the problem difficult to solve, and the mixed integer program (MIP) belongs to the NP-hard class. Mixed integer optimization problems have a large number of applications in various fields, such as operations research and machine learning. Although MIP are typically hard to solve, the good news is that researchers are making substantial progress on solving problems more efficiently using better computation powers and more robust algorithms. Cutting plane algorithms, which were first proposed by Gomory and Johnson in the 1960s, are widely used in the state-of-the-art solvers. In the cutting plane algorithms, a family of real functions (so called cut-generating functions) are used to provide valid constraints to the optimization problem so that they can be solved faster. Cut-generating functions are typically piecewise linear functions and satisfy subadditivity. In this dissertation, we study the subadditivity of piecewise linear functions and use a software to verify subadditivity more efficiently. It is important to verify subadditivity of a cut-generating function before applying it to optimization problems. As the structure of the cut-generating function gets complicated, the existing algorithm can take a very long time to verify subadditivity. We develop a spatial branch and bound algorithm to prove or disprove subadditivity of a given piecewise linear function. We use a benchmark work to show that the new algorithm works better for functions with complicated structures. We also address the reproducibility of the benchmark work, and we provide a open sourced repository so that other interested researchers can reproduce the experiment.Dual-feasible functions are in the scope of superadditive duality theory, and they are an important family of functions which have been used in certain combinatorial optimization problems. We provide a new characterization of strong dual-feasible functions and we relate them to cut-generating functions. Inspired by results on cut-generating functions, we discover new results on dual-feasible functions. Software has been used to study properties of dual-feasible functions, based on which new dual-feasible functions can be found.

ISBN: 9798691214356Subjects--Topical Terms:

515831
Mathematics.
Subjects--Index Terms:

Benchmark

Subadditivity of Piecewise Linear Functions.
LDR:03817nmm a2200397 4500 001 2280415
005 20210827095944.5
008 220723s2020 ||||||||||||||||| ||eng d
020 $a 9798691214356
035 $a (MiAaPQ)AAI28093438
035 $a AAI28093438
040 $a MiAaPQ $c MiAaPQ
100 1 $a Wang, Jiawei. $3 3542751
245 1 0 $a Subadditivity of Piecewise Linear Functions.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2020
300 $a 146 p.
500 $a Source: Dissertations Abstracts International, Volume: 82-05, Section: B.
500 $a Advisor: Koeppe, Matthias.
502 $a Thesis (Ph.D.)--University of California, Davis, 2020.
506 $a This item must not be sold to any third party vendors.
520 $a An optimization problem is trying to minimize or maximize a real objective function such that the input variables satisfies certain constraints. The simplest optimization problem is the linear program (LP), which has been proved to be in the P class and are usually solved by the simplex method or interior point methods. However, imposing integral constraints to an optimization problem can make the problem difficult to solve, and the mixed integer program (MIP) belongs to the NP-hard class. Mixed integer optimization problems have a large number of applications in various fields, such as operations research and machine learning. Although MIP are typically hard to solve, the good news is that researchers are making substantial progress on solving problems more efficiently using better computation powers and more robust algorithms. Cutting plane algorithms, which were first proposed by Gomory and Johnson in the 1960s, are widely used in the state-of-the-art solvers. In the cutting plane algorithms, a family of real functions (so called cut-generating functions) are used to provide valid constraints to the optimization problem so that they can be solved faster. Cut-generating functions are typically piecewise linear functions and satisfy subadditivity. In this dissertation, we study the subadditivity of piecewise linear functions and use a software to verify subadditivity more efficiently. It is important to verify subadditivity of a cut-generating function before applying it to optimization problems. As the structure of the cut-generating function gets complicated, the existing algorithm can take a very long time to verify subadditivity. We develop a spatial branch and bound algorithm to prove or disprove subadditivity of a given piecewise linear function. We use a benchmark work to show that the new algorithm works better for functions with complicated structures. We also address the reproducibility of the benchmark work, and we provide a open sourced repository so that other interested researchers can reproduce the experiment.Dual-feasible functions are in the scope of superadditive duality theory, and they are an important family of functions which have been used in certain combinatorial optimization problems. We provide a new characterization of strong dual-feasible functions and we relate them to cut-generating functions. Inspired by results on cut-generating functions, we discover new results on dual-feasible functions. Software has been used to study properties of dual-feasible functions, based on which new dual-feasible functions can be found.
590 $a School code: 0029.
650 4 $a Mathematics. $3 515831
650 4 $a Theoretical mathematics. $3 3173530
650 4 $a Information technology. $3 532993
653 $a Benchmark
653 $a Branch-and-bound
653 $a Cut-generating function
653 $a Dual-feasible function
653 $a Subadditivity
653 $a Optimization errors
653 $a Real objective functions
690 $a 0405
690 $a 0642
690 $a 0489
710 2 $a University of California, Davis. $b Mathematics. $3 3343026
773 0 $t Dissertations Abstracts International $g 82-05B.
790 $a 0029
791 $a Ph.D.
792 $a 2020
793 $a English
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28093438