Journal articles: 'Combinatorial optimization Computer algorithms'

1

Korolyov, Vyacheslav, and Oleksandr Khodzinskyi. "Solving Combinatorial Optimization Problems on Quantum Computers." Cybernetics and Computer Technologies, no. 2 (July 24, 2020): 5–13. http://dx.doi.org/10.34229/2707-451x.20.2.1.

Full text

Abstract:

Introduction. Quantum computers provide several times faster solutions to several NP-hard combinatorial optimization problems in comparison with computing clusters. The trend of doubling the number of qubits of quantum computers every year suggests the existence of an analog of Moore's law for quantum computers, which means that soon they will also be able to get a significant acceleration of solving many applied large-scale problems. The purpose of the article is to review methods for creating algorithms of quantum computer mathematics for combinatorial optimization problems and to analyze the influence of the qubit-to-qubit coupling and connections strength on the performance of quantum data processing. Results. The article offers approaches to the classification of algorithms for solving these problems from the perspective of quantum computer mathematics. It is shown that the number and strength of connections between qubits affect the dimensionality of problems solved by algorithms of quantum computer mathematics. It is proposed to consider two approaches to calculating combinatorial optimization problems on quantum computers: universal, using quantum gates, and specialized, based on a parameterization of physical processes. Examples of constructing a half-adder for two qubits of an IBM quantum processor and an example of solving the problem of finding the maximum independent set for the IBM and D-wave quantum computers are given. Conclusions. Today, quantum computers are available online through cloud services for research and commercial use. At present, quantum processors do not have enough qubits to replace semiconductor computers in universal computing. The search for a solution to a combinatorial optimization problem is performed by achieving the minimum energy of the system of coupled qubits, on which the task is mapped, and the data are the initial conditions. Approaches to solving combinatorial optimization problems on quantum computers are considered and the results of solving the problem of finding the maximum independent set on the IBM and D-wave quantum computers are given. Keywords: quantum computer, quantum computer mathematics, qubit, maximal independent set for a graph.

APA, Harvard, Vancouver, ISO, and other styles

2

Calégari, Patrice, Frédéric Guidec, Pierre Kuonen, and Frank Nielsen. "Combinatorial optimization algorithms for radio network planning." Theoretical Computer Science 263, no. 1-2 (July 2001): 235–45. http://dx.doi.org/10.1016/s0304-3975(00)00245-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Iori, Manuel. "Metaheuristic algorithms for combinatorial optimization problems." 4OR 3, no. 2 (June 2005): 163–66. http://dx.doi.org/10.1007/s10288-005-0052-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Ramaswamy, Vasu, and Vadim Shapiro. "Combinatorial Laws for Physically Meaningful Design." Journal of Computing and Information Science in Engineering 4, no. 1 (March 1, 2004): 3–10. http://dx.doi.org/10.1115/1.1645863.

Full text

Abstract:

A typical computer representation of a design includes geometric and physical information organized in a suitable combinatorial data structure. Queries and transformations of these design representations are used to formulate most algorithms in computational design, including analysis, optimization, evolution, generation, and synthesis. Formal properties, and in particular existence and validity of the computed solutions, must be assured and preserved by all such algorithms. Using tools from algebraic topology, we show that a small set of the usual combinatorial operators: boundary (∂), coboundary (δ), and dualization *–are sufficient to represent a variety of physical laws and invariants. Specific examples include geometric integrity, balance and equilibrium, and surface smoothing. Our findings point a way toward systematic development of data structures and algorithms for design in a common formal computational framework.

APA, Harvard, Vancouver, ISO, and other styles

5

Yagiura, Mutsunori, and Toshihide Ibaraki. "On metaheuristic algorithms for combinatorial optimization problems." Systems and Computers in Japan 32, no. 3 (2001): 33–55. http://dx.doi.org/10.1002/1520-684x(200103)32:3<33::aid-scj4>3.0.co;2-p.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Markakis, Vangelis, Ioannis Milis, and Vangelis Th Paschos. "Special Issue: “Combinatorial Optimization: Theory of Algorithms and Complexity”." Theoretical Computer Science 540-541 (June 2014): 1. http://dx.doi.org/10.1016/j.tcs.2014.05.015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Ehrgott, M. "Approximation algorithms for combinatorial multicriteria optimization problems." International Transactions in Operational Research 7, no. 1 (January 2000): 5–31. http://dx.doi.org/10.1111/j.1475-3995.2000.tb00182.x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Mbarek, Fatma, and Volodymyr Mosorov. "Load Balancing Based on Optimization Algorithms: An Overview." Journal of Telecommunications and Information Technology 4, no. 2019 (December 30, 2019): 3–12. http://dx.doi.org/10.26636/jtit.2019.131819.

Full text

Abstract:

Combinatorial optimization challenges are rooted in real-life problems, continuous optimization problems, discrete optimization problems and other signiﬁcant problems in telecommunications which include, for example, routing, design of communication networks and load balancing. Load balancing applies to distributed systems and is used for managing web clusters. It allows to forward the load between web servers, using several scheduling algorithms. The main motivation for the study is the fact that combinatorial optimization problems can be solved by applying optimization algorithms. These algorithms include ant colony optimization (ACO), honey bee (HB) and multi-objective optimization (MOO). ACO and HB algorithms are inspired by the foraging behavior of ants and bees which use the process to locate and gather food. However, these two algorithms have been suggested to handle optimization problems with a single-objective. In this context, ACO and HB have to be adjusted to multiobjective optimization problems. This paper provides a summary of the surveyed optimization algorithms and discusses the adaptations of these three algorithms. This is pursued by a detailed analysis and a comparison of three major scheduling techniques mentioned above, as well as three other, new algorithms (resulting from the combination of the aforementioned techniques) used to eﬃciently handle load balancing issues.

