Search

We consider both facial reduction, FR, and symmetry reduction, SR, techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and solving the doubly nonnegative, DNN, relaxation of many classes of hard combinatorial problems. We also show that the singularity degree remains the same after SR, and that the DNN relaxations considered here have singularity degree one, that is reduced to zero after FR. The combination of FR and SR leads to a significant improvement in both numerical stability and running time for both the ADMM and interior point approaches. We test our method on various DNN relaxations of hard combinatorial problems including quadratic assignment problems with sizes of more than n = 500. This translates to a semidefinite constraint of order 250, 000 and 625 x 10(8) nonnegative constrained variables, before applying the reduction techniques.

A common computational approach for polynomial optimization problems (POPs) is to use (hierarchies of) semidefinite programming (SDP) relaxations. When the variables in the POP are required to be nonnegative–as is the case for combinatorial optimization problems, for example–these SDP problems typically involve nonnegative matrices, i.e. they are conic optimization problems over the doubly nonnegative cone. The Jordan reduction, a symmetry reduction method for conic optimization, was recently introduced for symmetric cones by Parrilo and Permenter [Mathematical Programming 181(1), 2020]. We extend this method to the doubly nonnegative cone, and investigate its application to known relaxations of the quadratic assignment and maximum stable set problems. We also introduce new Julia software where the symmetry reduction is implemented.

We propose a new hybrid quantum algorithm based on the classical Ant Colony Optimization algorithm to produce approximate solutions for NP-hard problems, in particular optimization problems. First, we discuss some previously proposed Quantum Ant Colony Optimization algorithms, and based on them, we develop an improved algorithm that can be truly implemented on near-term quantum computers. Our iterative algorithm codifies only the information about the pheromones and the exploration parameter in the quantum state, while subrogating the calculation of the numerical result to a classical computer. A new guided exploration strategy is used in order to take advantage of the quantum computation power and generate new possible solutions as a superposition of states. This approach is specially useful to solve constrained optimization problems, where we can implement efficiently the exploration of new paths without having to check the correspondence of a path to a solution before the measurement of the state. As an example of a NP-hard problem, we choose to solve the Quadratic Assignment Problem. The benchmarks made by simulating the noiseless quantum circuit and the experiments made on IBM quantum computers show the validity of the algorithm.

Elementary landscapes are a special type of combinatorial landscapes that have some properties that make them particularly suitable for working with meta-heuristic algorithms, specially local search based methods. In most of the cases a landscape is not elementary, however, if the neighborhood function meets some conditions, it can be decomposed into a set of elementary landscapes through a process that is called Elementary Landscape Decomposition (ELD). This is the case of the Quadratic Assignment Problem (QAP) under the swap neighborhood, which can be additively decomposed into three elementary landscapes. This work has two main goals. First, we use the ELD approach to analyze the behaviour of two local search based meta-heuristics that optimize the QAP. In this sense, we intend to check whether incorporating the ELD during the optimization process improves the performance of meta-heuristic algorithms. Second, we propose an additional decomposition of the elementary landscapes that form the QAP. This decomposition defines a framework that helps us to characterize what is measured by each elementary landscape, hence giving us a deeper insight into the ELD of the problem.

Hospital facilities are known as functionally complex buildings. There are usually configurational problems that lead to inefficient transportation processes for patients, medical staff, and/or logistics of materials. The Quadratic Assignment Problem (QAP) is a well-known problem in the field of Operations Research from the category of the facility's location/allocation problems. However, it has rarely been utilized in architectural design practice. This paper presents a formulation of such logistics issues as a QAP for space planning processes aimed at renovation of existing hospitals, a heuristic QAP solver developed in a CAD environment, and its implementation as a computational design tool designed to be used by architects. The tool is implemented in C# for Grasshopper (GH), a plugin of Rhinoceros CAD software. This tool minimizes the internal transportation processes between interrelated facilities where each facility is assigned to a location in an existing building. In our model, the problem of assignment is relaxed in that a single facility may be allowed to be allocated within multiple voxel locations, thus alleviating the complexity of the unequal area assignment problem. The QAP formulation takes into account both the flows between facilities and distances between locations. The distance matrix is obtained from the spatial network of the building by using graph traversal techniques. The developed tool also calculates spatial geodesic distances (walkable, easiest, and/or shortest paths for pedestrians) inside the building. The QAP is solved by a heuristic optimization algorithm, called Iterated Local Search. Using one exemplary real test case, we demonstrate the potential of this method in the context of hospital layout design/re-design tasks in 3D. Finally, we discuss the results and possible further developments concerning a generic computational space planning framework., Design Informatics

We consider the problem of minimizing the sum of three functions, one of which is nonconvex but differentiable, and the other two are convex but possibly nondifferentiable. We investigate the Three Operator Splitting method (TOS) of Davis & Yin (2017) with an aim to extend its theoretical guarantees for this nonconvex problem template. In particular, we prove convergence of TOS with nonasymptotic bounds on its nonstationarity and infeasibility errors. In contrast with the existing work on nonconvex TOS, our guarantees do not require additional smoothness assumptions on the terms comprising the objective; hence they cover instances of particular interest where the nondifferentiable terms are indicator functions. We also extend our results to a stochastic setting where we have access only to an unbiased estimator of the gradient. Finally, we illustrate the effectiveness of the proposed method through numerical experiments on quadratic assignment problems.

We consider the problem of minimizing the sum of three functions, one of which is nonconvex but differentiable, and the other two are convex but possibly nondifferentiable. We investigate the Three Operator Splitting method (TOS) of Davis & Yin (2017) with an aim to extend its theoretical guarantees for this nonconvex problem template. In particular, we prove convergence of TOS with nonasymptotic bounds on its nonstationarity and infeasibility errors. In contrast with the existing work on nonconvex TOS, our guarantees do not require additional smoothness assumptions on the terms comprising the objective; hence they cover instances of particular interest where the nondifferentiable terms are indicator functions. We also extend our results to a stochastic setting where we have access only to an unbiased estimator of the gradient. Finally, we illustrate the effectiveness of the proposed method through numerical experiments on quadratic assignment problems.

