Search

We commence an algorithmic study of Bulk-Robustness, a new model of robustness in combinatorial optimization. Unlike most existing models, Bulk-Robust combinatorial optimization features a highly nonuniform failure model. Instead of an interdiction budget, Bulk-Robust counterparts provide an explicit list of interdiction sets, comprising the admissible set of scenarios, thus allowing to model correlations between failures of different components in the system, interdiction sets of variable cardinality and more. The resulting model is suitable for capturing failures of complex structures in the system. We provide complexity results and approximation algorithms for Bulk-Robust counterparts of the Minimum Matroid Basis problems and the Shortest Path problem. Our results rely on various techniques, and outline the rich and heterogeneous combinatorial structure of Bulk-Robust optimization., Mathematical Programming, 149 (1-2), ISSN:0025-5610, ISSN:1436-4646

Το Shortest Superstring Problem (SSP) είναι ένα πρόβλημα συνδυαστικής βελτιστοποίησης που έχει προσελκύσει το ενδιαφέρων πολλών ερευνητών, λόγω των εφαρμογών του. Μπορεί να χρησιμοποιηθεί σε προβλήματα Υπολογιστικής Μοριακής Βιολογίας όπως η αλληλούχιση του DNA και σε προβλήματα της επιστήμης υπολογιστών όπως η συμπίεση δεδομένων. Το SSP είναι ένα NP-hard πρόβλημα. Ένα άρθρο ανασκόπησης για το SSP παρουσιάζεται στο πρώτο κεφάλαιο της παρούσας διατριβής με έναν περιεκτικό και σαφή τρόπο, καλύπτοντας ολόκληρη τη σχετική βιβλιογραφία, αναδεικνύοντας την κατακτημένη γνώση και βοηθώντας στην μελλοντική έρευνα.Η μέθοδος GRASP (Greedy Randomized Adaptive Search Procedure) είναι μια επαναληπτική ευρετική μέθοδος για συνδυαστική βελτιστοποίηση. Η μέθοδος Path Relinking (PR) αποτελεί έναν τρόπο ενοποίησης των στρατηγικών εντατικοποίησης και διαφοροποίησης στην αναζήτηση για βέλτιστες λύσεις. Η PR στα πλαίσια του GRASP εισήχθη ως μηχανισμός μνήμης για την αξιοποίηση των δεδομένων από καλές λύσεις που έχουν ήδη βρεθεί. Στο δεύτερο κεφάλαιο, παρουσιάζεται η υλοποίηση της μεθόδου GRASP με PR για το SSP. Η νέα μέθοδος λύνει στιγμιότυπα μεγάλης κλίμακας και υπερτερεί του φυσικού άπληστου αλγόριθμου στη συντριπτική πλειοψηφία των στιγμιοτύπων που δοκιμάστηκαν. Η προτεινόμενη μέθοδος είναι ικανή να παράγει πολλαπλές λύσεις κοντά στο βέλτιστο, γεγονός το οποίο είναι σημαντικό για την πρακτική της αλληλούχισης του DNA και επιτρέπει μια φυσική και εύκολη παράλληλη υλοποίηση. Ένα σύνολο αναφοράς στιγμιοτύπων με γνωστή βέλτιστη λύση κατασκευάστηκε χρησιμοποιώντας μια νέα Διατύπωση Ακέραιου Προγραμματισμού (Integer Programming Formulation) για το SSP.Η οικογένεια των γράφων επικάλυψης αποτελεί ένα κατάλληλο είδος δομής δεδομένων για την περίπτωση του SSP. Έχουν εφαρμογές στην αλληλούχιση γονιδιώματος, στην συμπίεση ακολουθιών και στον χρονοπρογραμματισμό μηχανών. Ένας κατευθυνόμενος γράφος με βάρη είναι γράφος επικάλυψης αν υπάρχει ένα σύνολο από ακολουθίες, οι οποίες βρίσκονται σε ένα προς ένα αντιστοιχία με τις κορυφές του γράφου, έτσι ώστε κάθε βάρος του γράφου να ισούται με την επικάλυψη μεταξύ των αντίστοιχων ακολουθιών. Στο τρίτο κεφάλαιο της παρούσας διατριβής, παρουσιάζεται ένα θεώρημα χαρακτηρισμού των γράφων επικάλυψης και ο αντίστοιχος αλγόριθμος αναγνώρισής τους.Το Quadratic Assignment Problem (QAP) είναι ένα από τα δυσκολότερα προβλήματα συνδυαστικής βελτιστοποίησης. Το QAP είναι ένα NP-hard πρόβλημα, ενώ η εύρεση ενός ε-προσεγγιστικού αλγόριθμου για αυτό είναι επίσης δύσκολη. Ο κλασικός άπληστος αλγόριθμος για διακριτά προβλήματα βελτιστοποίησης όπου η βέλτιστη λύση είναι ένα μεγιστοτικό ανεξάρτητο υποσύνολο ενός πεπερασμένου συνόλου βάσης με στοιχεία με βάρη, μπορεί να οριστεί με δύο διαφορετικούς τρόπους που είναι δυϊκοί ο ένας προς το άλλο. Τον άπληστο-εισαγωγής (greedy-in) αλγόριθμο, όπου μια λύση κατασκευάζεται από ένα κενό σύνολο με την εισαγωγή του επόμενου καλύτερου στοιχείου, ενός κάθε φορά, μέχρι να προκύψει μια μη εφικτή λύση και τον άπληστο-εξαγωγής (greedy-out) αλγόριθμο, όπου ξεκινώντας από το σύνολο βάσης, διαγράφεται το επόμενο χειρότερο στοιχείο, ένα κάθε φορά, μέχρι να προκύψει κάποια εφικτή λύση. Έχει αποδειχτεί ότι ενώ ο πρώτος αλγόριθμος παρέχει έναν παράγοντα προσέγγισης για τα προβλήματα μεγιστοποίησης, η απόδοσή του στην χειρότερη περίπτωση δεν είναι φραγμένη για τα προβλήματα ελαχιστοποίησης και το αντίστροφο για τον δεύτερο αλγόριθμο. Στο τέταρτο κεφάλαιο αυτής της διατριβής, παρουσιάζεται ο άπληστος-εξαγωγής αλγόριθμος για το QAP, αφότου αναπτύσσεται ένας συνδυαστικός χαρακτηρισμός των λύσεων του προβλήματος.