APA, Harvard, Vancouver, ISO, and other styles

9

Kotsireas, I. S., C. Koukouvinos, P. M. Pardalos, and O. V. Shylo. "Periodic complementary binary sequences and Combinatorial Optimization algorithms." Journal of Combinatorial Optimization 20, no. 1 (November 26, 2008): 63–75. http://dx.doi.org/10.1007/s10878-008-9194-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Ahmadian, Ali, Ali Elkamel, and Abdelkader Mazouz. "An Improved Hybrid Particle Swarm Optimization and Tabu Search Algorithm for Expansion Planning of Large Dimension Electric Distribution Network." Energies 12, no. 16 (August 8, 2019): 3052. http://dx.doi.org/10.3390/en12163052.

Full text

Abstract:

Optimal expansion of medium-voltage power networks is a common issue in electrical distribution planning. Minimizing the total cost of the objective function with technical constraints make it a combinatorial problem which should be solved by powerful optimization algorithms. In this paper, a new improved hybrid Tabu search/particle swarm optimization algorithm is proposed to optimize the electric expansion planning. The proposed method is analyzed both mathematically and experimentally and it is applied to three different electric distribution networks as case studies. Numerical results and comparisons are presented and show the efficiency of the proposed algorithm. As a result, the proposed algorithm is more powerful than the other algorithms, especially in larger dimension networks.

APA, Harvard, Vancouver, ISO, and other styles

11

Bac, Fam Quang, and V. L. Perov. "New evolutionary genetic algorithms for NP-complete combinatorial optimization problems." Biological Cybernetics 69, no. 3 (July 1993): 229–34. http://dx.doi.org/10.1007/bf00198963.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Pessoa, Artur Alves, Michael Poss, Ruslan Sadykov, and François Vanderbeck. "Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty." Operations Research 69, no. 3 (May 2021): 739–54. http://dx.doi.org/10.1287/opre.2020.2035.

Full text

Abstract:

Capacitated vehicle routing problems are widely studied combinatorial optimization problems, and branch-and-cut-and-price algorithms can solve instances harder than ever before. These models, however, neglect that demands volumes are often not known with precision when planning the vehicle routes, thus incentivizing decision makers to significantly overestimate the volumes for avoiding coping with infeasible routes. A robust formulation that models demand uncertainty through a knapsack polytope is considered. A new branch-and-cut-and-price algorithm for the problem is provided, which combines efficient algorithms for the problem with no uncertainty with profound results in robust combinatorial optimization and includes novel heuristics and new valid inequalities. The numerical results illustrate that the resulting approach is two orders of magnitude faster that the best algorithm from the literature, solving twice as many instances to optimality.

APA, Harvard, Vancouver, ISO, and other styles

13

Li, Xiu Ying, and Dong Ju Du. "Research on the Application of College Automated Course Scheduling System Based on Genetic Algorithm." Advanced Materials Research 760-762 (September 2013): 1782–85. http://dx.doi.org/10.4028/www.scientific.net/amr.760-762.1782.

Full text

Abstract:

A reasonable curriculum contributes to the improvement of the training and teaching quality of college students. Using computer which is speed and strong ability to arrange curriculum automatically is imperative. Automatically curriculum arrangement is a constrained, multi-objective and intricate combinatorial optimization problem. Based on genetic algorithm of population search, it is suitable to process complex and nonlinear optimization problems which it difficult to solve for traditional search methods. In this paper solves complex automated course scheduling using genetic algorithms.

APA, Harvard, Vancouver, ISO, and other styles

14

King, Charles R., Dan E. Tamir, and Mark McKenney. "Improving Combinatorial Optimization Algorithms through Record Keeping in Constructive Multistart Search." International Journal of Intelligent Systems 29, no. 9 (June 24, 2014): 864–79. http://dx.doi.org/10.1002/int.21667.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Iqbal, Muhammad, Muhammad Zarlis, T. Tulus, and Herman Mawengkang. "Pendekatan Pengembangan Metaheuristik dalam optimisasi kombinatorial." Prosiding Seminar Nasional Riset Information Science (SENARIS) 1 (November 30, 2019): 1193. http://dx.doi.org/10.30645/senaris.v1i0.135.

Full text

Abstract:

Combinatorial problems are problems that have a finite set of feasible solutions. Although in principle the solution to this problem can be obtained with complete enumeration, in complex problems it takes time that cannot be practically accepted, combinatorial analysis is a mathematical study of the arrangement, grouping, ordering, or selection of discrete objects, usually limited in number (finite in number) , many combinatorial optimization problems have been generated by research in computer design, computational theory, and by computer applications on numerical problems that require new methods, new approaches, and new mathematical insights, on combinatorial optimization, the function g (x) is defined as mapping g: {0,1} n → {0,1}, obtaining feasible regions Most methods for solving combinatorial optimization problems propose feasible regions, namely areas that are constrained by problem constraints after relaxation such as counts or binary variables, Field slices generally use the metaheuristic method proposed by para Other researchers, for example Genetic algorithms, simulated annealing, taboo search, plant propagation, methods do not use feasible regional concepts, but proposing the starting point for abstract completion is a brief summary of the paper to help readers quickly ascertain the research objectives and match the research needs.

APA, Harvard, Vancouver, ISO, and other styles

16

Titilayo, Adedeji Oluyinka, Alade Oluwaseun Modupe, Makinde Bukola Oyeladun, and OYELEYE Taye E. "Selected Soft Computing Algorithms for Job Shop Problem (JSP)." International Journal of Science and Engineering Applications 10, no. 9 (September 2021): 125–31. http://dx.doi.org/10.7753/ijsea1009.1003.

Full text

Abstract:

Job Shop Problem (JSP) is an optimization problem in computer science and operations research in which jobs are assigned to resources at particular times. Each operation has a specific machine that it needs to be processed on and only one operation in a job can be processed at a given time. This problem is one of the best known combinatorial optimization problems. The aim of this project is to adapt Bat, Bee, Firefly, and Flower pollination algorithms, implement and evaluate the developed algorithms for solving Job Shop Problem.

APA, Harvard, Vancouver, ISO, and other styles

17

Hazimeh, Hussein, and Rahul Mazumder. "Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms." Operations Research 68, no. 5 (September 2020): 1517–37. http://dx.doi.org/10.1287/opre.2019.1919.

Full text

Abstract:

In several scientific and industrial applications, it is desirable to build compact, interpretable learning models where the output depends on a small number of input features. Recent work has shown that such best-subset selection-type problems can be solved with modern mixed integer optimization solvers. Despite their promise, such solvers often come at a steep computational price when compared with open-source, efficient specialized solvers based on convex optimization and greedy heuristics. In “Fast Best-Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms,” Hussein Hazimeh and Rahul Mazumder push the frontiers of computation for best-subset-type problems. Their algorithms deliver near-optimal solutions for problems with up to a million features—in times comparable with the fast convex solvers. Their work suggests that principled optimization methods play a key role in devising tools central to interpretable machine learning, which can help in gaining a deeper understanding of their statistical properties.

APA, Harvard, Vancouver, ISO, and other styles

18

Santucci, Valentino, Marco Baioletti, and Alfredo Milani. "An algebraic framework for swarm and evolutionary algorithms in combinatorial optimization." Swarm and Evolutionary Computation 55 (June 2020): 100673. http://dx.doi.org/10.1016/j.swevo.2020.100673.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Battiti, Roberto, and Giampietro Tecchiolli. "Parallel biased search for combinatorial optimization: genetic algorithms and TABU." Microprocessors and Microsystems 16, no. 7 (January 1992): 351–67. http://dx.doi.org/10.1016/0141-9331(92)90003-c.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Verma, Jyotsna, and Nishtha Kesswani. "A Review on Bio-Inspired Migration Optimization Techniques." International Journal of Business Data Communications and Networking 11, no. 1 (January 2015): 24–35. http://dx.doi.org/10.4018/ijbdcn.2015010103.

Full text

Abstract:

Nature inspired computing techniques has become a very popular topic in recent years. Number of applications in computer networks, robotics, biology, combinatorial optimization, etc. can be seen in literatures which are based on the bio-inspired techniques. Nature inspired techniques are proven to solve complex optimization problems irrespective of their problem size. This review summarizes various nature inspired migration algorithms and comparison between them, based on the automated tools, evolutionary techniques and applications.

APA, Harvard, Vancouver, ISO, and other styles

21

Waldman, Marvin, Hong Li, and Moises Hassan. "Novel algorithms for the optimization of molecular diversity of combinatorial libraries." Journal of Molecular Graphics and Modelling 18, no. 4-5 (2000): 533–36. http://dx.doi.org/10.1016/s1093-3263(00)80095-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Immorlica, Nicole, Brendan Lucier, Jieming Mao, Vasilis Syrgkanis, and Christos Tzamos. "Combinatorial Assortment Optimization." ACM Transactions on Economics and Computation 9, no. 1 (March 2021): 1–34. http://dx.doi.org/10.1145/3434415.

Full text

Abstract:

Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product is fixed in advance, and a probabilistic choice function describes which product a customer will choose from any given subset. We introduce the combinatorial assortment problem, where each customer may select a bundle of products. We consider a choice model in which each consumer selects a utility-maximizing bundle subject to a private valuation function, and study the complexity of the resulting optimization problem. Our main result is an exact algorithm for additive k -demand valuations, under a model of vertical differentiation in which customers agree on the relative value of each pair of items but differ in their absolute willingness to pay. For valuations that are vertically differentiated but not necessarily additive k -demand, we show how to obtain constant approximations under a “well-priced” condition, where each product’s price is sufficiently high. We further show that even for a single customer with known valuation, any sub-polynomial approximation to the problem requires exponentially many demand queries when the valuation function is XOS and that no FPTAS exists even when the valuation is succinctly representable.

APA, Harvard, Vancouver, ISO, and other styles

23

Yang, Peihao, Linghe Kong, Meikang Qiu, Xue Liu, and Guihai Chen. "Compressed Imaging Reconstruction with Sparse Random Projection." ACM Transactions on Multimedia Computing, Communications, and Applications 17, no. 1 (April 16, 2021): 1–25. http://dx.doi.org/10.1145/3447431.

Full text

Abstract:

As the Internet of Things thrives, monitors and cameras produce tons of image data every day. To efficiently process these images, many compressed imaging frameworks are proposed. A compressed imaging framework comprises two parts, image signal measurement and reconstruction. Although a plethora of measurement devices have been designed, the development of the reconstruction is relatively lagging behind. Nowadays, most of existing reconstruction algorithms in compressed imaging are optimization problem solvers based on specific priors. The computation burdens of these optimization algorithms are enormous and the solutions are usually local optimums. Meanwhile, it is inconvenient to deploy these algorithms on cloud, which hinders the popularization of compressed imaging. In this article, we dive deep into the random projection to build reconstruction algorithms for compressed imaging. We first fully utilize the information in the measurement procedure and propose a combinatorial sparse random projection (SRP) reconstruction algorithm. Then, we generalize the SRP to a novel distributed algorithm called Cloud-SRP (CSRP), which enables efficient reconstruction on cloud. Moreover, we explore the combination of SRP with conventional optimization reconstruction algorithms and propose the Iterative-SRP (ISRP), which converges to a guaranteed fixed point. With minor modifications on the naive optimization algorithms, the ISRP yields better reconstructions. Experiments on real ghost imaging reconstruction reveal that our algorithms are effective. And simulation experiments show their advantages over the classical algorithms.