We consider the problem of minimizing the sum of three functions, one of which is nonconvex but differentiable, and the other two are convex but possibly nondifferentiable. We investigate the Three Operator Splitting method (TOS) of Davis & Yin (2017) with an aim to extend its theoretical guarantees for this nonconvex problem template. In particular, we prove convergence of TOS with nonasymptotic bounds on its nonstationarity and infeasibility errors. In contrast with the existing work on nonconvex TOS, our guarantees do not require additional smoothness assumptions on the terms comprising the objective; hence they cover instances of particular interest where the nondifferentiable terms are indicator functions. We also extend our results to a stochastic setting where we have access only to an unbiased estimator of the gradient. Finally, we illustrate the effectiveness of the proposed method through numerical experiments on quadratic assignment problems.

The Quadratic Assignment Problem (QAP) is one of the classical combinatorial optimization problems and is known for its diverse applications. The QAP is an NP-hard optimization problem which attracts the use of heuristic or metaheuristic algorithms that can find quality solutions in an acceptable computation time. On the other hand, there is quite a broad spectrum of mathematical programming techniques that were developed for finding the lower bounds for the QAP. This paper presents a fusion of the two approaches whereby the solutions from the computations of the lower bounds are used as the starting points for a metaheuristic, called HC12, which is implemented on a GPU CUDA platform. We perform extensive computational experiments that demonstrate that the use of these lower bounding techniques for the construction of the starting points has a significant impact on the quality of the resulting solutions.

The Quadratic Assignment Problem (QAP) is one of the classical combinatorial optimization problems and is known for its diverse applications. The QAP is an NP-hard optimization problem which attracts the use of heuristic or metaheuristic algorithms that can find quality solutions in an acceptable computation time. On the other hand, there is quite a broad spectrum of mathematical programming techniques that were developed for finding the lower bounds for the QAP. This paper presents a fusion of the two approaches whereby the solutions from the computations of the lower bounds are used as the starting points for a metaheuristic, called HC12, which is implemented on a GPU CUDA platform. We perform extensive computational experiments that demonstrate that the use of these lower bounding techniques for the construction of the starting points has a significant impact on the quality of the resulting solutions.

We consider the problem of minimizing the sum of three functions, one of which is nonconvex but differentiable, and the other two are convex but possibly nondifferentiable. We investigate the Three Operator Splitting method (TOS) of Davis & Yin (2017) with an aim to extend its theoretical guarantees for this nonconvex problem template. In particular, we prove convergence of TOS with nonasymptotic bounds on its nonstationarity and infeasibility errors. In contrast with the existing work on nonconvex TOS, our guarantees do not require additional smoothness assumptions on the terms comprising the objective; hence they cover instances of particular interest where the nondifferentiable terms are indicator functions. We also extend our results to a stochastic setting where we have access only to an unbiased estimator of the gradient. Finally, we illustrate the effectiveness of the proposed method through numerical experiments on quadratic assignment problems.

Hospital facilities are known as functionally complex buildings. There are usually configurational problems that lead to inefficient transportation processes for patients, medical staff, and/or logistics of materials. The Quadratic Assignment Problem (QAP) is a well-known problem in the field of Operations Research from the category of the facility's location/allocation problems. However, it has rarely been utilized in architectural design practice. This paper presents a formulation of such logistics issues as a QAP for space planning processes aimed at renovation of existing hospitals, a heuristic QAP solver developed in a CAD environment, and its implementation as a computational design tool designed to be used by architects. The tool is implemented in C# for Grasshopper (GH), a plugin of Rhinoceros CAD software. This tool minimizes the internal transportation processes between interrelated facilities where each facility is assigned to a location in an existing building. In our model, the problem of assignment is relaxed in that a single facility may be allowed to be allocated within multiple voxel locations, thus alleviating the complexity of the unequal area assignment problem. The QAP formulation takes into account both the flows between facilities and distances between locations. The distance matrix is obtained from the spatial network of the building by using graph traversal techniques. The developed tool also calculates spatial geodesic distances (walkable, easiest, and/or shortest paths for pedestrians) inside the building. The QAP is solved by a heuristic optimization algorithm, called Iterated Local Search. Using one exemplary real test case, we demonstrate the potential of this method in the context of hospital layout design/re-design tasks in 3D. Finally, we discuss the results and possible further developments concerning a generic computational space planning framework., Design Informatics

We consider the problem of minimizing the sum of three functions, one of which is nonconvex but differentiable, and the other two are convex but possibly nondifferentiable. We investigate the Three Operator Splitting method (TOS) of Davis & Yin (2017) with an aim to extend its theoretical guarantees for this nonconvex problem template. In particular, we prove convergence of TOS with nonasymptotic bounds on its nonstationarity and infeasibility errors. In contrast with the existing work on nonconvex TOS, our guarantees do not require additional smoothness assumptions on the terms comprising the objective; hence they cover instances of particular interest where the nondifferentiable terms are indicator functions. We also extend our results to a stochastic setting where we have access only to an unbiased estimator of the gradient. Finally, we illustrate the effectiveness of the proposed method through numerical experiments on quadratic assignment problems.