We introduce and study the combinatorial optimization problem with interaction costs (COPIC). COPIC is the problem of finding two combinatorial structures, one from each of two given families, such that the sum of their independent linear costs and the interaction costs between elements of the two selected structures is minimized. COPIC generalizes the quadratic assignment problem and many other well studied combinatorial optimization problems, and hence covers many real world applications. We show how various topics from different areas in the literature can be formulated as special cases of COPIC. The main contributions of this paper are results on the computational complexity and approximability of COPIC for different families of combinatorial structures (e.g. spanning trees, paths, matroids), and special structures of the interaction costs. More specifically, we analyze the complexity if the interaction cost matrix is parameterized by its rank and if it is a diagonal matrix. Also, we determine the structure of the intersection cost matrix, such that COPIC is equivalent to independently solving linear optimization problems for the two given families of combinatorial structures.

In this paper, a novel bi-level grouping optimization (BIGO) model is proposed for solving the storage location assignment problem with grouping constraint (SLAP-GC). A major challenge in this problem is the grouping constraint which restricts the number of groups each product can have and the locations of items in the same group. In SLAP-GC, the problem consists of two subproblems, one is how to group the items, and the other one is how to assign the groups to locations. It is an arduous task to solve the two subproblems simultaneously. To overcome this difficulty, we propose a BIGO. BIGO optimizes item grouping in the upper level, and uses the lower-level optimization to evaluate each item grouping. Sophisticated fitness evaluation and search operators are designed for both upper and lower level optimization so that the feasibility of solutions can be guaranteed, and the search can focus on promising areas in the search space. Based on the BIGO model, a multistart random search method and a tabu search algorithm are proposed. The experimental results on the real-world dataset validate the efficacy of the BIGO model and the advantage of the tabu search method over the random search method. © 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

The Travelling Salesman Problem (TSP) is an NP-hard problem with high number of possible solutions. The complexity increases with the factorial of n nodes in each specific problem. Meta-heuristic algorithms are an optimization algorithm that able to solve TSP problem towards a satisfactory solution. To date, there are many meta-heuristic algorithms introduced in literatures which consist of different philosophies of intensification and diversification. This paper focuses on 6 heuristic algorithms: Nearest Neighbor, Genetic Algorithm, Simulated Annealing, Tabu Search, Ant Colony Optimization and Tree Physiology Optimization. The study in this paper includes comparison of computation, accuracy and convergence.

The quadratic assignment problem (QAP) is a combinatorial optimization problem that arises in many real-world applications, such as equipment allocation in industry. The QAP is NP-hard and, in practice, one of the hardest combinatorial optimization problems to solve to optimality. Exact solutions of QAP are typically obtained by the branch-and-bound method. This method, however, potentially requires a high computational effort, and the use of good lower bounds is essential to prune the search tree. Branch-and-bound algorithms that use the dual-ascent procedure based on the level-2 reformulation linearization technique (RLT2) belong to the state of the art on exactly solving QAP. In this work, we propose a parallel implementation of that branch-and-bound algorithm. Our approach uses the Auction Algorithm of Bertsekas and Castañon to solve the linear assignment problems of RLT2, which allows us to take advantage of the massive parallel environment of graphics processing units to speed up the lower bound computation and implement some memory optimization techniques to address large-size problems. We report experimental results that show significant execution time reductions compared to previous works and allow us to provide, for the first time, exact solutions for two instances of QAP: tai35b and tai40b.

