Search

The problem of finding optimal block designs can be formulated as a combinatorial optimization, but its resolution is still a formidable challenge. This paper presents a general and user-friendly algorithm, namely Modified Particle Swarm Optimization (MPSO), to construct optimal or near-optimal block designs. It can be used for several classes of block designs such as binary, non-binary and test-control block designs with correlated or uncorrelated observations. In order to evaluate the algorithm, we compare our results with the optimal designs presented in some published papers. An advantage of our algorithm is its independency to the sizes of blocks and the structure of correlations. [ABSTRACT FROM AUTHOR]

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1 / 2 -approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively. Unfortunately, a recent work Konrad and Naidu (Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX/RANDOM 2021, August 16–18, 2021. LIPIcs, vol 207, pp 19:1–19:18, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.19) shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1 / 2 -approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms were previously known, and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs. The main significance of our results is not in the numerical improvements, but in demonstrating the potential of non-maximal-matching-first algorithms. [ABSTRACT FROM AUTHOR]

The Digital Annealer is a CMOS hardware designed by Fujitsu Laboratories for high-speed solving of Quadratic Unconstrained Binary Optimization (QUBO) problems that could be difficult to solve by means of existing general-purpose computers. In this paper, we present a mathematical description of the first-generation Digital Annealer's Algorithm from the Markov chain theory perspective, establish a relationship between its stationary distribution with the Gibbs-Boltzmann distribution, and provide a necessary and sufficient condition on its cooling schedule that ensures asymptotic convergence to the ground states. [ABSTRACT FROM AUTHOR]

Nodes localization has been a critical subject in wireless sensor network (WSN) field. As far as existing localization algorithms are concerned, distance vector hop (DV-Hop) has the advantages of no extra hardware and implementation simplicity, however its localization accuracy cannot meet some specific requirements. In order to enhance the accuracy of WSN nodes localization, a DV-Hop based localization algorithm based on nodes negotiation and multi communication radii (NNMCR DV-Hop) is proposed in this paper. Firstly, the hop counts between WSN nodes is modified from an integer to a decimal by changing communication radius of anchor nodes through nodes negotiation. By refining the hop counts, the accuracy of the estimated distance from the unknown to the anchor nodes is improved. Secondly, the calculation of the average hop size of the anchor node is abstracted into a combinatorial optimization problem which is solved by using binary particle swarm optimization (BPSO) to improve the accuracy of the estimated distance which is between the anchor and the unknown node. Finally, when calculating the coordinates of unknown nodes, only the anchor nodes with smaller hop counts are selected to participate in the calculation. Simulation experiments show that compared with the original DV-Hop as well as other improved algorithms based on DV-Hop, NNMCR DV-Hop greatly improves the localization accuracy of unknown nodes without additional hardware. [ABSTRACT FROM AUTHOR]

This paper presents a Q-learning-based algorithm for sequence and orientation optimization toward the 2D rectangular strip packing problem. The width-filled skyline is used to represent the interior packing state, and a constructive rectangular packing algorithm with the commonly adopted fitness evaluation for placement is designed. Then, the consecutive item packing is simulated as Markov Decision Process, where the state is defined as the set of already packed items, and the action is defined as the rectangle selected to be packed along with its orientation. We propose the reverse updating of Q-value in the paradigm of Q-learning and use the algorithm to optimize the sequence and orientation of the rectangles. The decreasing-size-choice mechanism in Q-learning is studied on randomly generated problems to optimize the setting of ε-greedy policy. We also test the Q-learning-based algorithm on the benchmark instances of C21, N13, N-series from NT, Cgcut and Beng. Compared with a few state-of-the-art algorithms, the computational results show that the proposed algorithm can produce good packing quality when adequate execution time allowed. [ABSTRACT FROM AUTHOR]

Recently, substantial progress has been made in developing efficient algorithms for solving combinatorial optimization problems. In this paper, following this direction, the problem of designing supply chains which is an important combinatorial optimization problem is considered. The structural properties of supply chain models are investigated to transform such models into a generalized network optimization model. The transformation to a generalized network optimization model reduces the algorithms' solution time. Moreover, this paper proposes a new efficient hybrid algorithm based on tabu search and generalized network simplex algorithm (GN-TSA) for designing multi-objectives supply chain models. The developed algorithm's parameters are tuned properly, validated, and evaluated. The algorithm's performance is then compared to an exact algorithm embedded in the General Algebraic Modeling System (GAMS) and two metaheuristic algorithms, namely a linear programming simplex algorithm integrated with the tabu search approach (LP-TSA) and simulated annealing. The findings indicated that the GN-TSA obtains solutions very close to the exact algorithm with less computation time. In addition, the proposed algorithm outperforms the LP-TSA and simulated annealing in terms of computation time, while the quality of the solutions is the same as solutions obtained by LP-TSA and better than simulated annealing. On average, the results revealed that the reduction in computational time is more than 26.30% using GN-TSA compared to LP-TSA and simulated annealing. [ABSTRACT FROM AUTHOR]

A hybrid algorithm combines two or more individual algorithms in order to integrate the advantages of these individual algorithms. In recent years, a huge number of hybrid algorithms have been proposed, and their efficiencies have been demonstrated by experimental studies. However, few theoretical results that support the experimental conclusions are available. In this paper, we focus on theoretical investigation about the efficiency of hybrid algorithms for combinatorial optimization problems. We first analyze the runtime of three specific hybrid algorithms and their component algorithms on two instances. One is a well-known pseudo-Boolean function, and the other is an instance of a classical combinatorial optimization problem. We then theoretically investigate the relationship between the upper bounds of the expected runtime of three kinds of general hybrid algorithms and their component algorithms. [ABSTRACT FROM AUTHOR]

