東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Algorithmic Methods for Concave Opti...

Li, Tao.

Linked to FindBook

Google Book

Amazon

博客來

Algorithmic Methods for Concave Optimization Problems with Binary Variables.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Algorithmic Methods for Concave Optimization Problems with Binary Variables./
Author:	Li, Tao.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2017,
Description:	46 p.
Notes:	Source: Masters Abstracts International, Volume: 78-08.
Contained By:	Masters Abstracts International78-08.
Subject:	Industrial engineering. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10239320
ISBN:	9781369470222

Algorithmic Methods for Concave Optimization Problems with Binary Variables.
Li, Tao.

Algorithmic Methods for Concave Optimization Problems with Binary Variables. - Ann Arbor : ProQuest Dissertations & Theses, 2017 - 46 p.

Source: Masters Abstracts International, Volume: 78-08.

Thesis (M.S.)--Lehigh University, 2017.

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

In this thesis, we discuss two problems that involve concave minimization problems with binary variables. For the first problem, we compare the Lagrangian relaxation method and our reformulation method in solving the location model with risk pooling (LMRP) with constant customer demand rate and equal standard deviation of daily demand. Our new method is to reformulate the original non-linear model for the LMRP as a linear one. In the reformulation, we introduce a set of parameters representing the increase in the cost of the non-linear part for each additional cost assigned to a potential facility site, and a set of new decision variables indicating how many customers are assigned to each facility. Then we get a linear model by replacing the none-linear part of the original objective function by the sum of the additional costs from 0 to the number of customers assigned. The algorithms are tested on problems with 5 to 500 potential facilities and randomly generated locations. The computation time of the Lagrangian method grows slower as the number of potential sites increases than the linear method does. Though the new method takes more time than the Lagrangian method, it may have better efficiency for solving problems with special patterns in the distance matrix or other special structure. In the second half of this thesis, we discuss a general multiple-square-root pricing problem. We test a heuristic that involves sorting, similar to the method for solving the Lagrangian sub-problem for the LMRP, and we explore conditions under which the heuristic could be optimal. The accuracy rates for this method are decreasing at a slow rate as the number of the square root terms grows, while it stays high when the number is not too big.

ISBN: 9781369470222Subjects--Topical Terms:

526216
Industrial engineering.

Algorithmic Methods for Concave Optimization Problems with Binary Variables.
LDR:02780nmm a2200313 4500 001 2207451
005 20190920131228.5
008 201008s2017 ||||||||||||||||| ||eng d
020 $a 9781369470222
035 $a (MiAaPQ)AAI10239320
035 $a (MiAaPQ)lehigh:11604
035 $a AAI10239320
040 $a MiAaPQ $c MiAaPQ
100 1 $a Li, Tao. $3 1905598
245 1 0 $a Algorithmic Methods for Concave Optimization Problems with Binary Variables.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2017
300 $a 46 p.
500 $a Source: Masters Abstracts International, Volume: 78-08.
500 $a Publisher info.: Dissertation/Thesis.
500 $a Advisor: Snyder, Lawrence.
502 $a Thesis (M.S.)--Lehigh University, 2017.
506 $a This item must not be sold to any third party vendors.
520 $a In this thesis, we discuss two problems that involve concave minimization problems with binary variables. For the first problem, we compare the Lagrangian relaxation method and our reformulation method in solving the location model with risk pooling (LMRP) with constant customer demand rate and equal standard deviation of daily demand. Our new method is to reformulate the original non-linear model for the LMRP as a linear one. In the reformulation, we introduce a set of parameters representing the increase in the cost of the non-linear part for each additional cost assigned to a potential facility site, and a set of new decision variables indicating how many customers are assigned to each facility. Then we get a linear model by replacing the none-linear part of the original objective function by the sum of the additional costs from 0 to the number of customers assigned. The algorithms are tested on problems with 5 to 500 potential facilities and randomly generated locations. The computation time of the Lagrangian method grows slower as the number of potential sites increases than the linear method does. Though the new method takes more time than the Lagrangian method, it may have better efficiency for solving problems with special patterns in the distance matrix or other special structure. In the second half of this thesis, we discuss a general multiple-square-root pricing problem. We test a heuristic that involves sorting, similar to the method for solving the Lagrangian sub-problem for the LMRP, and we explore conditions under which the heuristic could be optimal. The accuracy rates for this method are decreasing at a slow rate as the number of the square root terms grows, while it stays high when the number is not too big.
590 $a School code: 0105.
650 4 $a Industrial engineering. $3 526216
690 $a 0546
710 2 $a Lehigh University. $b Industrial Engineering. $3 2092122
773 0 $t Masters Abstracts International $g 78-08.
790 $a 0105
791 $a M.S.
792 $a 2017
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10239320