[EN] I propose an improved algorithm that can be implemented on a real quantum computer with a new guided exploration strategy. The benchmarks made by simulating the quantum circuit shows that the time to solve a problem using QACO could outperform greatly other classical bio-inspired algorithms, in particular the one QACO is based on, the Ant Colony Optimization. Quantum computation is on the verge of becoming the new technology for solving time- and energy-consuming problems. To make use of the full potential of quantum computers one must implement algorithms that are significantly different from the ones used on digital computers. This work serves as an introduction to both quantum computing and algorithms. Starting from the basis of the quantum physics, I expose each of the steps needed to understand the mathematics beneath this topic. Using this basis, I develope one quantum algorithm from scratch. Based on a previously proposed Quantum Ant Colony Optimization (QACO) algorithm, I propose an improved algorithm that can be implemented on a real quantum computer with a new guided exploration strategy. The benchmarks made by simulating the quantum circuit shows that the time to solve a problem using QACO could outperform greatly other classical bio-inspired algorithms, in particular the one QACO is based on, the Ant Colony Optimization., [ES] La computación cuántica está a punto de convertirse en la nueva tecnología para resolver problemas de tiempo y consumo de energía. Para hacer uso del potencial completo de las computadoras cuánticas uno debe implementar algoritmos que son significativamente diferentes de los utilizados en las computadoras digitales. Este trabajo sirve como introducción a la computación cuántica y algoritmos. A partir de la base de la física cuántica, expongo cada uno de los pasos necesarios para entender las matemáticas bajo este tema. Usando esta base, desarrollo un algoritmo cuántico desde cero. Basado en un algoritmo previamente propuesto de Optimización de Colonias de Hormigas Cuánticas (QACO), propongo un algoritmo mejorado que se puede implementar en un ordenador cuántico real con una nueva estrategia de exploración guiada. Los puntos de referencia realizados al simular el circuito cuántico muestran que el tiempo para resolver un problema utilizando QACO podría superar en gran medida otros algoritmos bioinspirados clásicos, en particular el QACO se basa en la Ant Colony Optimization.

Quantum computing is one of the most researched areas in computer science and withone of the greatest future prospects thanks to the new discoveries and methodologies thatcan provide approaches of a different kind to tackle problems and find solutions. One ofsuch methodologies is none other than quantum annealing, a metaheuristic focused on thequalities of quantum mechanics. Combinatorial Optimization (CO) problems have always been a hassle to find solutionsin large scale problems owing to their complexity and resource consumption. However,these can be transformed into an equivalent Quadratic Unconstrained Binary Optimization(QUBO) model that is constraint-free and its variables are (binary) decision variables.What is best, QUBO models can be efficiently solve with quantum annealing in a quantumcomputer. The objective of the project will be the study of all the particular functionalities andproperties of each aspect of all the transformation chain for the specific case study withthe QAP problem. The implementation of this problem, its transformation into a QUBOmodel and the solution obtained through quantum annealing are the key points that leadto harness the potential of quantum computing and set its current limits.

[EN] I propose an improved algorithm that can be implemented on a real quantum computer with a new guided exploration strategy. The benchmarks made by simulating the quantum circuit shows that the time to solve a problem using QACO could outperform greatly other classical bio-inspired algorithms, in particular the one QACO is based on, the Ant Colony Optimization. Quantum computation is on the verge of becoming the new technology for solving time- and energy-consuming problems. To make use of the full potential of quantum computers one must implement algorithms that are significantly different from the ones used on digital computers. This work serves as an introduction to both quantum computing and algorithms. Starting from the basis of the quantum physics, I expose each of the steps needed to understand the mathematics beneath this topic. Using this basis, I develope one quantum algorithm from scratch. Based on a previously proposed Quantum Ant Colony Optimization (QACO) algorithm, I propose an improved algorithm that can be implemented on a real quantum computer with a new guided exploration strategy. The benchmarks made by simulating the quantum circuit shows that the time to solve a problem using QACO could outperform greatly other classical bio-inspired algorithms, in particular the one QACO is based on, the Ant Colony Optimization., [ES] La computación cuántica está a punto de convertirse en la nueva tecnología para resolver problemas de tiempo y consumo de energía. Para hacer uso del potencial completo de las computadoras cuánticas uno debe implementar algoritmos que son significativamente diferentes de los utilizados en las computadoras digitales. Este trabajo sirve como introducción a la computación cuántica y algoritmos. A partir de la base de la física cuántica, expongo cada uno de los pasos necesarios para entender las matemáticas bajo este tema. Usando esta base, desarrollo un algoritmo cuántico desde cero. Basado en un algoritmo previamente propuesto de Optimización de Colonias de Hormigas Cuánticas (QACO), propongo un algoritmo mejorado que se puede implementar en un ordenador cuántico real con una nueva estrategia de exploración guiada. Los puntos de referencia realizados al simular el circuito cuántico muestran que el tiempo para resolver un problema utilizando QACO podría superar en gran medida otros algoritmos bioinspirados clásicos, en particular el QACO se basa en la Ant Colony Optimization.

Quantum computing is one of the most researched areas in computer science and withone of the greatest future prospects thanks to the new discoveries and methodologies thatcan provide approaches of a different kind to tackle problems and find solutions. One ofsuch methodologies is none other than quantum annealing, a metaheuristic focused on thequalities of quantum mechanics. Combinatorial Optimization (CO) problems have always been a hassle to find solutionsin large scale problems owing to their complexity and resource consumption. However,these can be transformed into an equivalent Quadratic Unconstrained Binary Optimization(QUBO) model that is constraint-free and its variables are (binary) decision variables.What is best, QUBO models can be efficiently solve with quantum annealing in a quantumcomputer. The objective of the project will be the study of all the particular functionalities andproperties of each aspect of all the transformation chain for the specific case study withthe QAP problem. The implementation of this problem, its transformation into a QUBOmodel and the solution obtained through quantum annealing are the key points that leadto harness the potential of quantum computing and set its current limits.