The knapsack problem (KP) is a discrete combinatorial optimization problem that has different utilities in many fields. It is described as a non-polynomial time (NP) problem and has several applications in many fields. The differential evolution (DE) algorithm has been successful in solving continuous optimization problems, but it needs further work to solve discrete and binary optimization problems and avoid local optima. According to the literature, no DE search operator or algorithm is optimal for all optimization tasks. As a result, using more than one search operator in a single algorithm architecture, called multi-operator-based algorithms, is a solution to address this problem. These methods outperformed single-based methods for continuous optimization problems. Thus, in this paper, a binary multi-operator differential evolution (BMODE) approach is presented to tackle the 0–1 KP. The presented methodology utilizes multiple differential evolution (DE) mutation strategies with complementary characteristics, with the best mutation operator being asserted utilizing the produced solutions' quality and the population's diversity. In BMODE, two types of transfer functions (TFs) (S-shaped and V-shaped) are used to transfer the continuous solutions to binary ones to be able to calculate the fitness function value. To handle the capacity constraints, a feasibility rule is utilized and some of the infeasible solutions are repaired. The performance of BMODE is tested by solving 40 instances with multiple dimensions, i.e., low, medium, and high. Experimental results of the proposed BMODE are compared with well-known state-of-the-art 0–1 knapsack algorithms. Based on Wilcoxon's nonparametric statistical test ( α = 0.05 ), the proposed BMODE can obtain the best results against the rival algorithms in most cases, and can work well on stability and computational accuracy. [ABSTRACT FROM AUTHOR]

The discounted {0-1} knapsack problem (DKP) is an NP-hard problem that is more challenging than the classical knapsack problem. In this paper, an enhanced version of the sine-cosine algorithm (SCA) called TMHSCA is proposed to solve the DKP. The SCA is a novel metaheuristic algorithm based on sine-cosine theory. Three effective improvements are proposed for the SCA to enhance the convergence speed and exploitation capability of the algorithm. First, by dividing the initial population into three subpopulations using random, greedy and opposition-based learning (OBL) strategies, the diversity of the population can be effectively enhanced. Furthermore, a forward-inverse sine-cosine search that expands the search space by utilizing the worst solution as another target is proposed. The proposed forward-inverse sine-cosine search strategy facilitates the algorithm to explore the easily ignored solution space. The last improvement includes the use of an OBL mutation and the mutation operator of differential evolution at a two-stage mutation, which increases the algorithm's convergence speed and fitness. In our proposed two-stage mutation, the number of mutations can be adaptively adjusted based on the optimization capabilities of the optimal individual. Additionally, a reshuffling repair strategy for repairing infeasible solutions by sorting items into groups to obtain the weight-to-value ratio is proposed. Extensive experiments are conducted on 40 publicly available datasets and are compared to the greedy algorithm, 3 SCAs and 8 competitive baseline methods. The experimental results demonstrate that our method achieves a state-of-the-art performance. [ABSTRACT FROM AUTHOR]

The two-dimension strip packing problem (2DSPP) is an NP-hard combinatorial optimization problem, and it has a wide range of applications. The order in which the rectangles are placed in the strip is the key to solving the 2DSPP. In this paper, the corner increment multi-level scoring strategy and the two-step selection strategy are proposed to make the selection of rectangles more reasonable. The hierarchical construction strategy is used to improve the constructive heuristic algorithm to expand the search space of the rectangle selection. Based on this, this paper proposes a multi-strategy rectangle selection algorithm TSMSA for solving 2DSPP. Comparing experiments with 7 excellent algorithms for solving 2DSPP on 737 instances of the benchmark dataset shows that the instance number of the optimal solution obtained by TSMSA is 1.05~2.9 times that of the other 7 algorithms. [ABSTRACT FROM AUTHOR]

The maximum internal spanning tree (MIST) problem is to find a spanning tree with maximum number of internal node for an undirected graph. It is a variation of the well-known minimum spanning tree problem and is NP-hard. Evolutionary algorithms (EAs) have been successfully applied to solve many NP-hard combinatorial optimization problems in numerical empirical studies. However, researchers know little about their performance guarantees from theory aspect. This paper designs a valid fitness function to guide the well-studied evolutionary algorithm, (1 + 1) EA , to optimize the MIST problem, and presents theoretical analysis to show that it can obtain a performance guarantee of 2 and 5/3 in expected runtime O (n m 2) and O (n m 4) , respectively. Moreover, this paper proves that the (1+1) EA can achieve a performance guarantee of 3 for a variation of the MIST problem, where each vertex is associated with a weight. In addition, comparison analyses on two family instance graphs are presented to show that (1 + 1) EA is better than two local search algorithms. This theoretical study provides insight into the process of (1 + 1) EA constructing a performance guarantee solution for the MIST problem. [ABSTRACT FROM AUTHOR]

This paper studies a shuffled linear regression problem. As a variant of ordinary linear regression, it requires estimating not only the regression variable, but also permutational correspondences between the covariates and responses. While existing formulations require the underlying ground-truth correspondences to be an ideal bijection such that all pieces of data should match, such a requirement barely holds in real-world applications due to either missing data or outliers. In this work, we generalize the formulation of shuffled linear regression to a broader range of conditions where only a part of the data should correspond. To this end, the effective recovery condition and NP-hardness of the proposed formulation are also studied. Moreover, we present a simple yet effective algorithm for deriving the solution. Its global convergence property and convergence rate are also analyzed in detail. Distinct tasks validate the effectiveness of our proposed formulation and the solution method. [ABSTRACT FROM AUTHOR]

