Spelling suggestions: "subject:"combinatorial optimization"" "subject:"ombinatorial optimization""
1 
Probabilistic limit theorems for combinatiorial optimization problems /McGivney, Katherine Grace, January 1997 (has links)
Thesis (Ph. D.)Lehigh University, 1997. / Includes vita. Bibliography: leaves 119120.

2 
Approximation techniques for unsplittable flow and traveling salesmen problemsFriggstad, Zachary Unknown Date
No description available.

3 
Algorithms for some combinatorial optimization problemsChen, Qin, 陈琴 January 2011 (has links)
published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy

4 
The use of geometric information in heuristic optimizationHinxman, Anthony Ian January 1978 (has links)
The trimloss, or cutting stock, problem arises whenever material manufactured continuously or in large pieces has to be cut into pieces of sizes ordered by customers. The problem is so to organize the cutting as to minimize the amount of waste (trimloss) resulting from it. Brown (1971) remarks that no practical solution method has been found for the generalized 2dimensional trimloss problem. This thesis discusses the applicability of heuristic search methods as solution techniques for this and other problems. Chapter 2 describes three types of combinatorial search method, statespace search, problem reduction, and branchandbound. There is a discussion of the ways in which heuristic information can be incorporated into these methods, and descriptions of the versions of the methods used in the work described in succeeding chapters. In the 1dimensional trimloss problem order lengths of some material such as steel bars must be cut from stock lengths held by the supplier. Gilmore and Gomory (1961, 1963) have formulated a mathematical programming solution of this problem, which also arises with the slitting of steel rolls, cutting of metal pipe and slitting of cellophane rolls. Their approach has been developed by Haessler (1971,1975) who is particularly concerned with problems arising in the paper industry. In the 1½dimensional case the material is manufactured as a continuous sheet of constant width and it is required to minimize the length produced to satisfy orders for rectangular pieces. In the 2dimensional case the orders are again for rectangular pieces, but here the stock is held as large rectangular sheets. In both cases there may be restrictions as to the way in which the material may be cut; the generalized problem in each case occurs when no such restrictions exist. The 1½dimensional problem appears to be easier of solution than the 2dimensional case since in the latter it is necessary not only to determine the relative positions of the required pieces in a cutting pattern, but also to partition the pieces into sets to be cut from separate stock sheets. A solution method for the easier problem might provide some insight into possible methods of solution of the more difficult. In chapter 3, a statespace search method for the solution of generalized 1½dimensional problems where the number of pieces in the order list is fairly small and the dimensions are small integers is described. This method can be developed to solve 2dimensional problems in which the order list is fairly small and the size of stock sheets variable but affecting the cost of the material. This development is described in chapter 4. A similarly structured statespace search can be used for finding solutions to optimal network problems. Such searches do not prove the solutions they find to be optimal, so it is of interest also to develop a method for finding solutions to the problems that proves them to be optimal. In chapter 5 the statespace search method is compared with one using branchandbound.problems change when large numbers of identical pieces are ordered, so a solution method with a different structure is required. Chapter 6 describes a problem reduction method for generalized 2dimensional problems in which the order lists are large and the dimensions are small integers. Even when there are restrictions on the way in which the material may be cut, the presence of other constraints may make a mathematical formulation of the 2dimensional trimloss problem intractable, so again a heuristic solution method may be desirable. In a problem where there are sequencing constraints on the design of successive cutting patterns, problem reduction is again found to provide a useful solution method. This is described in chapter 7. Some conclusions about the efficacy and potential of the methods used are drawn in chapter 8. The remainder of the present chapter is concerned with setting the work described in this thesis in the context of other work on the same and related problems.

5 
On various packing and covering problemsChen, Zhibin, 陳智斌 January 2009 (has links)
published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy

6 
A comparative study of metaheuristic algorithms for the fertilizer optimization problemDai, Chen 31 August 2006
Hard combinatorial optimization (CO) problems pose challenges to traditional algorithmic solutions. The search space usually contains a large number of local optimal points and the computational cost to reach a global optimum may be too high for practical use. In this work, we conduct a comparative study of several stateoftheart metaheuristic algorithms for hard CO problems solving. Our study is motivated by an industrial application called the Fertilizer Blends Optimization. We focus our study on a number of local search metaheuristics and analyze their performance in terms of both runtime efficiency and solution quality. We show that local search granularity (move step size) and the downhill move probability are two major factors that affect algorithm performance, and we demonstrate how experimental tuning work can be applied to obtain good performance of the algorithms. <p>Our empirical result suggests that the wellknown Simulated Annealing (SA) algorithm showed the best performance on the fertilizer problem. The simple Iterated Improvement Algorithm (IIA) also performed surprisingly well by combining strict uphill move and random neighborhood selection. A novel approach, called Delivery Network Model (DNM) algorithm, was also shown to be competitive, but it has the disadvantage of being very sensitive to local search granularity. The constructive local search method (GRASP), which combines heuristic space sampling and local search, outperformed IIA without a construction phase; however, the improvement in performance is limited and generally speaking, local search performance is not sensitive to initial search positions in our studied fertilizer problem.

7 
A comparative study of metaheuristic algorithms for the fertilizer optimization problemDai, Chen 31 August 2006 (has links)
Hard combinatorial optimization (CO) problems pose challenges to traditional algorithmic solutions. The search space usually contains a large number of local optimal points and the computational cost to reach a global optimum may be too high for practical use. In this work, we conduct a comparative study of several stateoftheart metaheuristic algorithms for hard CO problems solving. Our study is motivated by an industrial application called the Fertilizer Blends Optimization. We focus our study on a number of local search metaheuristics and analyze their performance in terms of both runtime efficiency and solution quality. We show that local search granularity (move step size) and the downhill move probability are two major factors that affect algorithm performance, and we demonstrate how experimental tuning work can be applied to obtain good performance of the algorithms. <p>Our empirical result suggests that the wellknown Simulated Annealing (SA) algorithm showed the best performance on the fertilizer problem. The simple Iterated Improvement Algorithm (IIA) also performed surprisingly well by combining strict uphill move and random neighborhood selection. A novel approach, called Delivery Network Model (DNM) algorithm, was also shown to be competitive, but it has the disadvantage of being very sensitive to local search granularity. The constructive local search method (GRASP), which combines heuristic space sampling and local search, outperformed IIA without a construction phase; however, the improvement in performance is limited and generally speaking, local search performance is not sensitive to initial search positions in our studied fertilizer problem.

8 
An analysis of the state space graph for integer permutation with application to local searchThompson, Barrett Michael 08 1900 (has links)
No description available.

9 
On partial completion problemsEaston, Todd William 08 1900 (has links)
No description available.

10 
A study of some assortment and location problemsNaqvi, I. A. January 1981 (has links)
No description available.

Page generated in 0.1727 seconds