[EN] I propose an improved algorithm that can be implemented on a real quantum computer with a new guided exploration strategy. The benchmarks made by simulating the quantum circuit shows that the time to solve a problem using QACO could outperform greatly other classical bio-inspired algorithms, in particular the one QACO is based on, the Ant Colony Optimization. Quantum computation is on the verge of becoming the new technology for solving time- and energy-consuming problems. To make use of the full potential of quantum computers one must implement algorithms that are significantly different from the ones used on digital computers. This work serves as an introduction to both quantum computing and algorithms. Starting from the basis of the quantum physics, I expose each of the steps needed to understand the mathematics beneath this topic. Using this basis, I develope one quantum algorithm from scratch. Based on a previously proposed Quantum Ant Colony Optimization (QACO) algorithm, I propose an improved algorithm that can be implemented on a real quantum computer with a new guided exploration strategy. The benchmarks made by simulating the quantum circuit shows that the time to solve a problem using QACO could outperform greatly other classical bio-inspired algorithms, in particular the one QACO is based on, the Ant Colony Optimization., [ES] La computación cuántica está a punto de convertirse en la nueva tecnología para resolver problemas de tiempo y consumo de energía. Para hacer uso del potencial completo de las computadoras cuánticas uno debe implementar algoritmos que son significativamente diferentes de los utilizados en las computadoras digitales. Este trabajo sirve como introducción a la computación cuántica y algoritmos. A partir de la base de la física cuántica, expongo cada uno de los pasos necesarios para entender las matemáticas bajo este tema. Usando esta base, desarrollo un algoritmo cuántico desde cero. Basado en un algoritmo previamente propuesto de Optimización de Colonias de Hormigas Cuánticas (QACO), propongo un algoritmo mejorado que se puede implementar en un ordenador cuántico real con una nueva estrategia de exploración guiada. Los puntos de referencia realizados al simular el circuito cuántico muestran que el tiempo para resolver un problema utilizando QACO podría superar en gran medida otros algoritmos bioinspirados clásicos, en particular el QACO se basa en la Ant Colony Optimization.

Quantum computing is one of the most researched areas in computer science and withone of the greatest future prospects thanks to the new discoveries and methodologies thatcan provide approaches of a different kind to tackle problems and find solutions. One ofsuch methodologies is none other than quantum annealing, a metaheuristic focused on thequalities of quantum mechanics. Combinatorial Optimization (CO) problems have always been a hassle to find solutionsin large scale problems owing to their complexity and resource consumption. However,these can be transformed into an equivalent Quadratic Unconstrained Binary Optimization(QUBO) model that is constraint-free and its variables are (binary) decision variables.What is best, QUBO models can be efficiently solve with quantum annealing in a quantumcomputer. The objective of the project will be the study of all the particular functionalities andproperties of each aspect of all the transformation chain for the specific case study withthe QAP problem. The implementation of this problem, its transformation into a QUBOmodel and the solution obtained through quantum annealing are the key points that leadto harness the potential of quantum computing and set its current limits.

This paper addresses the problem of distributing uniformly infrared radiative energy intercepted by a thermoplastic sheet surface during the infrared radiation transmitted by an oven with convection and conduction considerations. After discretizing this problem, we proposed an objective function that captures the uniform distribution of the radiative energy. With this approximation scheme, the corresponding problem appears to be nothing else than a variant of a quadratic assignment problem. Accordingly, we designed and applied a migrating bird optimization based algorithm (MBO for short), in order to minimize the corresponding objective function. To evaluate this approach we conducted a numerical experimental study.

Operacioni menadžer koristi skup postupaka čiji je cilj da se poslovi urade brže, jeftinije i kvalitetnije. Naučnici iz oblasti operacionog menadžmenta imaju zadatak da ovi postupci budu izvodljivi i praktični. Skoro uvek, menadžeri pokušavaju da nešto optimizuju – ili je to minimizacija troškova i potrošnje energije, ili pak, maksimizacija profita, rezultata, performansi i efikasnosti. Međutim, nije uvek moguće pronaći optimalna rešenja. U praksi, menadžer mora da se zadovolji rešenjima koja možda nisu optimalna, ali su dopustiva, zadovoljavajuća, robustna, i dostižna u razumnom vremenu. Ovakva rešenja se dobijaju primenama heuristika, koje mogu biti konstruktivne, poboljšavajuće ili hibridne. Oblast istraživanja u doktorskoj disertaciji su konstruktivne heuristike za probleme kombinatorne optimizacije u operacionom menadžmentu koji pripadaju klasi složenosti NP. Predstavljen je novi generalizovani konstruktivni algoritam koji omogućava da se raznovrsne heuristike formiraju izborom njegovih argumenata. Takođe je uvedeno opšte okruženje za generisanje permutacija, koje formira vezu između enumeracije permutacija i koraka u konstruktivnim heuristikama umetanja. Predložen je skup argumenata generalizovanog algoritma koji omogućuje paralelno praćenje više parcijalnih rešenja za vreme izvršavanja algoritma. Mogućnosti i prednosti generalizovanog algoritma su predstavljene kroz njegovu primenu na problem formiranja ćelija u proizvodnim sistemima, problem rasporeda proizvodnih ćelija i problem redosleda poslova u liniji. Novi pristup daje rešenja koja na ispitivanim primerima nadmašuju najbolje poznate rezultate iz literature., Operations manager deals with a collection of methods for getting things done more quickly, more cheaply or to a higher standard of quality. It is the job of the management scientist to make sure that these methods are practical and relevant. Almost always managers try to optimize something - whether to minimize the cost and energy consumption, or to maximize the profit, output, performance and efficiency. Subsequently, it is not always possible to find the optimal solutions. In practice, managers have to settle for suboptimal solutions or even feasible ones that are satisfactory, robust, and practically achievable in a reasonable time scale. These kind of solutions are obtained with heuristics, which can be constructive, improvement heuristics or hybrid. The field of research in the doctoral thesis are constructive heuristics for NP-hard combinatorial optimization problems in operations management. A new generalized constructive algorithm is presented which makes it possible to select a wide variety of heuristics just by the selection of its arguments values. A general framework for generating permutations of integers is presented. This framework forms a link between the numbering of permutations and steps in the insertion-based heuristics. A number of arguments controlling the operation of the generalized algorithm tracking multiple partial solutions, are identified. Features and benefits of the generalized algorithm are presented through the implemetations to the Cell Formation Problem, the Quadratic Assignment Problem and the Permutation Flowshop Problem. The new approach produces solutions that outperform, on the tested instances, the best known results from literature.

