Approaches for multi-objective combinatorial optimization problems

Lokman, Banu
In this thesis, we develop two exact algorithms and a heuristic procedure for Multiobjective Combinatorial Optimization Problems (MOCO). Our exact algorithms guarantee to generate all nondominated solutions of any MOCO problem. We test the performance of the algorithms on randomly generated problems including the Multiobjective Knapsack Problem, Multi-objective Shortest Path Problem and Multi-objective Spanning Tree Problem. Although we showed the algorithms work much better than the previous ones, we also proposed a fast heuristic method to approximate efficient frontier since it will also be applicable for real-sized problems. Our heuristic approach is based on fitting a surface to approximate the efficient frontier. We experiment our heuristic on randomly generated problems to test how well the heuristic procedure approximates the efficient frontier. Our results showed the heuristic method works well.


Parameter optimization of chemically activated mortaars containing high volumes of pozzolan by statistical design and analysis of experiments
Aldemir, Başak; Saatçioğlu, Ömer; Department of Industrial Engineering (2006)
This thesis illustrates parameter optimization of early and late compressive strengths of chemically activated mortars containing high volumes of pozzolan by statistical design and analysis of experiments. Four dominant parameters in chemical activation of natural pozzolans are chosen for the research, which are natural pozzolan replacement, amount of pozzolan passing 45 æm sieve, activator dosage and activator type. Response surface methodology has been employed in statistical design and analysis of experi...
Approaches for multiobjective combinatorial optimization problems
Özpeynirci, Nail Özgür; Köksalan, Murat; Department of Industrial Engineering (2008)
In this thesis, we consider multiobjective combinatorial optimization problems. We address two main topics. We first address the polynomially solvable cases of the Traveling Salesperson Problem and the Bottleneck Traveling Salesperson Problem. We consider multiobjective versions of these problems with different combinations of objective functions, analyze their computational complexities and develop exact algorithms where possible. We next consider generating extreme supported nondominated points of multiob...
Stability analysis of constraints in flexible multibody systems dynamics
İder, Sıtkı Kemal (Elsevier BV, 1990-1)
Automated algorithms for the dynamic analysis and simulation of constrained multibody systems assume that the constraint equations are linearly independent. During the motion, when the system is at a singular configuration, the constraint Jacobian matrix possesses less than full rank and hence it results in singularities. This occurs when the direction of a constraint coincides with the direction of the lost degree of freedom. In this paper the constraint equations for deformable bodies are modified for use...
An evolutionary algorithm for multiple criteria problems
Soylu, Banu; Köksalan, Murat; Department of Industrial Engineering (2007)
In this thesis, we develop an evolutionary algorithm for approximating the Pareto frontier of multi-objective continuous and combinatorial optimization problems. The algorithm tries to evolve the population of solutions towards the Pareto frontier and distribute it over the frontier in order to maintain a well-spread representation. The fitness score of each solution is computed with a Tchebycheff distance function and non-dominating sorting approach. Each solution chooses its own favorable weights accordin...
Modelling the evolution of demand forecasts in a production-distribution system
Yücer, Cem Tahsin; Meral, Fatma Sedef; Department of Industrial Engineering (2006)
In this thesis, we focus on a forecasting tool, Martingale Model of Forecast Evolution (MMFE), to model the evolution of forecasts in a production-distribution system. Additive form is performed to represent the evolution process. Variance-Covariance (VCV) matrix is defined to express the forecast updates. The selected demand pattern is stationary and it is normally distributed. It follows an Autoregressive Order-1 (AR(1)) model. Two forecasting procedures are selected to compare the MMFE with. These are MA...
Citation Formats
B. Lokman, “Approaches for multi-objective combinatorial optimization problems,” M.S. - Master of Science, Middle East Technical University, 2007.