Complex combinatorial problems are most often optimised with heuristic solvers, which usually deliver acceptable results without any indication of the quality obtained. Recently, predictive diagnostic optimisation was proposed as a means of characterising the fitness landscape while optimising a combinatorial problem. The scalars produced by predictive diagnostic optimisation appear to describe the difficulty of the problem with relative reliability. In this study, we record more scalars that may be helpful in determining problem difficulty during the optimisation process and analyse these in combination with other well-known landscape descriptors by using exploratory factor analysis on four landscapes that arise from different search operators, applied to a varied set of quadratic assignment problem instances. Factors are designed to capture properties by combining the collinear variances of several variables. The extracted factors can be interpreted as the features of landscapes detected by the variables, but disappoint in their weak correlations with the result quality achieved by the optimiser, which we regard as the most reliable indicator of difficulty available. It appears that only the prediction error of predictive diagnostic optimisation has a strong correlation with the quality of the results produced, followed by a medium correlation of the fitness distance correlation of the local optima.

Mixed integer quadratic programs with quadratic constraints (MIQQP) occur frequently in various areas of engineering practice and management science, but most solution methods for this kind of problems are often designed for its special cases. In this paper, we present a simple global optimization algorithm for solving problem (MIQQP). We first convert problem (MIQQP) into an equivalent generalized bilinear programming problem with integer variables (EIQQP). We next show that replacing the quadratic objective and constraint functions with their convex envelopes is dominated by an alternative methodology based on convexifying the range of the bilinear terms on the feasible region. Finally, by incorporating the reduction-correction techniques and sampling strategies into the branch and bound scheme, the proposed algorithm is developed for solving (MIQQP). Convergence and optimality of the algorithm are presented and numerical examples taken from some recent literature and MINLPLib2 are carried out to validate the performance of the proposed algorithm.

A new location problem is formulated and solved. It is the continuous version of the grey pattern problem which is a special case of the Quadratic Assignment Problem. The problem is a minimization of a convex function subject to non-convex constraints and has infinitely many optimal solutions. We propose several mathematical programming formulations that are suitable for a multi-start heuristic algorithm. In addition to solving these formulations by the Solver in Excel and Mathematica, a special Nelder–Mead algorithm is proposed. This special algorithm provided the best results. One suggested modification may improve the performance of the Nelder–Mead algorithm for other optimization problems as well.

LibCoopt is an open-source matlab code library which provides a general and convenient tool to approximately solve the combinatorial optimization problems on the set of partial permutation matrices, which are frequently encountered in computer vision, bioinformatics, social analysis, etc. To use the library, the user needs only to give the objective function and its gradient function associated with the problem. Two typical problems, the subgraph matching problem and the quadratic assignment problem, are employed to illustrate how to use the library and also its flexibility on different types of problems.

This paper presents an artificial neural network to solve the quadratic zero-one programming problems under linear constraints. In this paper, by using the connection between integer and nonlinear programming, the quadratic zero-one programming problem is transformed into the quadratic programming problem with nonlinear constraints. Then, by using the nonlinear complementarity problem (NCP) function and penalty method this problem is transformed into an unconstrained optimization problem. It is shown that the Hessian matrix of the associated function in the unconstrained optimization problem is positive definite in the optimal point. To solve the unconstrained optimization problem an artificial neural network is used. The proposed neural network has a simple structure and a low complexity of implementation. It is shown here that the proposed artificial neural network is stable in the sense of Lyapunov. Finally, some numerical examples are given to show that the proposed model finds the optimal solution of this problem in the low convergence time.

A new repeated iterated tabu search for the quadratic assignment problem is developed. A comparative study of this algorithm and the best existing algorithms for solving this problem has shown its competitiveness with respect to both its performance and quality of solutions.

In this article, we will examine whether the Problem Aware Local Search, an efficient method initially proposed for the DNA Fragment Assembly Problem, can also be used in other application domains and with other optimization problems. The main idea is to maintain the key features of PALS and apply it to different permutation-based combinatorial problems. In order to carry out a comprehensive analysis, we use a wide benchmark of well-known problems with different kinds of variation operators and fitness functions, such as the Quadratic Assignment Problem, the Flow Shop Scheduling Problem, and the Multiple Knapsack Problem. We also discuss the main design alternatives for building an efficient and accurate version of PALS for these problems in a competitive manner. In general, the results show that PALS can achieve high-quality solutions for these problems and do it efficiently.

In this paper we study the effect of a decision maker׳s risk attitude on the median and center problems, two well-known location problems, with uncertain demand in the mean–variance framework. We provide a mathematical programming formulation for both problems in the form of quadratic programming and develop solution procedures. In particular, we consider the vertex and absolute median problems separately, and identify a dominant set for the center problem. Glover׳s linearization method is applied to solve the vertex median problem. We also develop a branch and bound algorithm and a heuristic as the linearization technique takes too long for the vertex median problem on large networks. A computational experiment is conducted to compare the performance of the algorithms. We demonstrate the importance of taking into account the volatility and correlation structure when a location decision is made. The closest assignment property is also discussed for these location problems under the mean–variance objective.