The rapid growing number of web services has posed new challenges for service composition computing. How to combine services that meet the needs of users in the least amount of time from a huge number of candidate services is a hot topic of research today. As a meta-heuristic algorithm for solving optimization problems, salp swarm algorithm (SSA) has been widely applied to case scenarios in different fields due to its simple structure and high performance. However, QoS-aware service composition is a discrete problem and existing methods are not suitable for it. Therefore, in this paper, we propose an improved SSA integrating chaotic mapping method for QoS service composition selection, named CSSA. Through the randomness and ergodicity of chaos, reducing the possibility of falling into local optimum and strengthening the exploitation capability of the algorithm. In addition, a fuzzy continuous neighborhood search method is used to enhance the local search capability of the algorithm which makes the discrete space of service composition in a way similar to continuous space. Finally, two well-known datasets are used to verify the effectiveness of CSSA compared to three advanced algorithms and original SSA. The test results demonstrate that CSSA has significant advantages and it also has satisfactory performance in large scale scenarios. [ABSTRACT FROM AUTHOR]

Randomized search heuristics such as evolutionary algorithms are frequently applied to dynamic combinatorial optimization problems. Within this paper, we present a dynamic model of the classic weighted vertex cover problem and analyze the runtime performances of the well-studied algorithms randomized local search and (1 + 1) EA adapted to it, to contribute to the theoretical understanding of evolutionary computing for problems with dynamic changes. In our investigations, we use an edge-based representation based on the dual form of the Linear Programming formulation for the problem and study the expected runtime that the adapted algorithms require to maintain a 2-approximate solution when the given weighted graph is modified by an edge-editing or weight-editing operation. Considering the weights on the vertices may be exponentially large with respect to the size of the graph, the step size adaption strategy is incorporated, with or without the 1/5-th rule that is employed to control the increasing/decreasing rate of the step size. Our results show that three of the four algorithms presented in the paper can recompute 2-approximate solutions for the studied dynamic changes in polynomial expected runtime, but the (1 + 1) EA with 1/5-th rule requires pseudo-polynomial expected runtime. [ABSTRACT FROM AUTHOR]

The Weapon-Target Assignment (WTA) problem aims to assign a set of weapons to a number of assets (targets), such that the expected value of survived targets is minimized. The WTA problem is a nonlinear combinatorial optimization problem known to be NP-hard. This paper applies several existing techniques to linearize the WTA problem. One linearization technique (Camm et al. in Oper Res 50(6):946–955, 2002) approximates the nonlinear terms of the WTA problem via convex piecewise linear functions and provides heuristic solutions to the WTA problem. Such approximation problems are, though, relatively easy to solve from the computational point of view even for large-scale problem instances. Another approach proposed by O'Hanley et al. (Eur J Oper Res 230(1):63–75, 2013) linearizes the WTA problem exactly at the expense of incorporating a significant number of additional variables and constraints, which makes many large-scale problem instances intractable. Motivated by the results of computational experiments with these existing solution approaches, a specialized new exact solution approach is developed, which is called branch-and-adjust. The proposed solution approach involves the compact piecewise linear convex under-approximation of the WTA objective function and solves the WTA problem exactly. The algorithm builds on top of any existing branch-and-cut or branch-and-bound algorithm and can be implemented using the tools provided by state-of-the-art mixed integer linear programming solvers. Numerical experiments demonstrate that the proposed specialized algorithm is capable of handling very large scale problem instances with up to 1500 weapons and 1000 targets, obtaining solutions with optimality gaps of up to 2.0 % within 2 h of computational runtime. [ABSTRACT FROM AUTHOR]

The unprecedented growth of energy consumption in data centers created critical concern in recent years for both the research community and industry. Besides its direct associated cost; high energy consumption also results in a large amount of CO2 emission and incurs extra cooling expenditure. The foremost reason for overly energy consumption is the underutilization of data center resources. In modern data centers, virtualization provides a promising approach to improve the hardware utilization level. Virtual machine placement is a process of mapping a group of virtual machines (VMs) onto a set of physical machines (PMs) in a data center with the aim of maximizing resource utilization and minimizing the total power consumption by PMs. An optimal virtual machine placement algorithm substantially contributes to cutting down the power consumption through assigning the input VMs to a minimum number of PMs and allowing the dispensable PMs to be turned off. However, VM Placement Problem is a complex combinatorial optimization problem and known to be NP-Hard problem. This paper presents an extensive review of virtual machine placement problem along with an overview of different approaches for solving virtual machine placement problem. The aim of this paper is to illuminate challenges and issues for current virtual machine placement techniques. Furthermore, we present a taxonomy of virtual machine placement based on various aspects such as methodology, number of objectives, operation mode, problem objectives, resource demand type and number of clouds. The state-of-the-art VM Placement techniques are classified in single objectives and multi-objective groups and a number of prominent works are reviewed in each group. Eventually, some open issues and future trends are discussed which serve as a platform for future research work in this domain. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem (QAP) is one of the hardest combinatorial optimization tasks. It has many real-world applications such as airport gate assignment, and hospital layout problem. Designing enhanced optimization methodologies for the QAP is an active research area. In this paper, we present an integrated firefly algorithm (FA) based on mutually orthogonal Latin squares (MOLS), named as FA-MOLS, to solve the QAP. In the optimization process, the FA-MOLS employs three improvements, namely the MOLS strategy, opposition-based learning scheme, and repeated 2-exchange mutation to maintain the balance between exploitation and exploration abilities. By these improvements, it is intended to avoid the trapping in local optima and improve the convergence speed. The performance of the proposed FA-MOLS is validated on different test instances from the literature. Additionally, two real-world QAPs are simulated and investigated, the office buildings of a single company and the layout of hospital departments. The comprehensive experimental simulations and the nonparametric Wilcoxon's test affirm that the proposed FA-MOLS can provide a highly competitive performance compared with other algorithms from the literature. Therefore, it is concluded that FA-MOLS is an efficient and reliable algorithm for solving industrial quadratic assignment tasks. [ABSTRACT FROM AUTHOR]

Grey Wolf Optimizer (GWO) is a nature-inspired swarm intelligence algorithm that mimics the hunting behavior of grey wolves. GWO, in its basic form, is a real coded algorithm that needs modifications to deal with binary optimization problems. In this paper, previous work on the binarization of GWO are reviewed, and are classified with respect to their encoding scheme, updating strategy, and transfer function. Then, we propose a novel binary GWO algorithm (named SetGWO), which is based on set encoding and uses set operations in its updating strategy. The proposed algorithm uses a completely different encoding scheme that eliminates the need for the transfer function and boundary checking, and also uses lower-dimensional agents; therefore, decreases the running time. Also, by using an exclusive exploration set for each agent, defining a different distance measure and an encircling strategy in discrete spaces, the quality of solutions has been improved. Experimental results on different real-world combinatorial optimization problems and datasets show that SetGWO outperforms other existing binary GWO algorithms in terms of quality of solutions, running time, and scalability. [ABSTRACT FROM AUTHOR]

We study the generalized minimum Manhattan network (GMMN) problem: given a set P of pairs of points in the Euclidean plane R 2 , we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the L 1 metric (a so-called Manhattan path) for each pair in P . This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in P , and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach. [ABSTRACT FROM AUTHOR]

The knapsack problem arises in several real-world applications, like manufacturing systems, transportation, cutting and packing, and hydrological studies. In this paper, we investigate the use of an iterative rounding strategy-based algorithm for tackling a special knapsack problem: the set-union knapsack problem. First, the approach builds a series of starting partial solutions by using the principle of fractional values related to a series of linear relaxations of the (sub)instance at hand. Second, each step of the rounding procedure is coupled with an enhanced local search procedure, where its goal is to search around a local partial solution by applying the so-called critical element tailored for the problem studied. Third, both degrading and re-optimization strategies are introduced in order to extend the diversified search space. Finally, all strategies are embedded into an iterative search in order to augmenting the quality of the solutions. The performance of the proposed method is evaluated on benchmark instances of the literature and new large-scale instances; its provided results are compared to those reached by the Cplex solver and the best methods available in the literature. The method seems competitive, where it is able to achieve new (lower) bounds and matches the rest of the bounds. [ABSTRACT FROM AUTHOR]

In this paper we present a scaling algorithm for minimizing arbitrary functions over vertices of polytopes in an oracle model of computation which includes an augmentation oracle. For the binary case, when the vertices are 0–1 vectors, we show that the oracle time is polynomial. Also, this algorithm allows us to generalize some concepts of combinatorial optimization concerning performance bounds of greedy algorithms and leads to new bounds for the complexity of the simplex method. [ABSTRACT FROM AUTHOR]

We propose a dead-end control algorithm for the exact solution of NP-hard combinatorial optimization problems. The efficiency of the algorithm is demonstrated by examples of solving the set-partition and 0-1 knapsack problems. The paper also shows that the use of the idea of dead-end controls when implementing the dynamic programming method can considerably reduce the number of problem state variables at each optimization step. A comparative analysis of the proposed method with known algorithms for solving these problems is carried out. [ABSTRACT FROM AUTHOR]

Nowadays, large part of the technical knowledge associated with collapses of slabs is based on past failures of bridges, floors, flat roofs and balconies. Collapse mechanisms tend to often differ from each other due to unique features which make it difficult to derive a generalised technique that can predict the right mechanism. This paper proposes a novel algorithm for tackling the problem of detection of collapse mechanisms, which is part of a pseudo-lower bound method for assessing concrete slabs in bridges and buildings. The problem is generalised to a combinatorial one, and the solution is based on a set of well-known combinatorial optimization algorithms. The proposed approach enables an identification of the domain of existence of yield-lines potentially leading to collapse. The output provides an estimation of a hampered domain of feasible yield-lines through which engineers can quickly identify zones of the slab and directions in which yield-lines leading to collapse are more likely to occur. Numerical applications of the algorithm are presented herein. [ABSTRACT FROM AUTHOR]

The partner selection problem (PSP) is a key issue in constituting and reconfiguring strategic alliances. In this paper, we seek to address PSP under time, budget, activity precedence, and resource constraints. Multiple objectives are considered, our proposed approach simultaneously minimizing total cost and project duration while maximizing average quality. For these purposes, we present a novel multi-objective symbiotic organisms search for scheduling (MOSOSS). In this new algorithm, evolutionary operators are completely redesigned for combinatorial optimization. Furthermore, they are specifically adapted for scheduling problems. One notable original aspect of the new MOSOSS algorithm is that it evolves partial (incompletely scheduled) solutions. For this purpose, we propose evolutionary operators specially constructed to deal with both incomplete and complete schedules. Experimental results on randomly generated PSP instances show that MOSOSS offers a better coverage of the Pareto front as compared to the extant multiple objective symbiotic organisms search and NSGA-II. [ABSTRACT FROM AUTHOR]

