Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `subject:(Reoptimization)`

.
Showing records 1 – 3 of
3 total matches.

▼ Search Limiters

North Carolina State University

1.
Kramer, Jeremy Daniel.
Min-Cost Multicommodity Network Flows: A Linear Case for the Convergence and *Reoptimization* of Multiple Single-Commodity Network Flows.

Degree: MS, Operations Research, 2009, North Carolina State University

URL: http://www.lib.ncsu.edu/resolver/1840.16/1229

Network Flow problems are prevalent in Operations Research, Computer Science, Industrial Engineering and Management Science. They constitute a class of problems that are frequently faced by real world applications, including transportation, telecommunications, production planning, etc. While many problems can be modeled as Network Flows, these problems can quickly become unwieldy in size and difficult to solve. One particularly large instance is the Min-Cost Multicommodity Network Flow problem. Due to the time-sensitive nature of the industry, faster algorithms are always desired: recent advances in decomposition methods may provide a remedy. One area of improvement is the cost reoptimization of the min-cost single commodity network flow subproblems that arise from the decomposition. Since similar single commodity network flow problems are solved, information from the previous solution provides a "warm-start" of the current solution. While certain single commodity network flow algorithms may be faster "from scratch," the goal is to reduce the overall time of computation. Reoptimization is the key to this endeavor. Three single commodity network flow algorithms, namely, cost scaling, network simplex and relaxation, will be examined. They are known to reoptimize well. The overall goal is to analyze the effectiveness of this approach within one particular class of network problems.
*Advisors/Committee Members: Thom J. Hodgson, Committee Member (advisor), William J. Stewart, Committee Member (advisor), Shu-Cherng Fang, Committee Chair (advisor).*

Subjects/Keywords: decomposition; network flows; reoptimization

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Kramer, J. D. (2009). Min-Cost Multicommodity Network Flows: A Linear Case for the Convergence and Reoptimization of Multiple Single-Commodity Network Flows. (Thesis). North Carolina State University. Retrieved from http://www.lib.ncsu.edu/resolver/1840.16/1229

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Kramer, Jeremy Daniel. “Min-Cost Multicommodity Network Flows: A Linear Case for the Convergence and Reoptimization of Multiple Single-Commodity Network Flows.” 2009. Thesis, North Carolina State University. Accessed October 19, 2019. http://www.lib.ncsu.edu/resolver/1840.16/1229.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Kramer, Jeremy Daniel. “Min-Cost Multicommodity Network Flows: A Linear Case for the Convergence and Reoptimization of Multiple Single-Commodity Network Flows.” 2009. Web. 19 Oct 2019.

Vancouver:

Kramer JD. Min-Cost Multicommodity Network Flows: A Linear Case for the Convergence and Reoptimization of Multiple Single-Commodity Network Flows. [Internet] [Thesis]. North Carolina State University; 2009. [cited 2019 Oct 19]. Available from: http://www.lib.ncsu.edu/resolver/1840.16/1229.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Kramer JD. Min-Cost Multicommodity Network Flows: A Linear Case for the Convergence and Reoptimization of Multiple Single-Commodity Network Flows. [Thesis]. North Carolina State University; 2009. Available from: http://www.lib.ncsu.edu/resolver/1840.16/1229

Not specified: Masters Thesis or Doctoral Dissertation

Georgia Tech

2. Altner, Douglas S. Advancements on problems involving maximum flows.

Degree: PhD, Industrial and Systems Engineering, 2008, Georgia Tech

URL: http://hdl.handle.net/1853/24828

This thesis presents new results on a few problems involving maximum flows. The first topic we explore is maximum flow network interdiction. The second topic we explore is reoptimization heuristics for rapidly solving an entire sequence of Maximum Flow Problems.
In the Cardinality Maximum Flow Network Interdiction Problem (CMFNIP), an interdictor chooses R arcs to delete from an s-t flow network so as to minimize the maximum flow on the network induced on the undeleted arcs. This is an
intensively studied problem that has nontrivial applications in military strategy, intercepting contraband and flood control. CMFNIP is a strongly
NP-hard special case of the Maximum Flow Network Interdiction Problem (MFNIP), where each arc has an interdiction cost and the interdictor is constrained by an interdiction budget. Although there are several papers on MFNIP, very few
theoretical results have been documented. In this talk, we introduce two exponentially large classes of valid inequalities for CMFNIP and prove that they can be separated in polynomial time. Second, we prove that the integrality gap
of the commonly used integer linear programming formulation for CMFNIP is contained in the set Omega(|V| ^(1 e)) where |V| is the number of nodes in the network and e is in the interval (0,1). We prove that this result holds even
when the linear programming relaxation is strengthened with our two classes of valid inequalities and we note that this result immediately extends to MFNIP.
In the second part of this defense, we explore incremental algorithms for solving an online sequence of Maximum Flow Problems (MFPs). Sequences of MFPs arise in a diverse collection of settings including computational biology,
finger biometry, constraint programming and real-time scheduling. To initiate this study, we develop an algorithm for solving a sequence of MFPs when the ith MFP differs from the (i-1)st MFP, for each possible i, in that the underlying
networks differ by exactly one arc. Second, we develop maximum flow reoptimization heuristics to rapidly compute a robust minimum capacity s-t cut
in light of uncertain arc capacities. Third, we develop heuristics to efficiently compute a maximum expected maximum flow in the context of two-stage stochastic programming. We present computational results illustrating the practical performance of our algorithms.
*Advisors/Committee Members: Ozlem Ergun (Committee Chair), Dana Randall (Committee Member), Joel Sokol (Committee Member), Shabbir Ahmed (Committee Member), William Cook (Committee Member).*

Subjects/Keywords: Network interdiction; Reoptimization; Robust minimum cuts; Maximum flows; Mathematical optimization; Linear programming; Maximal functions

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Altner, D. S. (2008). Advancements on problems involving maximum flows. (Doctoral Dissertation). Georgia Tech. Retrieved from http://hdl.handle.net/1853/24828

Chicago Manual of Style (16^{th} Edition):

Altner, Douglas S. “Advancements on problems involving maximum flows.” 2008. Doctoral Dissertation, Georgia Tech. Accessed October 19, 2019. http://hdl.handle.net/1853/24828.

MLA Handbook (7^{th} Edition):

Altner, Douglas S. “Advancements on problems involving maximum flows.” 2008. Web. 19 Oct 2019.

Vancouver:

Altner DS. Advancements on problems involving maximum flows. [Internet] [Doctoral dissertation]. Georgia Tech; 2008. [cited 2019 Oct 19]. Available from: http://hdl.handle.net/1853/24828.

Council of Science Editors:

Altner DS. Advancements on problems involving maximum flows. [Doctoral Dissertation]. Georgia Tech; 2008. Available from: http://hdl.handle.net/1853/24828

ETH Zürich

3. Krug, Sacha. Analysis of approximation algorithms for the traveling salesman problem in near-metric graphs.

Degree: 2011, ETH Zürich

URL: http://hdl.handle.net/20.500.11850/42971

We consider the beta-metric traveling salesman problem (Delta-beta-TSP), i.e., the TSP restricted to input instances satisfying the beta-triangle inequality c({v,w}) <= beta * (c{v,u} + c{u,w}), for any three vertices u,v,w. The well-known path matching Christofides algorithm (PMCA) provides an approximation ratio of 3/2 * beta^{2} and is the best known algorithm in the range 1 <= beta <= 2. We show that this upper bound is tight by providing a worst-case example. This example can also be used to show the tightness of the upper bound for the PMCA variants for the Hamiltonian path problem with zero and one prespecified endpoints. For two prespecified endpoints, we cannot reuse the example, but we construct another worst-case example to show the tightness of the upper bound also in this case. Furthermore, we establish improved lower bounds for an approximation algorithm for the metric Hamiltonian path problem as well as for two approximation algorithms for the metric TSP reoptimization problem.

Subjects/Keywords: Approximation algorithms; Reoptimization; PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS; COMBINATORIAL PROBLEMS (DISCRETE PROGRAMMING); KOMBINATORISCHE PROBLEME (DISKRETE OPTIMIERUNG); Hamiltonian path problem; Traveling salesman problem; PROGRAMME UND ALGORITHMEN ZUR LĂ–SUNG SPEZIELLER PROBLEME; info:eu-repo/classification/ddc/004; Data processing, computer science

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Krug, S. (2011). Analysis of approximation algorithms for the traveling salesman problem in near-metric graphs. (Thesis). ETH Zürich. Retrieved from http://hdl.handle.net/20.500.11850/42971

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Krug, Sacha. “Analysis of approximation algorithms for the traveling salesman problem in near-metric graphs.” 2011. Thesis, ETH Zürich. Accessed October 19, 2019. http://hdl.handle.net/20.500.11850/42971.

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Krug, Sacha. “Analysis of approximation algorithms for the traveling salesman problem in near-metric graphs.” 2011. Web. 19 Oct 2019.

Vancouver:

Krug S. Analysis of approximation algorithms for the traveling salesman problem in near-metric graphs. [Internet] [Thesis]. ETH Zürich; 2011. [cited 2019 Oct 19]. Available from: http://hdl.handle.net/20.500.11850/42971.

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Krug S. Analysis of approximation algorithms for the traveling salesman problem in near-metric graphs. [Thesis]. ETH Zürich; 2011. Available from: http://hdl.handle.net/20.500.11850/42971

Not specified: Masters Thesis or Doctoral Dissertation