We consider the boolean quadratic programming problem with generalized upper bound constraints (BQP-GUB) which subsumes the well-known quadratic semi-assignment problem. BQP-GUB has applications in engineering, production planning and biology. We present various complexity results on the problem along with different metaheuristic algorithms. Results of extensive experimental analysis are presented demonstrating the efficacy of our proposed algorithms.

A new version of BLS algorithm is introduced.Levenshtein Distance (LD) metric is applied to the BLS heuristic.The QAP is optimized with several processors using OpenMP.Significant improvements are obtained.The BLS-OpenMP can be reported as one of the best heuristics for the QAP. The Quadratic Assignment Problem (QAP) is one of the most challenging NP-Hard combinatorial optimization problems. Circuit-layout design, transportation/traffic engineering, and assigning gates to airplanes are some of the interesting applications of the QAP. In this study, we introduce an enhanced version of a recent local search heuristic, Breakout Local Search Algorithm (BLS), by using the Levenshtein Distance metric for checking the similarity of the new starting points to previously explored QAP permutations. The similarity-checking process prevents the local search algorithm, BLS, from getting stuck in already-explored areas. In addition, the proposed BLS Algorithm (BLS-OpenMP) incorporates multi-threaded computation using OpenMP. The stagnation-aware search for the optimal solutions of the QAP is executed concurrently on several cores with diversified trajectories while considering their similarity to already-discovered local optima. The exploration of the search space is improved by selecting the starting points intelligently and speeding up the fitness evaluations linearly with number of processors/threads. BLS-OpenMP has been tested on the hardest 59 problem instances of the QAPLIB, and it obtained 57 of the best known results. The overall deviation of the achieved solutions from the best known results is 0.019% on average, which is a significant improvement compared with state-of-the-art algorithms.

In this paper, we address continuous, integer and combinatorial k-sum optimization problems. We analyze different formulations of this problem that allow to solve it through the minimization of a relatively small number of minisum optimization problems. This approach provides a general tool for solving a variety of k-sum optimization problems and at the same time, improves the complexity bounds of many ad-hoc algorithms previously reported in the literature for particular versions of this problem. Moreover, the results developed for k-sum optimization have been extended to the more general case of the convex ordered median problem, improving upon existing solution approaches.

Combinatorially complex problems are often optimised with heuristic solvers which generally provide acceptable results but no indication as to how the quality achieved compares to the best possible. In previous work we have introduced Predictive Diagnostic Optimisation (PDO), a heuristic based on local search that provides information about the search space structure through a set of indicators whilst searching for the optimal solution. PDO can collect useful information about the search process, such as the variation in the number of steps needed to locally optimise a random solution and the error between the expected and actual qualities of the local optimum, known as the prediction error. Given previous experimental results on the quadratic assignment problem, it appears that a high prediction error coincides with lower search quality and vice versa. This work confirms this assumption with the help of two additional problems but also shows that the reliability of the prediction error is challenged by structural properties that lead to a homogeneity of the optima basins. Conversely, a high variation in the number of steps that lead to the local optima increases the reliability of the prediction error as an indicator of search quality.

The generalized quadratic assignment problem (GQAP) is the task of assigning a set of facilities to a set of locations such that the sum of the assignment and transportation costs is minimized. The facilities may have different space requirements, and the locations may have varying space capacities. Also, multiple facilities may be assigned to each location such that space capacity is not exceeded. In this paper, an application of the GQAP is presented for assigning a set of machines to a set of locations on the plant floor. Construction algorithms and a simple tabu search heuristic are developed for the GQAP. A set of test problems available in the literature was used to evaluate the performances of the TS heuristic using different construction algorithms. The results show that the simple TS heuristic is effective for solving the GQAP.

We review some complexity results and present a viable heuristic approach based on the Variable Neighborhood Search (VNS) framework for multimode extension of combinatorial optimization problems, such as the the Set Covering Problem (SCP) and the Covering Location Problem (CLP).

Methods of tropical (idempotent) mathematics are applied to the solution of minimax location problems under constraints on the feasible location region. A tropical optimization problem is first considered, formulated in terms of a general semifield with idempotent addition. To solve the optimization problem, a parameter is introduced to represent the minimum value of the objective function, and then the problem is reduced to a parametrized system of inequalities. The parameter is evaluated using existence conditions for solutions of the system, whereas the solutions of the system for the obtained value of the parameter are taken as the solutions of the initial optimization problem. Then, a minimax location problem is formulated to locate a single facility on a line segment in the plane with a rectilinear metric. When no constraints are imposed, this problem, which is also known as the Rawls problem or the messenger boy problem, has known geometric and algebraic solutions. For the location problems, where the location region is restricted to a line segment, a new solution is obtained, based on the representation of the problems in the form of the tropical optimization problem considered above. Explicit solutions of the problems for various positions of the line are given both in terms of tropical mathematics and in the standard form.

