Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for subject:(Reoptimization). Showing records 1 – 3 of 3 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ 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

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 DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th 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 (16th 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 (7th 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

Note: this citation may be lacking information needed for this citation format:
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

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 DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th 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 (16th 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 (7th 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

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 * beta2 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 DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th 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

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th 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.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th 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.

Note: this citation may be lacking information needed for this citation format:
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

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.