APA, Harvard, Vancouver, ISO, and other styles

24

Barkoutsos, Panagiotis Kl, Giacomo Nannicini, Anton Robert, Ivano Tavernelli, and Stefan Woerner. "Improving Variational Quantum Optimization using CVaR." Quantum 4 (April 20, 2020): 256. http://dx.doi.org/10.22331/q-2020-04-20-256.

Full text

Abstract:

Hybrid quantum/classical variational algorithms can be implemented on noisy intermediate-scale quantum computers and can be used to find solutions for combinatorial optimization problems. Approaches discussed in the literature minimize the expectation of the problem Hamiltonian for a parameterized trial quantum state. The expectation is estimated as the sample mean of a set of measurement outcomes, while the parameters of the trial state are optimized classically. This procedure is fully justified for quantum mechanical observables such as molecular energies. In the case of classical optimization problems, which yield diagonal Hamiltonians, we argue that aggregating the samples in a different way than the expected value is more natural. In this paper we propose the Conditional Value-at-Risk as an aggregation function. We empirically show -- using classical simulation as well as quantum hardware -- that this leads to faster convergence to better solutions for all combinatorial optimization problems tested in our study. We also provide analytical results to explain the observed difference in performance between different variational algorithms.

APA, Harvard, Vancouver, ISO, and other styles

25

Rongxi Zhou, Xiaoguang Wang, and Guanqun Tong. "A Combinatorial Optimization Model of Interest Rate Term Structure Using Genetic Algorithms." INTERNATIONAL JOURNAL ON Advances in Information Sciences and Service Sciences 5, no. 4 (February 28, 2013): 1001–9. http://dx.doi.org/10.4156/aiss.vol5.issue4.120.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Xiaoning, Fan, Lin Yan, and Ji Zhuoshang. "Ship Pipe Routing Design Using the ACO with Iterative Pheromone Updating." Journal of Ship Production 23, no. 01 (February 1, 2007): 36–45. http://dx.doi.org/10.5957/jsp.2007.23.1.36.

Full text

Abstract:

Ship pipe routing design (SPRD) that belongs to non-deterministic polynomial (NP)-hard problem concerns minimizing the cost of pipe material while satisfying constraints and avoiding obstacles. Currently, this total solution mainly depends on human experts. The stochastic search algorithms suitable for computer technology provide the opportunity to automate and optimize it. The Ant Colony Optimization (ACO) is an effective metaheuristic and stochastic search technique to solve combinatorial optimization problems by using principle of pheromone information. Based on ACO, the method of ant colony algorithm with iterative pheromone updating is first proposed to solve ship pipeline routing in three-dimensional space. Simulation results show that the new updating approach of pheromone is feasible and effective. Mean-while, the performance and computer processing time of the proposed algorithm outperform the original ACO used to generate SPRD solutions.

APA, Harvard, Vancouver, ISO, and other styles

27

Zhang, Heng, Paat Rusmevichientong, and Huseyin Topaloglu. "Assortment Optimization Under the Paired Combinatorial Logit Model." Operations Research 68, no. 3 (May 2020): 741–61. http://dx.doi.org/10.1287/opre.2019.1930.

Full text

Abstract:

When retailers decide which assortment of products to offer, they can make use of a choice model that describes how customers choose and substitute among the products. The key is to use a choice model that faithfully captures the choice process of customers, while making sure that the corresponding problem of finding the revenue-maximizing assortment remains tractable. In “Assortment Optimization Under the Paired Combinatorial Logit Model,” Zhang, Rusmevichientong, and Topaloglu consider the paired combinatorial logit model to capture the choice process of customers. This choice model uses a utility maximization framework to capture the customer choices, and the utilities of the products can have a rather general correlation structure. The authors demonstrate that one can construct algorithms with performance guarantees to solve the assortment optimization problem under this choice model.

APA, Harvard, Vancouver, ISO, and other styles

28

Cacchiani, Valentina. "Models and algorithms for combinatorial optimization problems arising in railway applications." 4OR 7, no. 1 (May 27, 2008): 109–12. http://dx.doi.org/10.1007/s10288-008-0075-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

ZHANG, GEXIANG, HAINA RONG, FERRANTE NERI, and MARIO J. PÉREZ-JIMÉNEZ. "AN OPTIMIZATION SPIKING NEURAL P SYSTEM FOR APPROXIMATELY SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS." International Journal of Neural Systems 24, no. 05 (May 30, 2014): 1440006. http://dx.doi.org/10.1142/s0129065714400061.

Full text

Abstract:

Membrane systems (also called P systems) refer to the computing models abstracted from the structure and the functioning of the living cell as well as from the cooperation of cells in tissues, organs, and other populations of cells. Spiking neural P systems (SNPS) are a class of distributed and parallel computing models that incorporate the idea of spiking neurons into P systems. To attain the solution of optimization problems, P systems are used to properly organize evolutionary operators of heuristic approaches, which are named as membrane-inspired evolutionary algorithms (MIEAs). This paper proposes a novel way to design a P system for directly obtaining the approximate solutions of combinatorial optimization problems without the aid of evolutionary operators like in the case of MIEAs. To this aim, an extended spiking neural P system (ESNPS) has been proposed by introducing the probabilistic selection of evolution rules and multi-neurons output and a family of ESNPS, called optimization spiking neural P system (OSNPS), are further designed through introducing a guider to adaptively adjust rule probabilities to approximately solve combinatorial optimization problems. Extensive experiments on knapsack problems have been reported to experimentally prove the viability and effectiveness of the proposed neural system.

APA, Harvard, Vancouver, ISO, and other styles