In this paper, we show that the quadratic assignment problem (QAP) can be reformulated to an equivalent rank constrained doubly nonnegative (DNN) problem. Under the framework of the difference of convex functions (DC) approach, a semi-proximal DC algorithm (DCA) is proposed for solving the relaxation of the rank constrained DNN problem whose subproblems can be solved by the semi-proximal augmented Lagrangian method (sPALM). We show that the generated sequence converges to a stationary point of the corresponding DC problem, which is feasible to the rank constrained DNN problem. Moreover, numerical experiments demonstrate that for most QAP instances, the proposed approach can find the global optimal solutions efficiently, and for others, the proposed algorithm is able to provide good feasible solutions in a reasonable time., Comment: 24 pages, 1 figure

A quadratic assignment problem (QAP), which is a combinatorial optimisation problem, is developed to model the problem of locating facilities with material flows between them. The aim of solving the QAP formulation for a facility layout problem (FLP) is to increase a system’s operating efficiency by reducing material handling costs, which can be measured by interdepartmental distances and flows. The QAP-formulated FLP can be viewed as a discrete optimisation problem, where the quadratic objective function is optimised with respect to discrete decision variables subject to linear equality constraints. The conventional approach for solving this discrete optimisation problem is to use the linearisation of the quadratic objective function whereby additional discrete variables and constraints are introduced. The adoption of the linearisation process can result in a significantly increased number of variables and constraints; solving the resulting problem can therefore be challenging. In this paper, a new appro...

The Quadratic Assignment Problem (QAP) is a well-known NP -hard combinatorial optimization problem that has received a lot of attention from the research community since it has many practical applications, such as allocation of facilities, design of electronic devices, etc. In this paper, we propose a hybrid approximate approach for the QAP based upon the framework of the Biased Random Key Genetic Algorithm. This hybrid approach includes an improvement method to be applied over the best individuals of the population in order to exploit the promising regions found in the search space. In the computational experiments, we evaluate the performance of our approach on widely known instances from the literature. In these experiments, we compare our approach against the best proposals from the related literature and we conclude that our approach is able to report high-quality solutions by means of short computational times.

The idea of k-adaptability in two-stage robust optimization is to calculate a fixed number k of second-stage policies here-and-now. After the actual scenario is revealed, the best of these policies is selected. This idea leads to a min---max---min problem. In this paper, we consider the case where no first stage variables exist and propose to use this approach to solve combinatorial optimization problems with uncertainty in the objective function. We investigate the complexity of this special case for convex uncertainty sets. We first show that the min---max---min problem is as easy as the underlying certain problem if k is greater than the number of variables and if we can optimize a linear function over the uncertainty set in polynomial time. We also provide an exact and practical oracle-based algorithm to solve the latter problem for any underlying combinatorial problem. On the other hand, we prove that the min---max---min problem is NP-hard for every fixed number k, even when the uncertainty set is a polyhedron, given by an inner description. For the case that k is smaller or equal to the number of variables, we finally propose a fast heuristic algorithm and evaluate its performance.

We consider a relaxation of the quadratic assignment problem without the constraint on the number of objects assigned to a specific position. This problem is NP-hard in the general case. To solve the problem, we propose a polynomial algorithm with guaranteed posterior accuracy estimate; we distinguish a class of problems with special assignment cost functions where the algorithm is 2-approximate. We show that if the graph in question contains one simple loop, and the set of assignment positions is a metric space, the proposed algorithm is 2-approximate and guaranteed to be asymptotically exact. We conduct a computational experiment in order to analyze the algorithm's errors and evaluate its accuracy.

In the classical min-max approach to robust combinatorial optimization, a single feasible solution is computed that optimizes the worst case over a given set of considered scenarios. As is well known, this approach is very conservative, leading to solutions that in the average case are far from being optimal. In this paper, we present a different approach: the objective is to compute k feasible solutions such that the best of these solutions for each given scenario is worst-case optimal, i.e., we model the problem as a min-max-min problem. In practice, these k solutions can be computed once in a preprocessing phase, while choosing the best of the k solutions can be done in real time for each scenario occuring. Using a polynomial-time oracle algorithm, we show that the problem of choosing k min-max-min optimal solutions is as easy as the underlying combinatorial problem if k ≥ n + 1 and if the uncertainty set is a polytope or an ellipsoid. On contrary, in the discrete scenario case, many tractable problems such as the shortest path problem or the minimum spanning tree problem turn NP-hard in the new approach.