Optimization of reactive power dispatch (ORPD) problem is a key factor for stable and secure operation of the electric power systems. In this paper, a newly explored nature-inspired optimization through artificial ecosystem optimization (AEO) algorithm is proposed to cope with ORPD problem in large-scale and practical power systems. ORPD is a well-known highly complex combinatorial optimization task with nonlinear characteristics, and its complexity increases as a number of decision variables increase, which makes it hard to be solved using conventional optimization techniques. However, it can be efficiently resolved by using nature-inspired optimization algorithms. AEO algorithm is a recently invented optimizer inspired by the energy flocking behavior in a natural ecosystem including non-living elements such as sunlight, water, and air. The main merit of this optimizer is its high flexibility that leads to achieve accurate balance between exploration and exploitation abilities. Another attractive property of AEO is that it does not have specific control parameters to be adjusted. In this work, three-objective version of ORPD problem is considered involving active power losses minimization and voltage deviation and voltage stability index. The proposed optimizer was examined on medium- and large-scale IEEE test systems, including 30 bus, 118 bus, 300 bus and Algerian electricity grid DZA 114 bus (220/60 kV). The results of AEO algorithm are compared with well-known existing optimization techniques. Also, the results of comparison show that the proposed algorithm performs better than other algorithms for all examined power systems. Consequently, we confirm the effectiveness of the introducing AEO algorithm to relieve the over losses problem, enhance power system performance, and meet solutions feasibility. One-way analysis of variance (ANOVA) has been employed to evaluate the performance and consistency of the proposed AEO algorithm in solving ORPD problem. [ABSTRACT FROM AUTHOR]

The maximum weighted stable set problem in claw-free graphs is a well-known generalization of the maximum weighted matching problem, and a classical problem in combinatorial optimization. In spite of the recent development of fast(er) combinatorial algorithms and some progresses in the characterization of the corresponding stable set polytope, the problem of "providing a decent linear description" for this polytope (Grötschel et al. in Geometric algorithms and combinatorial optimization, Springer, New York, 1988) is still open. The main contribution of this paper is to propose an algorithmic answer to that question by providing a polynomial-time and computationally attractive separation routine for the stable set polytope of claw-free graphs, that only requires a combinatorial decomposition algorithm, the solution of (moderate sized) compact linear programs, and Padberg and Rao's algorithm for separating over the matching polytope. In particular, it is a generalization of the latter and avoids the heavy computational burden of resorting to the ellipsoid method, on which the only poly-time separation routine known so far relied. Besides, our separation routine comes with a 'small' (but not polynomial) extended linear programming formulation and a procedure to derive a linear description of the stable set polytope of claw-free graphs in the original space. [ABSTRACT FROM AUTHOR]

Given a complete edge-weighted undirected graph G(V, E, W), clique partitioning problem (CPP) aims to cluster all vertices into an unknown number of disjoint groups and the objective is to maximize the sum of the edge weights of the induced subgraphs. CPP is an NP-hard combinatorial optimization problem with many real-world applications. In this paper, we propose a novel two-model local search algorithm with a self-adaptive parameter (TMLS _ SA) to solve CPP. First, a simple solution is presented, that is, one vertex per group is used. Then, we present a two-model local search that is used to improve the solution which comprises a move operator model and an exchange operator model. In the local search phase, a gain function is used to guide the search toward a possible best solution, and a lock mechanism is also applied to prevent the local search from immediately returning to visited solutions. Finally, we execute a perturbation procedure to increase the diversity. The perturbation strength is updated self-adaptively according to the solutions obtained. Our algorithm TMLS _ SA is compared with several representative algorithms, and the experimental results show that TMLS _ SA is superior to competitors on almost all test instances with respect to the solution quality. [ABSTRACT FROM AUTHOR]

In this paper, we propose to study a wide class of combinatorial optimization problems called combinatorial optimization problems with labelling. First, we give a combinatorial method to deal with the labelling version of some classical combinatorial optimization problems including minimum vertex cover, maximum independent set, minimum dominating set and minimum set cover, and convert the labelling problems into the original problems by polynomial-time reduction. We show that, although the labelling version of these problem seems more universal than their original counterparts, they are actually equivalent to the corresponding original problem from an algorithmic point of view. Moreover, we generalize the greedy approach for solving submodular cover problem to its labelling version, and as simple applications of our new method, we use it to solve the labelling versions of the minimum weighted spanning tree and connected vertex cover problem in a unified way. [ABSTRACT FROM AUTHOR]

The paper considers a mathematical model of the land use problem on hypergraphs. It is shown that, within the framework of this model, the problem can be formulated as an optimization problem on a fragmented structure. Moreover, the problem of finding the optimal solution itself reduces to the problem of unconditional combinatorial optimization on a set of permutations. A variant of a hybrid algorithm for finding approximate solutions to the problem based on a combination of a fragmented algorithm and an ant colony algorithm is proposed. [ABSTRACT FROM AUTHOR]

