Browsing by Subject "Combinatorial optimization"
Now showing 1 - 8 of 8
Results Per Page
Sort Options
Item Algorithms and heuristics for combinatorial optimization in phylogeny(2006) Ganapathysaravanabavan, Ganeshkumar; Ramachandran, Vijaya; Warnow, TandyItem An exact branch and bound algorithm for the general quadratic assignment problem(Texas Tech University, 1988-12) Charnsethikul, PeerayuthThis research is concerned with the development of an exact algorithm for a general quadratic assignment problem (QAP), of which the Koopmans-Beckmann formulation, in the context of an analysis of the location of economic activities or facilities, is a special case. The algorithm is based on the linearization of a general QAP of size n into a linear assignment problem of size n(n-l)/2. The objective value and the dual solution of this subproblem are used to compute the lower bound used in an exact branch and bound procedure. Computational experience and comparisons to other well known methods are discussed.Item Branch-and-cut for piecewise linear optimization(2012-05) Rajat, Gupta; Farias, Ismael R. d.; Simonton, James L.; Matis, Timothy I.; Smith, Phillip; Zhang, YuanlinIn this research we report and analyze the results of our extensive testing of branch-and- cut for piecewise linear optimization using the cutting planes. We tested large instances for transshipment problem using MIP, LOG and SOS2 formulations. Besides analysis of the performance of the cuts, we also analyze the effect of formulation of the performance of branch-and-cut. These tests were conducted using callable libraries of CPLEX and GUROBI. Finally, we also analyzed the results of piecewise linear optimization problems with semi- continuous constraints.Item Characterizing neighborhoods favorable to local search techniques(2004) Dimova, Boryana Slavcheva; Barnes, J. Wesley.; Popova, ElmiraNP-Complete problems are the most difficult problems to solve and polynomial time algorithms to solve these problems do not exist. One of the more powerful approaches for such problems are heuristic direct search techniques. For a given problem, a landscape is composed of (1) a solution space, (2) an objective function value defined at all elements of the solution space and (3) a direct search neighborhood defined for each element of the solution space. The goal of the research documented in this dissertation was to extend previous characterizations of landscapes conducive to the success of direct search methodologies. The primary contributions of this dissertation are as follows: (1) The extension of the characterization of AR(1) elementary landscapes to include arbitrary neighborhood definitions (2) The creation of an entirely new class of landscapes favorable to direct search methods, a subset of the AR(p) neighborhoods where p>1 (3) The development of a lower (upper) bound for a local minima (maxima) in AR(1) elementary landscapes using information stability (4) The characterization multistep composite AR(1) elementary landscapesItem A column generation approach for stochastic optimization problems(2006) Wang, Yong Min; Bard, Jonathan F.; Morton, David P.Item A group theoretic approach to metaheuristic local search for partitioning problems(2005) Kinney, Gary W.; Barnes, J. Wesley.Item On the shortest path and minimum spanning tree problems(2003) Pettie, Seth; Ramachandran, VijayaThe shortest path and minimum spanning tree problems are two of the classic textbook problems in combinatorial optimization. They are simple to describe and admit simple polynomial-time algorithms. However, despite years of concerted research effort, the asymptotic complexity of these problems remains unresolved. The main contributions of this dissertation are a number of asymptotically faster algorithms for the minimum spanning tree and shortest path problems. Of equal interest, we provide some clues as to why these problems are so diffcult. In particular, we show why certain modern approaches to the problems are doomed to have super-linear complexity. A sampling of our results are listed below. We emphasize that all of our algorithms work with general graphs, and make no restrictive assumptions on the numerical representation of edge-lengths. A provably optimal deterministic minimum spanning tree algorithm. (We give a constructive proof that the algorithmic complexity of the minimum spanning tree problem is equivalent to its decision-tree complexity.) An all-pairs shortest path algorithm for general graphs running in time O(mn + n2 log log n), where m and n are the number of edges and vertices. This provides the first improvement over approaches based on Dijkstra's algorithm. An all-pairs shortest path algorithm for undirected graphs running in O(mn log α ) time, where α = α (m, n) is the inverse-Ackermann function. A single-source shortest path algorithm running in O(m α +min{n log log r, n log n}) time, where r bounds the ratio of any two edge lengths. For r polynomial in n this is O(m + n log log n), an improvement over Dijkstra's algorithm. An inverse-Ackermann style lower bound for the online minimum spanning tree veri cation problem. This is the rst inverse-Ackermann type lower bound for a comparison-based problem. An Ω (m + n log n) lower bound on any hierarchy-type single-source shortest path algorithm, implying that this type of algorithm cannot improve upon Dijkstra's algorithm. (All of our shortest path algorithms are of the hierarchy type.) The first parallel minimum spanning tree algorithm that is optimal w.r.t. to both time and work. Our algorithm is for the EREW PRAM model. A parallel, expected linear-work minimum spanning tree algorithm using only a polylogarithmic number of random bits. An O(mn log α ) bound on the comparison-addition complexity of all-pairs shortest paths. This is within a tiny log α factor of optimal when m = O(n).Item Shortest spanning tree network design for cost minimization(Texas Tech University, 1970-05) Chen, ChinNot available