This study proposes a new approach combining the chemical reaction optimization framework with the unified tabu search (UTS) heuristic to solve the capacitated vehicle routing problem (CVRP). The CVRP is one of the most well-studied problems not only because of its real-life applications but also due to the fact that the CVRP could be used to evaluate the efficiency of new algorithms and optimization methods. Chemical reaction optimization (CRO) is a new optimization framework mimicking the nature of chemical reactions. The CRO method has proved to be very effective for solving NP-hard optimization problems such as the quadratic assignment problem, neural network training, the knapsack problem, and the traveling salesman problem. We also present the design of elementary chemical reaction operations, the adaptation of the UTS algorithm to educate solutions in these operations. Finally, a thorough testing against well-known benchmark problems has been conducted. Experimental results show that the proposed algorithm is efficient and highly competitive in comparison with several prominent algorithms for this problem. The presented methodology may be a fine approach for developing similar algorithms to address other routing variants.

In this paper, we study the problem of minimizing the ratio of two complex indefinite quadratic functions subject to a strictly convex quadratic constraint. First, using the known method due to Dinkelbach, we reformulate the fractional problem as a univariate equation. To find the root of the univariate equation, the generalized Newton method is utilized that requires solving a nonconvex quadratic optimization problem at each iteration. To solve these nonconvex quadratic problems, we present an efficient algorithm by a diagonalization scheme that requires solving a univariate minimization problem at each iteration. Moreover, for the homogeneous case, it requires solving a simple linear optimization problem. Our preliminary numerical experiments on several randomly generated test problems show that, the new approach is much faster in finding the global optimal solution than the known semidefinite relaxation approach, especially when solving large scale problems.

Linear unconstrained problem of combinatorial optimization on arrangements under stochastic uncertainty is being solved. The minimum is defined as the result of sequential comparison of numerical characteristics of random variables. The properties of the solution of the optimization problem under study are obtained. These properties use the properties of special constructed deterministic problems. The authors also propose the reduction method to solve linear unconstrained problem of combinatorial stochastic optimization, which is based on obtained solution's properties.

In this paper we introduce a new approach to solve fuzzy assignment problem namely, ones assignment method. Considering each fuzzy cost as a triangular fuzzy numbers the fuzzy assignment problem has been transformed into crisp values by using linguistic variables and ranking techniques and then it is solved by ones assignment method. The proposed method is a systematic procedure, easy to apply and can be utilized for all types of assignment problem with maximize or minimize objective functions. At the end, this method is illustrated with some numerical example

A generic scheme is proposed for designing and classifying simple probabilistic population-based optimization (SPPBO) algorithms that use principles from population-based ant colony optimization (PACO) and simplified swarm optimization (SSO) for solving combinatorial optimization problems. The scheme, called SPPBO, identifies different types of populations (or archives) and their influence on the construction of new solutions. The scheme is used to show how SSO can be adapted for solving combinatorial optimization problems and how it is related to PACO. Moreover, several new variants and combinations of these two metaheuristics are generated with the proposed scheme. An experimental study is done to evaluate and compare the influence of different population types on the optimization behavior of SPPBO algorithms, when applied to the traveling salesperson problem and the quadratic assignment problem.

The paper establishes the necessary condition for the solution of a linear unconditional problem of combinatorial optimization on arrangements where coefficients of objective function are positive. These results are used to establish the properties of the solution of linear unconditional optimization problem on arrangements for the case where probabilistic uncertainty takes place in the definition of the feasible domain and the minimum is defined according to the linear order introduced on the set of discrete random variables: we formulate and prove the condition that can underlie the search for solution and the ways of constructing the solution in some special cases.

The doubly constrained entropy distribution/assignment (DEDA) problem that combines a gravity-based trip distribution (TD) problem and a traffic assignment (TA) problem has long been formulated as an optimization model and solved by two solution algorithms, i.e., partial- and full-linearization solution algorithms. As an alternative, this research first treats the DEDA problem by the augmented Lagrangian dual (ALD) method as the singly constrained entropy distribution/assignment (SEDA) problem, which in turn is addressed, via a tactical supernetwork representation, as an “extended” 1-origin-to-1-destination TA problem. A quick-precision TA solution algorithm, − called TAPAS (Traffic Assignment by Paired Alternative Segments), − is then adopted for solutions. The proposed approach is demonstrated with a numerical example for the correctness of the result, using Lingo 11 solver and the partial linearization solution (PLS) algorithm. Moreover, through the use of TAPAS in the innermost loop, the proposed approach also has the merit of generating unique path flow solution, which is very useful in route guidance under the intelligent transportation systems environment, among other academic applications. In addition, the proposed approach can be easily applied, or with minor modification at most, to various combined models in travel demand forecasting.

In this paper Branch and bound technique is applied to assignment problem with fuzzy cost with objective to minimise cost, fuzzy cost is assumed as triangular fuzzy number, Yager’s ranking method has been used for ranking the fuzzy numbers, after transforming assignment problem into a crisp one using linguistic variables, assignment problem is solved by branch and bound technique. To deal with fuzzy assignment problem with qualitative data, linguistic variable helps to convert qualitative data into quantitative data.