Bi-level programming problems are a special class of optimization problems with two levels of optimization tasks. These problems have been widely studied in the literature and often appear in many practical problem solving tasks. Although many applications fit the bi-level framework, however, real-life implementations are scarce, due mainly to the lack of efficient algorithms able to handle effectively this NP-hard problem. Several solution approaches have been proposed to solve these problems; however, most of them are restricted to the continuous case. Motivated by this observation, we have recently proposed a Co-evolutionary Decomposition-based Algorithm (CODBA) to solve bi-level combinatorial problems. CODBA scheme has been able to bring down the computational expense significantly as compared to other competitive approaches within this research area. In this paper, we further improve CODBA approach by incorporating a local search procedure to make the search process more efficient. The proposed extension called CODBA-LS includes a variable neighborhood search to the lower-level task to help in faster convergence of the algorithm. Further experimental tests based on the bi-level production–distribution problems in supply chain management model on a set of artificial and real-life data turned out to be effective on both computation time and solution quality. [ABSTRACT FROM AUTHOR]

A user-centric memetic algorithm (UcMA) represents an instance of the so-called interactive evolutionary computation, in which the subjacent algorithm that interacts with a human consists of a memetic algorithm (MA) that manages knowledge of the problem with the aim of accelerating the solution search process. UcMAs have been proved to be effective optimization methods to tackle problems that require human intervention (in the form of evaluations/decisions). This paper proposes two generic schemas to distribute a number of (interactive/proactive) UcMAs that act as independent agents and, eventually, synchronize to interchange information. These schemas can be instantiated via a number of parameters (including the cooperation topology) to develop novel 2-dimensional spatially structured cooperative UcMAs. These algorithms can be viewed as specific instances of the so-called parallel MAs but with the particularity that they are especially suited to dealing with combinatorial problems whose solving requires subjective evaluations. An experimental study over microarray ordering problems is done including distinct instances of an NP-hard problem with strong implications in biomedicine and molecular biology, namely the gene ordering problem. It is shown that some distributed UcMAs, especially those based on proactivity, which have been instantiated from our proposals, efficiently handle these problems. [ABSTRACT FROM AUTHOR]

The sport teams grouping problem (STGP) concerns the assignment of sport teams to round-robin tournaments. The objective is to minimize the total travel distance of the participating teams while simultaneously respecting fairness constraints. The STGP is an NP-Hard combinatorial optimization problem highly relevant in practice. This paper investigates the performance of some complimentary optimization approaches to the STGP. Three integer programming formulations are presented and thoroughly analyzed: two compact formulations and another with an exponential number of variables, for which a branch-and-price algorithm is proposed. Additionally, a meta-heuristic method is applied to quickly generate feasible high-quality solutions for a set of real-world instances. By combining the different approaches' results, solutions within 1.7% of the optimum values were produced for all feasible instances. Additionally, to support further research, the considered STGP instances and corresponding solutions files were shared online. [ABSTRACT FROM AUTHOR]

Inventory routing problem (IRP) is one of the most important logistics problems; in this type of problems, decision maker usually has the option to use several types of vehicles to form a fleet with appropriate size and composition in order to minimize both inventory and transportation costs. Meanwhile, the increasing fuel consumption and its economic and environmental impacts mean that this issue must also be incorporated into the routing problems. This paper proposes a new bi-objective model for green inventory routing problem with the heterogeneous fleet. The objectives of the proposed model are (I) to reduce the emissions and (II) to minimize the fleet size, vehicle type, routing, and inventory costs. Given the NP-hard nature of the assessed problem, a bi-objective meta-heuristic algorithm based on the quantum evolutionary algorithm is proposed to achieve these objectives. To evaluate the performance of the proposed algorithm, its results are compared with the results of the exact method and Non-dominated Sorting Genetic Algorithm II (NSGAII). The results of these comparisons indicate the better performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The paper presents a genetic algorithm for multicriteria optimization of parameters of a technological process, which finds a solution not from a certain point but from a specified population. The objective functions are used without their derivatives and probabilistic choice rules are applied. The multicriteria optimization is based on finding a solution that simultaneously optimizes the machining parameters defined by functions of productivity, tool consumption, tool cost, etc. [ABSTRACT FROM AUTHOR]

This paper concerns with some variants of the inverse obnoxious median location problem on tree networks, where the aim is either to augment or to reduce the edge lengths at the minimum total cost such that a prespecified subset of vertices becomes an obnoxious multi-facility median location with respect to the perturbed edge lengths. For both augmentation and reduction models, under the rectilinear norm and the sum-type Hamming distance, we develop novel combinatorial algorithms with polynomial time complexities. Particularly, if the underlying tree is an extended star graph, then the problems can be solved in linear time. [ABSTRACT FROM AUTHOR]

In this paper, a carton heterogeneous vehicle routing problem with a collection depot is presented, which can collaboratively pick the cartons from several carton factories to a collection depot and then from the depot to serve their corresponding customers by using of heterogeneous fleet. Since the carton heterogeneous vehicle routing problem with a collection depot is a very complex problem, particle swarm optimization (PSO) is used to solve the problem in this paper. To improve the performance of the PSO, a self-adaptive inertia weight and a local search strategy are used. At last, the model and the algorithm are illustrated with two test examples. The results show that the proposed PSO is an effective method to solve the multi-depot vehicle routing problem, and the carton heterogeneous vehicle routing problem with a collection depot. Moreover, the proposed model is feasible with a saving of about 28 % in total delivery cost and could obviously reduce the required number of vehicles when comparing to the actual instance. [ABSTRACT FROM AUTHOR]

In open vehicle routing problem (OVRP), after delivering service to the last customer, the vehicle does not necessarily return to the initial depot. This type of problem originally defined about thirty years ago and still is an open issue. In real life, the OVRP is similar to the delivering newspapers and consignments. The problem of service delivering to a set of customers is a particular open VRP with an identical fleet for transporting vehicles that do not necessarily return to the initial depot. Contractors which are not the employee of the delivery company use their own vehicles and do not return to the depot. Solving the OVRP means to optimize the number of vehicles, the traveling distance and the traveling time of a vehicle. In time, several algorithms such as tabu search, deterministic annealing and neighborhood search were used for solving the OVRP. In this paper, a new combinatorial algorithm named OVRP_GELS based on gravitational emulation local search algorithm for solving the OVRP is proposed. We also used record-to-record algorithm to improve the results of the GELS. Several numerical experiments show a good performance of the proposed method for solving the OVRP when compared with existing techniques. [ABSTRACT FROM AUTHOR]

When a conflict or plan change occurs in the process of cloud service execution, if the initial scheme is not rescheduled in time, it can lead to a delivery delay and a series of nonlinear losses. The cloud service rescheduling (CSRS) problem is considered as a particularly hard combinatorial optimization problem with multi-participants, which is significantly different from traditional flow shop rescheduling problem. It is difficult to coordinate the relationship of service suppliers and construct a reward mechanism to encourage them to participate in the rescheduling. According to the various strategies of service suppliers that do or do not participate in the rescheduling, a game theory model was constructed. The main aim of this paper is to explore how to minimize the reward of suppliers and ensure that the game model develops in a desired direction. Hence, a novel hybrid approach using shuffled frog leading algorithm (SFLA) and Nash equilibrium (NE) theory was proposed to solve the CSRS problem. In addition, we carried out a case study to demonstrate that the SFLA and NE approaches can be implemented for realistically sized problem sets and that the cost savings are significant [ABSTRACT FROM AUTHOR]

This paper investigates collaborative optimization (CO) for multidisciplinary design optimization problems with multi-objective subsystems. A multi-stage optimization strategy is presented in the system level to enhance the performance of CO that may be weakened by the initial point in some cases. Resolving the multi-objective problem in subsystems with the preference-based algorithm requires setting the preference values for all the objective functions. Therefore, we transform the incompatibility function into a disciplinary constraint aiming to avoid providing the preference value, and propose two transformation methods, namely, closest distance and relaxed distance. At the end of the paper, the results of two engineering examples demonstrate the performance of the multi-stage optimization strategy, and the effectiveness of the transformation for the incompatibility function. [ABSTRACT FROM AUTHOR]

Particle swarm optimization (PSO) is a population based algorithm for solving global optimization problems. Owing to its efficiency and simplicity, PSO has attracted many researchers' attention and developed many variants. Orthogonal learning particle swarm optimization (OLPSO) is proposed as a new variant of PSO that relies on a new learning strategy called orthogonal learning strategy. The OLPSO differs in the utilization of the information of experience from the standard PSO, in which each particle utilizes its historical best experience and globally best experience through linear summation. In OLPSO, particles can fly in better directions by constructing an efficient exemplar through orthogonal experimental design. However, the global version based orthogonal learning PSO (OLPSO-G) still have some drawbacks in solving some complex multimodal function optimization. In this paper, we proposed a quadratic interpolation based OLPSO-G (QIOLPSO-G), in which, a quadratic interpolation based construction strategy for the personal historical best experience is applied. Meanwhile, opposition-based learning, and Gaussian mutation are also introduced into this paper to increase the diversity of the population and discourage the premature convergence. Experiments are conducted on 16 benchmark problems to validate the effectiveness of the QIOLPSO-G, and comparisons are made with four typical PSO algorithms. The results show that the introduction of the three strategies does enhance the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G( V, E) with $$\alpha (G) \le 3$$ in time $$\mathcal{O}(|E|\log |V|)$$ . More precisely, in time $$\mathcal{O}(|E|)$$ we check whether $$\alpha (G) \le 3$$ or produce a stable set with cardinality at least 4; moreover, if $$\alpha (G) \le 3$$ we produce in time $$\mathcal{O}(|E|\log |V|)$$ a maximum weight stable set of G. This improves the bound of $$\mathcal{O}(|E||V|)$$ due to Faenza, Oriolo and Stauffer. [ABSTRACT FROM AUTHOR]

In this paper we address the Swap-Body Vehicle Routing Problem (SB-VRP), a variant of the truck and trailer routing problem. It was introduced in the VeRoLog Challenge 2014. We develop a solution approach that we coin Relax-and-Repair. It consists in solving a relaxed version of the SB-VRP and deriving a feasible solution by repairing the relaxed one. We embed this approach within a population-based heuristic. During computation we store all feasible routes in order to derive better solutions by solving a set-partitioning problem. In order to take advantages of nowadays multi-core machines, our algorithm is designed as a collaborative parallel population-based heuristic. Experimental results show that our relax-and-repair algorithm is very competitive and point the impact of each phase on the quality of the obtained solutions. The advantage of our approach is that it can be adapted to solve complex industrial routing problems. [ABSTRACT FROM AUTHOR]

Finding complete subgraphs in a graph, that is, cliques, is a key problem and has many real-world applications, e.g., finding communities in social networks, clustering gene expression data, modeling ecological niches in food webs, and describing chemicals in a substance. The problem of finding the largest clique in a graph is a well-known difficult combinatorial optimization problem and is called the maximum clique problem. In this paper, we formulate a very convenient continuous characterization of the maximum clique problem based on the symmetric rank-one non-negative approximation of a given matrix and build a one-to-one correspondence between stationary points of our formulation and cliques of a given graph. In particular, we show that the local (resp. global) minima of the continuous problem corresponds to the maximal (resp. maximum) cliques of the given graph. We also propose a new and efficient clique finding algorithm based on our continuous formulation and test it on the DIMACS data sets to show that the new algorithm outperforms other existing algorithms based on the Motzkin-Straus formulation and can compete with a sophisticated combinatorial heuristic. [ABSTRACT FROM AUTHOR]