30

Lin, Geng, and Jian Guan. "An Integrated Method Based on PSO and EDA for the Max-Cut Problem." Computational Intelligence and Neuroscience 2016 (2016): 1–13. http://dx.doi.org/10.1155/2016/3420671.

Full text

Abstract:

The max-cut problem is NP-hard combinatorial optimization problem with many real world applications. In this paper, we propose an integrated method based on particle swarm optimization and estimation of distribution algorithm (PSO-EDA) for solving the max-cut problem. The integrated algorithm overcomes the shortcomings of particle swarm optimization and estimation of distribution algorithm. To enhance the performance of the PSO-EDA, a fast local search procedure is applied. In addition, a path relinking procedure is developed to intensify the search. To evaluate the performance of PSO-EDA, extensive experiments were carried out on two sets of benchmark instances with 800 to 20000 vertices from the literature. Computational results and comparisons show that PSO-EDA significantly outperforms the existing PSO-based and EDA-based algorithms for the max-cut problem. Compared with other best performing algorithms, PSO-EDA is able to find very competitive results in terms of solution quality.

APA, Harvard, Vancouver, ISO, and other styles

31

Zhang, Weiwei, Jingjing Lin, Honglei Jing, and Qiuwen Zhang. "A Novel Hybrid Clonal Selection Algorithm with Combinatorial Recombination and Modified Hypermutation Operators for Global Optimization." Computational Intelligence and Neuroscience 2016 (2016): 1–14. http://dx.doi.org/10.1155/2016/6204728.

Full text

Abstract:

Artificial immune system is one of the most recently introduced intelligence methods which was inspired by biological immune system. Most immune system inspired algorithms are based on the clonal selection principle, known as clonal selection algorithms (CSAs). When coping with complex optimization problems with the characteristics of multimodality, high dimension, rotation, and composition, the traditional CSAs often suffer from the premature convergence and unsatisfied accuracy. To address these concerning issues, a recombination operator inspired by the biological combinatorial recombination is proposed at first. The recombination operator could generate the promising candidate solution to enhance search ability of the CSA by fusing the information from random chosen parents. Furthermore, a modified hypermutation operator is introduced to construct more promising and efficient candidate solutions. A set of 16 common used benchmark functions are adopted to test the effectiveness and efficiency of the recombination and hypermutation operators. The comparisons with classic CSA, CSA with recombination operator (RCSA), and CSA with recombination and modified hypermutation operator (RHCSA) demonstrate that the proposed algorithm significantly improves the performance of classic CSA. Moreover, comparison with the state-of-the-art algorithms shows that the proposed algorithm is quite competitive.

APA, Harvard, Vancouver, ISO, and other styles

32

Ravikumar, C. P., and H. Rasheed. "TOPS: A Target-Oriented Partial Scan Design Package Based on Simulated Annealing." VLSI Design 2, no. 3 (January 1, 1994): 233–39. http://dx.doi.org/10.1155/1994/32902.

Full text

Abstract:

In this paper, we describe algorithms based on Simulated Annealing for selecting a subset of flip-flops to be connected into a scan path. The objective for selection is to maximize the coverage of faults that are aborted by a sequential fault simulator. We pose the problem as a combinatorial optimization, and present a heuristic algorithm based on Simulated Annealing. The SCOAP testability measure is employed to assess the selection of flip-flops during the course of optimization. Our algorithms form a part of an integrated design package, TOPS, which has been designed as an enhancement to the OASIS standard-cell design automation system available from MCNC. We discuss the TOPS package and its performance on a number of ISCAS'89 benchmarks. We also present a comparative evaluation of the benchmark results.

APA, Harvard, Vancouver, ISO, and other styles

33

Dash, Sujata, Ruppa Thulasiram, and Parimala Thulasiraman. "Modified Firefly Algorithm With Chaos Theory for Feature Selection." International Journal of Swarm Intelligence Research 10, no. 2 (April 2019): 1–20. http://dx.doi.org/10.4018/ijsir.2019040101.

Full text

Abstract:

Conventional algorithms such as gradient-based optimization methods usually struggle to deal with high-dimensional non-linear problems and often land up with local minima. Recently developed nature-inspired optimization algorithms are the best approaches for finding global solutions for combinatorial optimization problems like microarray datasets. In this article, a novel hybrid swarm intelligence-based meta-search algorithm is proposed by combining a heuristic method called conditional mutual information maximization with chaos-based firefly algorithm. The combined algorithm is computed in an iterative manner to boost the sharing of information between fireflies, enhancing the search efficiency of chaos-based firefly algorithm and reduces the computational complexities of feature selection. The meta-search model is implemented using a well-established classifier, such as support vector machine as the modeler in a wrapper approach. The chaos-based firefly algorithm increases the global search mobility of fireflies. The efficiency of the model is studied over high-dimensional disease datasets and compared with standard firefly algorithm, particle swarm optimization, and genetic algorithm in the same experimental environment to establish its superiority of feature selection over selected counterparts.

APA, Harvard, Vancouver, ISO, and other styles

34

Masadeh, Raja, Nesreen Alsharman, Ahmad Sharieh, Basel A. Mahafzah, and Arafat Abdulrahman. "Task scheduling on cloud computing based on sea lion optimization algorithm." International Journal of Web Information Systems 17, no. 2 (March 26, 2021): 99–116. http://dx.doi.org/10.1108/ijwis-11-2020-0071.

Full text

Abstract:

Purpose Sea Lion Optimization (SLnO) algorithm involves the ability of exploration and exploitation phases, and it is able to solve combinatorial optimization problems. For these reasons, it is considered a global optimizer. The scheduling operation is completed by imitating the hunting behavior of sea lions. Design/methodology/approach Cloud computing (CC) is a type of distributed computing, contributory in a massive number of available resources and demands, and its goal is sharing the resources as services over the internet. Because of the optimal using of these services is everlasting challenge, the issue of task scheduling in CC is significant. In this paper, a task scheduling technique for CC based on SLnO and multiple-objective model are proposed. It enables decreasing in overall completion time, cost and power consumption; and maximizes the resources utilization. The simulation results on the tested data illustrated that the SLnO scheduler performed better performance than other state-of-the-art schedulers in terms of makespan, cost, energy consumption, resources utilization and degree of imbalance. Findings The performance of the SLnO, Vocalization of Whale Optimization Algorithm (VWOA), Whale Optimization Algorithm (WOA), Grey Wolf Optimization (GWO) and Round Robin (RR) algorithms for 100, 200, 300, 400 and 500 independent cloud tasks on 8, 16 and 32 VMs was evaluated. The results show that SLnO algorithm has better performance than VWOA, WOA, GWO and RR in terms of makespan and imbalance degree. In addition, SLnO exhausts less power than VWOA, WOA, GWO and RR. More precisely, SLnO conserves 5.6, 21.96, 22.7 and 73.98% energy compared to VWOA, WOA, GWO and RR mechanisms, respectively. On the other hand, SLnO algorithm shows better performance than the VWOA and other algorithms. The SLnO algorithm's overall execution cost of scheduling the cloud tasks is minimized by 20.62, 39.9, 42.44 and 46.9% compared with VWOA, WOA, GWO and RR algorithms, respectively. Finally, the SLnO algorithm's average resource utilization is increased by 6, 10, 11.8 and 31.8% compared with those of VWOA, WOA, GWO and RR mechanisms, respectively. Originality/value To the best of the authors’ knowledge, this work is original and has not been published elsewhere, nor is it currently under consideration for publication elsewhere.

APA, Harvard, Vancouver, ISO, and other styles

35

Blair, Charles. "Geometric Algorithms and Combinatorial Optimization (Martin Grotschel, Laszló Lovász, and Alexander Schrijver)." SIAM Review 31, no. 2 (June 1989): 332–33. http://dx.doi.org/10.1137/1031067.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Peres, Fernando, and Mauro Castelli. "Combinatorial Optimization Problems and Metaheuristics: Review, Challenges, Design, and Development." Applied Sciences 11, no. 14 (July 13, 2021): 6449. http://dx.doi.org/10.3390/app11146449.

Full text

Abstract:

In the past few decades, metaheuristics have demonstrated their suitability in addressing complex problems over different domains. This success drives the scientific community towards the definition of new and better-performing heuristics and results in an increased interest in this research field. Nevertheless, new studies have been focused on developing new algorithms without providing consolidation of the existing knowledge. Furthermore, the absence of rigor and formalism to classify, design, and develop combinatorial optimization problems and metaheuristics represents a challenge to the field’s progress. This study discusses the main concepts and challenges in this area and proposes a formalism to classify, design, and code combinatorial optimization problems and metaheuristics. We believe these contributions may support the progress of the field and increase the maturity of metaheuristics as problem solvers analogous to other machine learning algorithms.

APA, Harvard, Vancouver, ISO, and other styles

37

Arram, Anas, Masri Ayob, and Alaa Sulaiman. "Hybrid Bird Mating Optimizer With Single-Based Algorithms for Combinatorial Optimization Problems." IEEE Access 9 (2021): 115972–89. http://dx.doi.org/10.1109/access.2021.3102154.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Mattas, Konstantinos, George Botzoris, and Basil Papadopoulos. "Application of Fuzzy Sets for the Improvement of Routing Optimization Heuristic Algorithms." Transport and Telecommunication Journal 17, no. 4 (December 1, 2016): 350–61. http://dx.doi.org/10.1515/ttj-2016-0031.

Full text

Abstract:

Abstract The determination of the optimal circular path has become widely known for its difficulty in producing a solution and for the numerous applications in the scope of organization and management of passenger and freight transport. It is a mathematical combinatorial optimization problem for which several deterministic and heuristic models have been developed in recent years, applicable to route organization issues, passenger and freight transport, storage and distribution of goods, waste collection, supply and control of terminals, as well as human resource management. Scope of the present paper is the development, with the use of fuzzy sets, of a practical, comprehensible and speedy heuristic algorithm for the improvement of the ability of the classical deterministic algorithms to identify optimum, symmetrical or non-symmetrical, circular route. The proposed fuzzy heuristic algorithm is compared to the corresponding deterministic ones, with regard to the deviation of the proposed solution from the best known solution and the complexity of the calculations needed to obtain this solution. It is shown that the use of fuzzy sets reduced up to 35% the deviation of the solution identified by the classical deterministic algorithms from the best known solution.

APA, Harvard, Vancouver, ISO, and other styles

39

Thilagavathi, N., and T. Amudha. "A novel methodology for optimal land allocation for agricultural crops using Social Spider Algorithm." PeerJ 7 (September 17, 2019): e7559. http://dx.doi.org/10.7717/peerj.7559.

Full text

Abstract:

In the current agricultural scenario, availability of suitable land for cultivation is less and profitable allocation of the land for cultivating crops seems to be a cumbersome task. Crop planning optimization is a major research field in agriculture, in which land optimization is a significant challenge, which falls under the category of combinatorial optimization problems. The main objective of the present research is to maximize the net income from agriculture through optimal land allocation. Bio-inspired algorithms are quite popular in solving combinatorial optimization problems. Social Spider Algorithm (SSA), a new bio-inspired algorithm, is used to solve land optimization problem in this research based on the simulation of cooperative behaviour of social spiders. The agricultural area chosen for case study is the Coimbatore region, located in Tamilnadu state, India and the relevant data for the crops are collected from Tamilnadu Agricultural University Coimbatore, India. The optimal planting area, crop productivity for various land holdings and the water requirements are computed by SSA and the results have shown better directions for agricultural planning to improve the profit with constrained land area and water limitations.