A new probability-based approach is proposed for the learning in discrete PSO.A generic framework is proposed to discretize PSO and its variants.Five well-known PSO variants are discretized based on the proposed framework.Comparative evaluation and search landscapes analysis is presented. The Quadratic Assignment Problem (QAP) has attracted considerable research efforts due to its importance for a number of real life problems, in addition to its acknowledged difficulty. Almost all of the well-known nature-mimicking algorithms have been applied to solve the QAP. However, the Particle Swarm Optimization (PSO), which has proven to be very effective in various applications, has received little attention at this front. The reason can be ascribed to the Euclidian-distance based learning concept (at the core of the algorithm) which makes PSO, in its present form, unsuitable for combinatorial optimization problems. In this article, a new probability-based approach is proposed for the learning in PSO. Based on this learning concept, a generic framework is developed to discretize PSO and its variants, to make them suitable for combinatorial optimization. Five well-known PSO variants are discretized based on this proposed framework. A comparative study of all discretized PSO variants is also included. Moreover, the proposed framework is compared to other attempts to discretize PSO, in addition to three other meta-heuristic approaches. The comparison revealed that the proposed technique is more effective.

Many important integer and mixed-integer programming problems are difficult to solve. A representative example is unit commitment with combined cycle units and transmission capacity constraints. Complicated transitions within combined cycle units are difficult to follow, and system-wide coupling transmission capacity constraints are difficult to handle. Another example is the quadratic assignment problem. The presence of cross-products in the objective function leads to nonlinearity. In this study, building upon the novel integration of surrogate Lagrangian relaxation and branch-and-cut, such problems will be solved by relaxing selected coupling constraints. Monotonicity of the relaxed problem will be assumed and exploited and nonlinear terms will be dynamically linearised. The linearity of the resulting problem will be exploited using branch-and-cut. To achieve fast convergence, guidelines for selecting stepsizing parameters will be developed. The method opens up directions for solving nonlinear mixed-in...

Quadratic Assignment Problems (QAPs) are the hardest of combinatorial optimization problems, with some problems of sizes of the order of 30 still remaining unsolved optimally. Solving these problems with exact optimization methods is cumbersome and hence the use of non-traditional optimization methods is advisable. The discrete version of Particle Swarm Optimization (DPSO) is a widely accepted non-conventional optimization algorithm for combinatorial optimization problems. This paper uses Taguchi's robust design approach to determine the best combination of parameters for discrete particle swarm optimization algorithm for solving quadratic assignment problems.

Generally, the optimal solution of assignment problem can be obtained by Hungarian algorithm of two-sided optimization with time complexity . This paper suggests one-sided optimal assignment and swap optimization algorithm with time complexity can be achieve the goal of two-sided optimization. This algorithm selects the minimum cost for each row, and reassigns over-assigned to under-assigned cell. Next, that verifies the existence of swap optimization candidates, and swap optimizes with . For 27 experimental data, the swap-optimization performs only 22% of data, and 78% of data can be get the two-sided optimal result through one-sided optimal result. Also, that can be improves on the solution of best known solution for partial problems.

Evolutionary algorithms EAs are often employed to multiobjective optimization, because they process an entire population of solutions which can be used as an approximation of the Pareto front of the tackled problem. It is a common practice to couple local search with evolutionary algorithms, especially in the context of combinatorial optimization. In this paper a new local search method is proposed that utilizes the knowledge concerning promising search directions. The proposed method can be used as a general framework and combined with many methods of iterating over a neighbourhood of an initial solution as well as various decomposition approaches. In the experiments the proposed local search method was used with an EA and tested on 2-, 3-and 4-objective versions of two well-known combinatorial optimization problems: the travelling salesman problem TSP and the quadratic assignment problem QAP. For comparison two well-known local search methods, one based on Pareto dominance and the other based on decomposition, were used with the same EA. The results show that the EA coupled with the directional local search yields better results than the same EA coupled with any of the two reference methods on both the TSP and QAP problems.

Graph theory has been a powerful tool in solving difficult and complex problems arising in all disciplines. In particular, graph matching is a classical problem in pattern analysis with enormous applications. Many graph problems have been formulated as a mathematical program then solved using exact, heuristic and/or approximated-guaranteed procedures. On the other hand, graph theory has been a powerful tool in visualizing and understanding of complex mathematical programming problems, especially integer programs. Formulating a graph problem as a natural integer program (IP) is often a challenging task. However, an IP formulation of the problem has many advantages. Several researchers have noted the need for natural IP formulation of graph theoretic problems. The aim of the present study is to provide a unified framework for IP formulation of graph matching problems. Although there are many surveys on graph matching problems, however, none is concerned with IP formulation. This paper is the first to provide a comprehensive IP formulation for such problems. The framework includes variety of graph optimization problems in the literature. While these problems have been studied by different research communities, however, the framework presented here helps to bring efforts from different disciplines to tackle such diverse and complex problems. We hope the present study can significantly help to simplify some of difficult problems arising in practice, especially in pattern analysis.

We consider the bilevel assignment problem in which each decision maker (i.e., the leader and the follower) has its own objective function and controls a distinct set of edges in a given bipartite graph. The leader acts first by choosing some of its edges. Subsequently, the follower completes the assignment process. The edges selected by the leader and the follower are required to constitute a perfect matching. In this paper we propose an exact solution approach, which is based on a branch-and-bound framework and exploits structural properties of the assignment problem. Extensive computational experiments with linear sum and linear bottleneck objective functions are conducted to demonstrate the performance of the developed methods. While the considered problem is known to be NP-hard in general, we also describe some restricted cases that can be solved in polynomial time.

This paper presents the development of a novel vehicle-routing-based algorithm for optimizing component pick-up and placement on a collect-and-place type machine in printed circuit board manufacturing. We present a two-phase heuristic that produces solutions of remarkable quality with respect to other known approaches in a reasonable amount of computational time. In the first phase, a construction procedure is used combining greedy aspects and solutions to subproblems modeled as a generalized traveling salesman problem and quadratic assignment problem. In the second phase, this initial solution is refined through an iterative framework requiring an integer programming step. A detailed description of the heuristic is provided and extensive computational results are presented.

The paper proposes a new method to solve the assignment problem based on recursive derivation of the optimal solution. The assignment problem is formulated in the rearrangement matrix form that allows the use of the matrix approach to optimal solution. The algorithm is to find the minimum total weight matching in the bipartite graph with 2n vertices. The computational scheme of the recurrence method for solving the assignment problem is presented in the form adapted for implementation on a computer.

The quadratic matching problem (QMP) asks for a matching in a graph that optimises a quadratic objective in the edge variables. The QMP generalises the quadratic assignment problem as the latter can be seen as a perfect matching on a bipartite graph. In our approach, we strengthen the linearised IP-formulation by cutting planes that are derived from facets of the corresponding matching problem where only one quadratic term is present in the objective function (QMP1). As the influence of these cutting planes on the root bound decreases for instances with more quadratic terms in the objective, we present different methods to strengthen these cutting planes. Adopting the idea of the reformulation linearisation technique (RLT) we derive valid inequalities for the general QMP from QMP1 facets. Following the approach in Fomeni et?al. (2015) we replace cubic terms that appear in a reformulated QMP1 inequality by a quadratic estimator. Based on these methods we design and implement an exact branch-and-cut approach. When compared to solving the standard linearised IP formulation strengthened by cutting planes that result from the application of the RLT to the degree inequalities, we show that root bounds and cpu times for solving instances to optimality can significantly be improved, when the new method is applied.

Graphical abstractDisplay Omitted HighlightsA hybrid method combining great deluge and tabu search algorithms is proposed.This hybrid is supported with a two-stage external memory.First stage of acts as a short term memory that is frequently updated.Second stage acts as a long term memory that is updated less frequently.Elements of the second stage are maximally dissimilar in variable space. A two-stage memory architecture is maintained within the framework of great deluge algorithm for the solution of single-objective quadratic assignment problem. Search operators exploiting the accumulated experience in memory are also implemented to direct the search towards more promising regions of the solution space. The level-based acceptance criterion of the great deluge algorithm is applied for each best solution extracted in a particular iteration. The use of short- and long-term memory-based search supported by effective move operators resulted in a powerful combinatorial optimization algorithm. A successful variant of tabu search is employed as the local search method that is only applied over a few randomly selected memory elements when the second stage memory is updated. The success of the presented approach is illustrated using sets of well-known benchmark problems and evaluated in comparison to well-known combinatorial optimization algorithms. Experimental evaluations clearly demonstrate that the presented approach is a competitive and powerful alternative for solving quadratic assignment problems.

In this paper, we investigate the energy-efficient resource allocation problem in a single-cell orthogonal frequency division multiple access (OFDMA) system to achieve the energy efficiency (EE) tradeoff among users. Rather than overall system EE, our objective is to maximize the EE for each individual user. Therefore, a multiple-objective optimization problem is formulated, which in general has many Pareto optimal solutions and is hard to solve. To find its solution, we first convert it into two different single-objective optimization problems using the weighted-sum approach and the max-min approach, respectively. The single-objective optimization problems are non-convex due to the combinatorial channel allocation variables. Therefore, for both problems, we first provide an upper bound algorithm by relaxing the combinatorial variables and then develop a suboptimal heuristic algorithm. The sum-of-ratios optimization and the generalized fractional programming are utilized for the weighted-sum problem and the max-min problem, respectively. Numerical results demonstrate that both the weighted-sum and the max-min approaches can effectively solve the EE maximization problem, and the suboptimal heuristic algorithms can achieve a close performance to the corresponding upper bound algorithm.