Операциони менаџер користи скуп поступака чији је циљ да се послови ураде брже, јефтиније и квалитетније. Научници из области операционог менаџмента имају задатак да ови поступци буду изводљиви и практични. Скоро увек, менаџери покушавају да нешто оптимизују – или је то минимизација трошкова и потрошње енергије, или пак, максимизација профита, резултата, перформанси и ефикасности. Међутим, није увек могуће пронаћи оптимална решења. У пракси, менаџер мора да се задовољи решењима која можда нису оптимална, али су допустива, задовољавајућа, робустна, и достижна у разумном времену. Оваква решења се добијају применама хеуристика, које могу бити конструктивне, побољшавајуће или хибридне. Област истраживања у докторској дисертацији су конструктивне хеуристике за проблеме комбинаторне оптимизације у операционом менаџменту који припадају класи сложености НП. Представљен је нови генерализовани конструктивни алгоритам који омогућава да се разноврсне хеуристике формирају избором његових аргумената. Такође је уведено опште окружење за генерисање пермутација, које формира везу између енумерације пермутација и корака у конструктивним хеуристикама уметања. Предложен је скуп аргумената генерализованог алгоритма који омогућује паралелно праћење више парцијалних решења за време извршавања алгоритма. Могућности и предности генерализованог алгоритма су представљене кроз његову примену на проблем формирања ћелија у производним системима, проблем распореда производних ћелија и проблем редоследа послова у линији. Нови приступ даје решења која на испитиваним примерима надмашују најбоље познате резултате из литературе., Operations manager deals with a collection of methods for getting things done more quickly, more cheaply or to a higher standard of quality. It is the job of the management scientist to make sure that these methods are practical and relevant. Almost always managers try to optimize something - whether to minimize the cost and energy consumption, or to maximize the profit, output, performance and efficiency. Subsequently, it is not always possible to find the optimal solutions. In practice, managers have to settle for suboptimal solutions or even feasible ones that are satisfactory, robust, and practically achievable in a reasonable time scale. These kind of solutions are obtained with heuristics, which can be constructive, improvement heuristics or hybrid. The field of research in the doctoral thesis are constructive heuristics for NP-hard combinatorial optimization problems in operations management. A new generalized constructive algorithm is presented which makes it possible to select a wide variety of heuristics just by the selection of its arguments values. A general framework for generating permutations of integers is presented. This framework forms a link between the numbering of permutations and steps in the insertion-based heuristics. A number of arguments controlling the operation of the generalized algorithm tracking multiple partial solutions, are identified. Features and benefits of the generalized algorithm are presented through the implemetations to the Cell Formation Problem, the Quadratic Assignment Problem and the Permutation Flowshop Problem. The new approach produces solutions that outperform, on the tested instances, the best known results from literature.

The goal of this paper is to continue our investigation of the heuristic approaches of solving thestochastic quadratic assignment problem (StoQAP) and provide additional insight into the behavior of di erentformulations that arise through the stochastic nature of the problem. The deterministic Quadratic AssignmentProblem (QAP) belongs to a class of well-known hard combinatorial optimization problems. Working with severalreal-world applications we have found that their QAP parameters can (and should) be considered as stochasticones. Thus, we review the StoQAP as a stochastic program and discuss its suitable deterministic reformulations.The two formulations we are going to investigate include two of the most used risk measures - Value at Risk(VaR) and Conditional Value at Risk (CVaR). The focus is on VaR and CVaR formulations and results of testcomputations for various instances of StoQAP solved by a genetic algorithm, which are presented and discussed.

У роботі запропоновано евристичний алгоритм розв’язання квадратичної задачі про призначення. На відміну від існуючих евристичних алгоритмів, які потребують визначення декількох вхідних параметрів, запропонований алгоритм використовуєлише один параметр і базується на ідеї використання комбінації локальних оптимумів в околі перестановок двох елементів. Прицьому він дозволяє отримати більш якісні розв’язки за дещо менший час в порівнянні з відомими алгоритмами., В работе предложен эвристический алгоритм решения квадратичной задачи о назначениях. В отличие от известных эвристических алгоритмов, требующих задания нескольких входных параметров, предлагаемый алгоритм использует только один параметр, и базируется на идее использования комбинации различных локальных оптимумов в окрестности перестановок двух элементов. При этом он позволяет получить более качественные решения за несколько меньшее время по сравнению с известными алгоритмами., The paper presents a new heuristic algorithm for the quadratic assignment problem. Unlike existing heuristic algorithms that require a few input parameters setting, the proposed algorithm uses only one parameter and is based on the idea of exploiting a combination of different local optima in the neighborhood of the two elements permutations. At the same time it allows to obtain solutions of better quality in slightly lesser time compared to the known algorithms.

Quadratic assignment problems (QAPs) are commonly solved by heuristic methods, where the optimum is sought iteratively. Heuristics are known to provide good solutions but the quality of the solutions, i.e., the confidence interval of the solution is unknown. This paper uses statistical optimum estimation techniques (SOETs) to assess the quality of Genetic algorithm solutions for QAPs. We examine the functioning of different SOETs regarding biasness, coverage rate and length of interval, and then we compare the SOET lower bound with deterministic ones. The commonly used deterministic bounds are confined to only a few algorithms. We show that, the Jackknife estimators have better performance than Weibull estimators, and when the number of heuristic solutions is as large as 100, higher order JK-estimators perform better than lower order ones. Compared with the deterministic bounds, the SOET lower bound performs significantly better than most deterministic lower bounds and is comparable with the best deterministic ones.

Pareto Local Search (PLS) is a simple and effective local search method for tackling multi-objective combinatorial optimization problems. It is also a crucial component of many state-of-the-art algorithms for such problems. However, PLS may be not very effective when terminated before completion. In other words, PLS has poor anytime behavior. In this paper, we study the effect that various PLS algorithmic components have on its anytime behavior. We show that the anytime behavior of PLS can be greatly improved by using alternative algorithmic components. We also propose Dynagrid, a dynamic discretization of the objective space that helps PLS to converge faster to a good approximation of the Pareto front and continue to improve it if more time is available. We perform a detailed empirical evaluation of the new proposals on the bi-objective traveling salesman problem and the bi-objective quadratic assignment problem. Our results demonstrate that the new PLS variants not only have significantly better anytime behavior than the original PLS, but also may obtain better results for longer computation time or upon completion., SCOPUS: ar.j, info:eu-repo/semantics/published

Quadratic assignment problems (QAPs) are commonly solved by heuristic methods, where the optimum is sought iteratively. Heuristics are known to provide good solutions but the quality of the solutions, i.e., the confidence interval of the solution is unknown. This paper uses statistical optimum estimation techniques (SOETs) to assess the quality of Genetic algorithm solutions for QAPs. We examine the functioning of different SOETs regarding biasness, coverage rate and length of interval, and then we compare the SOET lower bound with deterministic ones. The commonly used deterministic bounds are confined to only a few algorithms. We show that, the Jackknife estimators have better performance than Weibull estimators, and when the number of heuristic solutions is as large as 100, higher order JK-estimators perform better than lower order ones. Compared with the deterministic bounds, the SOET lower bound performs significantly better than most deterministic lower bounds and is comparable with the best deterministic ones.

Quadratic assignment problems (QAPs) are commonly solved by heuristic methods, where the optimum is sought iteratively. Heuristics are known to provide good solutions but the quality of the solutions, i.e., the confidence interval of the solution is unknown. This paper uses statistical optimum estimation techniques (SOETs) to assess the quality of Genetic algorithm solutions for QAPs. We examine the functioning of different SOETs regarding biasness, coverage rate and length of interval, and then we compare the SOET lower bound with deterministic ones. The commonly used deterministic bounds are confined to only a few algorithms. We show that, the Jackknife estimators have better performance than Weibull estimators, and when the number of heuristic solutions is as large as 100, higher order JK-estimators perform better than lower order ones. Compared with the deterministic bounds, the SOET lower bound performs significantly better than most deterministic lower bounds and is comparable with the best deterministic ones.

Quadratic assignment problems (QAPs) are commonly solved by heuristic methods, where the optimum is sought iteratively. Heuristics are known to provide good solutions but the quality of the solutions, i.e., the confidence interval of the solution is unknown. This paper uses statistical optimum estimation techniques (SOETs) to assess the quality of Genetic algorithm solutions for QAPs. We examine the functioning of different SOETs regarding biasness, coverage rate and length of interval, and then we compare the SOET lower bound with deterministic ones. The commonly used deterministic bounds are confined to only a few algorithms. We show that, the Jackknife estimators have better performance than Weibull estimators, and when the number of heuristic solutions is as large as 100, higher order JK-estimators perform better than lower order ones. Compared with the deterministic bounds, the SOET lower bound performs significantly better than most deterministic lower bounds and is comparable with the best deterministic ones.

The study of Stochastic Local Search (SLS) algorithms is becoming more pivotal these days, due to their vast number of applications in decision making. Prior to the implementation of algorithmic knowledge for decision making, many decisions were made based on manual calculation, on the fly, or even based on guts feeling. Nowadays, such an approach is more rarely seen, especially when the decisions that need to be made are high-risk, cost intensive, or time-consuming. The increasingly often used SLS algorithms are one of the options available to assist the decision making process these days.The work discussed in this thesis concerns the study of SLS algorithms for solving the Quadratic Assignment Problem (QAP), a prominent combinatorial optimization problem, which until today is very hard to solve. Our interest is to study the behavior and performance of SLS algorithms for solving QAP instances of different characteristics, such as size, sparsity, and structure. In this study, we have also proposed new variants of SLS algorithms, inspired by existing, well-performing SLS algorithms for solving the QAP. The new variants of SLS algorithms are then further extended for solving the bi-objective QAP (bQAP).One main focus in this study is to see how the performance of algorithms scales with instance size. We have considered instances that are much larger than the ones usually used in the studies of algorithms for solving the QAP. By understanding how the algorithms perform when the instance size changes, we might be able to solve other problems effectively by considering the similarity in their characteristics to the ones of the QAP, or by seeing common trends in the relative performance of the various available SLS methods. For single objective QAP instances we found that the structure and size of instances do have a significant impact on the performance of SLS algorithms. For example, comparisons between Tabu Search (TS) and Simulated Annealing (SA) on instances with ran, Doctorat en Sciences de l'ingénieur et technologie, info:eu-repo/semantics/nonPublished

Pareto Local Search (PLS) is a simple and effective local search method for tackling multi-objective combinatorial optimization problems. It is also a crucial component of many state-of-the-art algorithms for such problems. However, PLS may be not very effective when terminated before completion. In other words, PLS has poor anytime behavior. In this paper, we study the effect that various PLS algorithmic components have on its anytime behavior. We show that the anytime behavior of PLS can be greatly improved by using alternative algorithmic components. We also propose Dynagrid, a dynamic discretization of the objective space that helps PLS to converge faster to a good approximation of the Pareto front and continue to improve it if more time is available. We perform a detailed empirical evaluation of the new proposals on the bi-objective traveling salesman problem and the bi-objective quadratic assignment problem. Our results demonstrate that the new PLS variants not only have significantly better anytime behavior than the original PLS, but also may obtain better results for longer computation time or upon completion., SCOPUS: ar.j, info:eu-repo/semantics/published

Performance comparisons between algorithms have a long tradition in metaheuristic research. An early example is comparisons between Tabu Search (TS) and Simulated Annealing (SA) algorithms for tackling the Quadratic Assignment Problem (QAP). The results of these comparisons are to a certain extent inconclusive, even when focusing on only these two types of algorithms. While comparisons of SA and TS algorithms were based on rather small-sized instances, here we focus on possible dependencies of the relative performance between SA and TS algorithms on instance size. In fact, our experimental results show that the assertion whether one algorithm is better than the other can depend strongly on QAP instance size even if one focuses on instances with otherwise same characteristics. © 2013 Elsevier Ltd., SCOPUS: ar.j, info:eu-repo/semantics/published

We show that for every positive epsilon > 0, unless NP subset of BP QP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2log(1-epsilon)n by a reduction from the maximum label cover problem. Our result also implies that Approximate Graph Isomorphism is not robust and is, in fact, 1 - epsilon versus epsilon hard assuming the Unique Games Conjecture. Then, we present an O(root n)-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in state-of-the-art exact algorithms., QC 20141201

Performance comparisons between algorithms have a long tradition in metaheuristic research. An early example is comparisons between Tabu Search (TS) and Simulated Annealing (SA) algorithms for tackling the Quadratic Assignment Problem (QAP). The results of these comparisons are to a certain extent inconclusive, even when focusing on only these two types of algorithms. While comparisons of SA and TS algorithms were based on rather small-sized instances, here we focus on possible dependencies of the relative performance between SA and TS algorithms on instance size. In fact, our experimental results show that the assertion whether one algorithm is better than the other can depend strongly on QAP instance size even if one focuses on instances with otherwise same characteristics. © 2013 Elsevier Ltd., SCOPUS: ar.j, info:eu-repo/semantics/published

Signed graphs are graphs with an assignment of a positive or a negative sign to each edge. These graphs are helpful to represent different types of networks. For instance, they have been used in social networks, where a positive sign in an edge represents friendship between the two endpoints of that edge, while a negative sign represents enmity. Given a signed graph, an important question is how to embed such a graph in a metric space so that in the embedding every vertex is closer to its positive neighbors than to its negative ones. This problem is known as Sitting Arrangement (SA) problem and it was introduced by Kermarrec et al. (Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 388–399, 2011). Cygan et al. (Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2012) proved that the decision version of SA problem is NP-Complete when the signed graph has to be embedded into the Euclidean line. In this work, we study the minimization version of SA (MinSA) problem in the Euclidean line. We relate MinSA problem to the well known quadratic assignment (QA) problem. We establish such a relation by proving that local minimums in MinSA problem are equivalent to local minimums in a particular case of QA problem. In this document, we design two heuristics based on the combinatorial structure of MinSA problem. We experimentally compare their performances against heuristics designed for QA problem. This comparison favors the proposed heuristics.

Applying parameter adaptation means operating on parameters of an algorithm while it is tackling an instance. For ant colony optimization, several parameter adaptation methods have been proposed. In the literature, these methods have been shown to improve the quality of the results achieved in some particular contexts. In particular, they proved to be successful when applied to novel ant colony optimization algorithms for tackling problems that are not a classical testbed for optimization algorithms. In this paper, we show that the adaptation methods proposed so far do not improve, and often even worsen the performance when applied to high performing ant colony optimization algorithms for some classical combinatorial optimization problems. © 2011 Springer Science + Business Media, LLC., SCOPUS: ar.j, info:eu-repo/semantics/published

Applying parameter adaptation means operating on parameters of an algorithm while it is tackling an instance. For ant colony optimization, several parameter adaptation methods have been proposed. In the literature, these methods have been shown to improve the quality of the results achieved in some particular contexts. In particular, they proved to be successful when applied to novel ant colony optimization algorithms for tackling problems that are not a classical testbed for optimization algorithms. In this paper, we show that the adaptation methods proposed so far do not improve, and often even worsen the performance when applied to high performing ant colony optimization algorithms for some classical combinatorial optimization problems. © 2011 Springer Science + Business Media, LLC., SCOPUS: ar.j, info:eu-repo/semantics/published

Solving efficiently large benchmarks of NP-hard permutation-based problems requires the development of hybrid methods combining different classes of optimization algorithms. The key challenge here is how to find connections between the divergent search strategies used in each class of methods in order to build efficient hybridization strategies. Genetic algorithms (GAs) are very popular population-based metaheuristics based on stochastic evolutionary operators. The hybridization of GAs with tree-based exact methods such as Branch-and-Bound is a promising research trend. B&B algorithms are based on an implicit enumeration of the solution space represented as a tree. Our hybridization approach consists in providing a common solution and search space coding and associated search operators enabling an efficient cooperation between the two methods. The tree-based representation of the solution space is traditionally used in B&B algorithms to enumerate the solutions of the problem at hand. In this thesis, this special representation is adapted to metaheuristics. The encoding of permutations as natural numbers, which refer to their lexicographic enumeration in the tree, is proposed as a new way to represent the solution space of permutation problems in metaheuristics. Mapping functions between the two representations and special search operators are defined for general permutation problems. This common representation allows the design of efficient cooperation strategies between GAs and B&B algorithms. The proposed hybrid schemes have been parallelized and validated on standard benchmarks of the 3D quadratic assignment problem (Q3AP) using the computational grid Grid5000.

La finalidad de este proyecto es estudiar la aplicación de heurísticas al problema de asignación cuadrática QAP, más concretamente, analizar y comparar las heurísticas de búsqueda tabú, algoritmos genéticos y recocido simulado aplicadas al problema QAP y combinarlas entre ellas para formar metaheurísticas que mejoren los resultados obtenidos. El proyecto mostrará las características de cada algoritmo, su programación y validación del código fuente. Por último, se realizará una experiencia computacional para analizar su efectividad frente a los diferentes problemas propuestos., Este proyecto se ha concebido como el estudio de diferentes metaheurísticas aplicadas al problema de asignación cuadrática conocido por sus siglas en inglés QAP. El problema QAP es un problema tipo NP-Hard ya que no existe ningún algoritmo capaz de resolverlo en tiempo polinomial e incluso problemas pequeños requieren de gran tiempo computacional para su resolución. El problema se basa en la asignación de n diferentes entidades en n diferentes localidades en función de un coste. El objetivo es minimizar el coste de emplazamiento optimizando la combinatoria posible.

We introduce Generalized p-Hub Median Problem (GpHMP) that seeks to locate p hub nodes and install p distinct hub facilities/operators on the hubs while discount factor resulted by consolidation of flow on the hub links depends on the facilities/operators that are installed/operating on both hub nodes end-point. In contrast, in traditional hub location problems it is commonly assumed that all the hub facilities share a similar characteristic and economy of scale resulted by consolidation of flow over hub edges is not directly relevant to the hub facilities being installed at both end-points. The mathematical model is presented and numerical results on the instances of CAB and AP data sets are reported.

We introduce Generalized p-Hub Median Problem (GpHMP) that seeks to locate p hub nodes and install p distinct hub facilities/operators on the hubs while discount factor resulted by consolidation of flow on the hub links depends on the facilities/operators that are installed/operating on both hub nodes end-point. In contrast, in traditional hub location problems it is commonly assumed that all the hub facilities share a similar characteristic and economy of scale resulted by consolidation of flow over hub edges is not directly relevant to the hub facilities being installed at both end-points. The mathematical model is presented and numerical results on the instances of CAB and AP data sets are reported.

Přístupu dynamice a shlukování pro permutativní problémy je uveden v této publikaci. Algoritmus SOMA je upraven pomocí tohoto přístupu a prověřena na QAPproblému. Výsledky jsou podložené rozsáhlými experimenty., This paper introduces the primary research involving Self Organinsing Migrating Algorithm (SOMA) to the permutative problem of Quadratic Assign- ment. SOMA is transformed from its canonical form to successfully solve permuta- tive optimization problems. Conversion and repairment routines are added to the generic SOMA. The results presented outline the high effectiveness of SOMA for solving QAP problems.

Přístupu dynamice a shlukování pro permutativní problémy je uveden v této publikaci. Algoritmus SOMA je upraven pomocí tohoto přístupu a prověřena na QAPproblému. Výsledky jsou podložené rozsáhlými experimenty., This paper introduces the primary research involving Self Organinsing Migrating Algorithm (SOMA) to the permutative problem of Quadratic Assign- ment. SOMA is transformed from its canonical form to successfully solve permuta- tive optimization problems. Conversion and repairment routines are added to the generic SOMA. The results presented outline the high effectiveness of SOMA for solving QAP problems.

AMS classification: 90C22, 20Cxx, 70-08

We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: [R.E. Burkard, S.E. Karisch, F. Rendl. QAPLIB — a quadratic assignment problem library. Journal on Global Optimization, 10: 291–403, 1997]. AMS classification: 90C22, 20Cxx, 70-08.

This paper presents HAS-QAP, a hybrid ant colony system coupled with a local search, applied to the quadratic assignment problem. HAS-QAP uses pheromone trail information to perform modifications on QAP solutions, unlike more traditional ant systems that use pheromone trail information to construct complete solutions. HAS-QAP is analysed and compared with some of the best heuristics available for the QAP: two versions of tabu search, namely, robust and reactive tabu search, hybrid genetic algorithm, and a simulated annealing method. Experimental results show that HAS QAP and the hybrid genetic algorithm perform best on real world, irregular and structured problems due to their ability to find the structure of good solutions, while HAS-QAP performance is less competitive on random, regular and unstructured problems., info:eu-repo/semantics/published

This paper presents HAS-QAP, a hybrid ant colony system coupled with a local search, applied to the quadratic assignment problem. HAS-QAP uses pheromone trail information to perform modifications on QAP solutions, unlike more traditional ant systems that use pheromone trail information to construct complete solutions. HAS-QAP is analysed and compared with some of the best heuristics available for the QAP: two versions of tabu search, namely, robust and reactive tabu search, hybrid genetic algorithm, and a simulated annealing method. Experimental results show that HAS QAP and the hybrid genetic algorithm perform best on real world, irregular and structured problems due to their ability to find the structure of good solutions, while HAS-QAP performance is less competitive on random, regular and unstructured problems., info:eu-repo/semantics/published

We consider the plant layout problem for a job shop environment. This problem is generally treated as a quadratic assignment problem with the objective of minimizing material handling costs. In this paper we investigate conditions under which the quadratic assignment solution also minimizes average work-in-process. To get some initial insights, we model the plant as an open queueing network and show that under a certain set of assumptions, the problem of minimizing work-in-process reduces to the quadratic assignment problem. We then investigate via simulation the robustness of this result. We found that the relationship between material handling costs and average work-in-process holds under much more general conditions than are assumed in the analytical model. For those cases where the result does not hold, we have refined the model by developing a simple secondary measure which appears to work well in practice.

By considering the quadratic assignment problem (QAP) as that of minimizing the product of a distance-graph with a flow-graph several special cases of the QAP are investigated. A polynomial-growth algorithm is described for the QAP when the distance and flow-graphs are isomorphic trees. In the case when the graphs are single stars the algorithm becomes the well known rule for multiplying two sequences of numbers. The case of a complete distance-graph and a tree flow-graph becomes the travelling salesman problem when the tree is a hamiltonian chain and the flows are all unity. A dynamic programming algorithm is presented for the case of the flow-graph being a general tree with arbitrary flows. The very special case of 'narrow' bipartite graphs is also considered., Sponsored in part by Office of Naval Research, Arlington, Va. Prepared in cooperation with Imperial Coll. of Science and Technology, London (England).