Designing competitive manufacturing systems with high levels of productivity and quality at a reasonable cost is a complex task. Decision makers must face numerous decision variables which involve multiple and iterative analysis of the estimated cost, quality and productivity of each design alternative. This paper adresses this issue by providing a fast algorithm for solving the buffer sizing and inspection positioning problem of large production lines by combining heuristic and exact algorithms. We develop a multilevel hybrid search method combining a genetic algorithm and tabu search to identify promising locations for the inspection stations and an exact method that optimizes rapidly (in polynomial time) the buffers' sizes for each location. Our method gives valuable insights into the problem, and its solution time is a small fraction of that required by the exact method on production lines with 10-30 machines. [ABSTRACT FROM AUTHOR]

This paper presents an original hybrid approach to solve the Capacitated Vehicle Routing Problem (CVRP). The approach combines a Probabilistic Algorithm with Constraint Programming (CP) and Lagrangian Relaxation (LR). After introducing the CVRP and reviewing the existing literature on the topic, the paper proposes an approach based on a probabilistic Variable Neighbourhood Search (VNS) algorithm. Given a CVRP instance, this algorithm uses a randomized version of the classical Clarke and Wright Savings constructive heuristic to generate a starting solution. This starting solution is then improved through a local search process which combines: (a) LR to optimise each individual route, and (b) CP to quickly verify the feasibility of new proposed solutions. The efficiency of our approach is analysed after testing some well-known CVRP benchmarks. Benefits of our hybrid approach over already existing approaches are also discussed. In particular, the potential flexibility of our methodology is highlighted. [ABSTRACT FROM AUTHOR]

Multi-Objective Combinatorial Optimization (MOCO) problems find a wide range of practical application problems, some of which involving Boolean variables and constraints. This paper develops and evaluates algorithms for solving MOCO problems, defined on Boolean domains, and where the optimality criterion is lexicographic. The proposed algorithms build on existing algorithms for either Maximum Satisfiability (MaxSAT), Pseudo-Boolean Optimization (PBO), or Integer Linear Programming (ILP). Experimental results, obtained on problem instances from haplotyping with pedigrees and software package dependencies, show that the proposed algorithms can provide significant performance gains over state of the art MaxSAT, PBO and ILP algorithms. Finally, the paper also shows that lexicographic optimization conditions are observed in the majority of the problem instances from the MaxSAT evaluations, motivating the development of dedicated algorithms that can exploit lexicographic optimization conditions in general MaxSAT problem instances. [ABSTRACT FROM AUTHOR]

In map generalization various operators are applied to the features of a map in order to maintain and improve the legibility of the map after the scale has been changed. These operators must be applied in the proper sequence and the quality of the results must be continuously evaluated. Cartographic constraints can be used to define the conditions that have to be met in order to make a map legible and compliant to the user needs. The combinatorial optimization approaches shown in this paper use cartographic constraints to control and restrict the selection and application of a variety of different independent generalization operators into an optimal sequence. Different optimization techniques including hill climbing, simulated annealing and genetic deep search are presented and evaluated experimentally by the example of the generalization of buildings in blocks. All algorithms used in this paper have been implemented in a web services framework. This allows the use of distributed and parallel processing in order to speed up the search for optimized generalization operator sequences. [ABSTRACT FROM AUTHOR]

Optimality in the range space is expressed as a tangency condition for an affine set and a cone. In a previous paper, an algorithm was introduced that reaches tangency keeping the two sets nonintersecting. Here,we introduce an exact finite-convergence evolutive algorithm that reaches tangency while keeping the two sets intersecting. In the process of developing the algorithm, we add some completion to the theory (e.g., the description of the contact polytope). Furthermore, we introduce a new formula to express the maximum, which is the primal counterpart of the dual formula introduced in a previous paper. [ABSTRACT FROM AUTHOR]

This paper is devoted to the numerical resolution of unit-commitment problems, with emphasis on the French model optimizing the daily production of electricity. The solution process has two phases. First a Lagrangian relaxation solves the dual to find a lower bound; it also gives a primal relaxed solution. We then propose to use the latter in the second phase, for a heuristic resolution based on a primal proximal algorithm. This second step comes as an alternative to an earlier approach, based on augmented Lagrangian (i.e. a dual proximal algorithm). We illustrate the method with some real-life numerical results. A companion paper is devoted to a theoretical study of the heuristic in the second phase. [ABSTRACT FROM AUTHOR]

Localisation of workpieces with large sculptured surfaces can be difficult. Previously, such pieces were measured by the probe of the machine and adjusted manually. This process is arduous and time-consuming and an even allowance cannot be ensured for every measured point. Searching for the optimal location of surface matching by computer can realise computer aided localisation (CAL) and thus enhance the precision of localisation, saving a lot of time and greatly accelerating machining cycles while reducing machining cost. In this paper, a method is proposed for a localisation problem that consists of rough surface matching and accuracy surface matching. Rough matching determines the variable range of the follow-up algorithms. Accuracy matching acquires the optimal location. Then fast localisation and a clamp can be implemented. A hybrid global optimisation method is adopted to cope with the accuracy matching. It shares the advantages of both genetic algorithms (GAs) and simplex algorithms. The method presented in this paper has been used in the 5-axis machining of both large Kaplan and Francis hydro turbine blades. It shows that the method is easy to realise and the algorithm is steady and robust. [ABSTRACT FROM AUTHOR]