APA, Harvard, Vancouver, ISO, and other styles

40

Baykasoğlu, Adil, and Mümin Emre Şenol. "Weighted superposition attraction algorithm for combinatorial optimization." Expert Systems with Applications 138 (December 2019): 112792. http://dx.doi.org/10.1016/j.eswa.2019.07.009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Zaman, A. G. M., Sajib Hasan, and Mohammad Samawat Ulla. "Evaluation of TSP for Emergency Routing." International Journal of Information Technology and Computer Science 13, no. 1 (February 8, 2021): 44–53. http://dx.doi.org/10.5815/ijitcs.2021.01.03.

Full text

Abstract:

The paper considers the symmetric traveling salesman problem and applies it to sixty-four (64) districts of Bangladesh (with geographic coordinates) as a new instance of the problem of finding an optimized route in need of emergency. It approached three different algorithms namely Integer Linear Programming, Nearest-neighbor, and Metric TSP as exact, heuristic, or approximate methods of solving the NP-hard class of problem to model the emergency route planning. These algorithms have been implanted using computer codes, used IBM ILOG CPLEX parallel optimization, visualized using Geographic Information System tools. The performance of these algorithms also has been evaluated in terms of computational complexity, their run-time, and resulted tour distance using exact, approximate, and heuristic methods to find the best fit of route optimization in emergence thus contributing to the field of combinatorial optimization.

APA, Harvard, Vancouver, ISO, and other styles

42

Tarnawski, Jakub. "New graph algorithms via polyhedral techniques." it - Information Technology 63, no. 3 (April 15, 2021): 177–82. http://dx.doi.org/10.1515/itit-2021-0014.

Full text

Abstract:

Abstract This article gives a short overview of my dissertation, where new algorithms are given for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. The first part of the dissertation addresses a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given edge-weighted directed graph. A ρ-approximation algorithm for ATSP is one that runs in polynomial time and always produces a tour at most ρ times longer than the shortest tour. Finding such an algorithm with constant ρ had been a long-standing open problem. Here we give such an algorithm. The second part of the dissertation addresses the perfect matching problem. We have known since the 1980s that it has efficient parallel algorithms if the use of randomness is allowed. However, we do not know if randomness is necessary – that is, whether the matching problem is in the class NC. We show that it is in the class quasi-NC. That is, we give a deterministic parallel algorithm that runs in poly-logarithmic time on quasi-polynomially many processors.

APA, Harvard, Vancouver, ISO, and other styles

43

Zhou, Wenchen, Weiwei Fang, Yangyang Li, Bo Yuan, Yiming Li, and Tian Wang. "Markov Approximation for Task Offloading and Computation Scaling in Mobile Edge Computing." Mobile Information Systems 2019 (January 23, 2019): 1–12. http://dx.doi.org/10.1155/2019/8172698.

Full text

Abstract:

Mobile edge computing (MEC) provides cloud-computing services for mobile devices to offload intensive computation tasks to the physically proximal MEC servers. In this paper, we consider a multiserver system where a single mobile device asks for computation offloading to multiple nearby servers. We formulate this offloading problem as the joint optimization of computation task assignment and CPU frequency scaling, in order to minimize a tradeoff between task execution time and mobile energy consumption. The resulting optimization problem is combinatorial in essence, and the optimal solution generally can only be obtained by exhaustive search with extremely high complexity. Leveraging the Markov approximation technique, we propose a light-weight algorithm that can provably converge to a bounded near-optimal solution. The simulation results show that the proposed algorithm is able to generate near-optimal solutions and outperform other benchmark algorithms.

APA, Harvard, Vancouver, ISO, and other styles

44

Goto, Hayato, Kosuke Tatsumura, and Alexander R. Dixon. "Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems." Science Advances 5, no. 4 (April 2019): eaav2372. http://dx.doi.org/10.1126/sciadv.aav2372.

Full text

Abstract:

Combinatorial optimization problems are ubiquitous but difficult to solve. Hardware devices for these problems have recently been developed by various approaches, including quantum computers. Inspired by recently proposed quantum adiabatic optimization using a nonlinear oscillator network, we propose a new optimization algorithm simulating adiabatic evolutions of classical nonlinear Hamiltonian systems exhibiting bifurcation phenomena, which we call simulated bifurcation (SB). SB is based on adiabatic and chaotic (ergodic) evolutions of nonlinear Hamiltonian systems. SB is also suitable for parallel computing because of its simultaneous updating. Implementing SB with a field-programmable gate array, we demonstrate that the SB machine can obtain good approximate solutions of an all-to-all connected 2000-node MAX-CUT problem in 0.5 ms, which is about 10 times faster than a state-of-the-art laser-based machine called a coherent Ising machine. SB will accelerate large-scale combinatorial optimization harnessing digital computer technologies and also offer a new application of computational and mathematical physics.

APA, Harvard, Vancouver, ISO, and other styles

45

Zhu, Ming, Qiang Yang, Jianping Dong, Gexiang Zhang, Xiantai Gou, Haina Rong, Prithwineel Paul, and Ferrante Neri. "An Adaptive Optimization Spiking Neural P System for Binary Problems." International Journal of Neural Systems 31, no. 01 (September 16, 2020): 2050054. http://dx.doi.org/10.1142/s0129065720500549.

Full text

Abstract:

Optimization Spiking Neural P System (OSNPS) is the first membrane computing model to directly derive an approximate solution of combinatorial problems with a specific reference to the 0/1 knapsack problem. OSNPS is composed of a family of parallel Spiking Neural P Systems (SNPS) that generate candidate solutions of the binary combinatorial problem and a Guider algorithm that adjusts the spiking probabilities of the neurons of the P systems. Although OSNPS is a pioneering structure in membrane computing optimization, its performance is competitive with that of modern and sophisticated metaheuristics for the knapsack problem only in low dimensional cases. In order to overcome the limitations of OSNPS, this paper proposes a novel Dynamic Guider algorithm which employs an adaptive learning and a diversity-based adaptation to control its moving operators. The resulting novel membrane computing model for optimization is here named Adaptive Optimization Spiking Neural P System (AOSNPS). Numerical result shows that the proposed approach is effective to solve the 0/1 knapsack problems and outperforms multiple various algorithms proposed in the literature to solve the same class of problems even for a large number of items (high dimensionality). Furthermore, case studies show that a AOSNPS is effective in fault sections estimation of power systems in different types of fault cases: including a single fault, multiple faults and multiple faults with incomplete and uncertain information in the IEEE 39 bus system and IEEE 118 bus system.

APA, Harvard, Vancouver, ISO, and other styles

46

Onwubolu, G. C. "Manufacturing cell scheduling using genetic algorithms." Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture 214, no. 2 (February 1, 2000): 159–63. http://dx.doi.org/10.1243/0954405001517531.

Full text

Abstract:

This paper presents a new approach to the scheduling of manufacturing cells which have flow-shop configuration. The approach is based on the genetic algorithm, which is a meta-heuristic for solving combinatorial optimization problems. The performance measure demonstrated in this paper is the optimization of the mean flow time. The procedure developed automatically computes the make-span. A flexible manufacturing cell schedule is used as a case study. The genetic algorithm procedure was used to solve a published data set for simple scheduling problems. The genetic algorithm procedure was further used to solve large flow-shop scheduling problems having machine sizes of up to 30 and job sizes of up to 100 in very reasonable computation time. The results show that the genetic-algorithm-based heuristic is promising for scheduling manufacturing cells.

APA, Harvard, Vancouver, ISO, and other styles

47

HALAVATI, RAMIN, and SAEED BAGHERI SHOURAKI. "SYMBIOTIC EVOLUTIONARY ALGORITHM, A REMEDY FOR LINKAGE PROBLEM." International Journal of Computational Intelligence and Applications 08, no. 03 (September 2009): 237–52. http://dx.doi.org/10.1142/s1469026809002606.

Full text

Abstract:

Recombination in Genetic Algorithms (GA) is supposed to extract the component characteristics from two parents and reassemble them in different combinations, hopefully producing an offspring that has the good characteristics of both parents, and this requires explicit chromosome and recombination, operator by design. This paper presents a novel evolutionary approach based on symbiogenesis which uses symbiotic combination instead of sexual recombination, and by using this operator, it requires no domain knowledge for chromosome or combination operator design. The algorithm is benchmarked on three problem sets: combinatorial optimization category, deceptive problems, and fully deceptive problems. The results, compared with that of standard genetic algorithm and symbiotic evolutionary adaptation model, show higher success rates and faster results.

APA, Harvard, Vancouver, ISO, and other styles

48

Oliveto, Pietro S., Jun He, and Xin Yao. "Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results." International Journal of Automation and Computing 4, no. 3 (July 2007): 281–93. http://dx.doi.org/10.1007/s11633-007-0281-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Nallakumarasamy, G., PSS Srinivasan, K. Venkatesh Raja, and R. Malayalamurthi. "Optimization of Operation Sequencing in CAPP Using Superhybrid Genetic Algorithms-Simulated Annealing Technique." ISRN Mechanical Engineering 2011 (June 26, 2011): 1–7. http://dx.doi.org/10.5402/2011/897498.

Full text

Abstract:

Computer-aided process planning (CAPP) is an important interface between computer-aided design (CAD) and computer-aided manufacturing (CAM) in computer-integrated manufacturing environment. A problem in traditional CAPP system is that the multiple planning tasks are treated in a linear approach. This leads to an overconstrained overall solution space, and the final solution is normally far from optimal or even nonfeasible. A single sequence of operations may not be the best for all the situations in a changing production environment with multiple objectives such as minimizing number of setups, maximizing machine utilization, and minimizing number of tool changes. In general, the problem has combinatorial characteristics and complex precedence relations, which makes the problem more difficult to solve. The main contribution of this work is to develop an intelligent CAPP system for shop-floor use that can be used by an average operator and to produce globally optimized results. In this paper, the feasible sequences of operations are generated based on the precedence cost matrix (PCM) and reward-penalty matrix (REPMAX) using superhybrid genetic algorithms-simulated annealing technique (S-GENSAT), a hybrid metaheuristic. Also, solution space reduction methodology based on PCM and REPMAX upgrades the procedure to superhybridization. In this work, a number of benchmark case studies are considered to demonstrate the feasibility and robustness of the proposed super-hybrid algorithm. This algorithm performs well on all the test problems, exceeding or matching the solution quality of the results reported in the literature. The main contribution of this work focuses on reducing the optimal cost with a lesser computational time along with generation of more alternate optimal feasible sequences. Also, the proposed S-GENSAT integrates solution space reduction, hybridization, trapping out of local minima, robustness, and convergence; it consistently outperformed both a conventional genetic algorithm and a conventional simulated annealing algorithm.

APA, Harvard, Vancouver, ISO, and other styles

50

Candia-Véjar, Alfredo, Eduardo Álvarez-Miranda, and Nelson Maculan. "Minmax regret combinatorial optimization problems: an Algorithmic Perspective." RAIRO - Operations Research 45, no. 2 (April 2011): 101–29. http://dx.doi.org/10.1051/ro/2011111.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Combinatorial optimization Computer algorithms'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles