Log in

Relevant bibliographies by topics / NP-Hard optimization problems / Journal articles

Journal articles on the topic 'NP-Hard optimization problems'

To see the other types of publications on this topic, follow the link: NP-Hard optimization problems.

Author: Grafiati

Published: 10 December 2022

Last updated: 28 January 2023

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

Select a source type:

Consult the top 50 journal articles for your research on the topic 'NP-Hard optimization problems.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Cai, Liming, David Juedes, and Iyad Kanj. "The inapproximability of non-NP-hard optimization problems." Theoretical Computer Science 289, no. 1 (October 2002): 553–71. http://dx.doi.org/10.1016/s0304-3975(01)00343-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Kremer, Ulrich. "Optimal and Near–Optimal Solutions for Hard Compilation Problems." Parallel Processing Letters 07, no. 04 (December 1997): 371–78. http://dx.doi.org/10.1142/s0129626497000371.

Full text

Abstract:

An optimizing compiler typically uses multiple program representations at different levels of program and performance abstractions in order to be able to perform transformations that – at least in the majority of cases – will lead to an overall improvement in program performance. The complexities of the program and performance abstractions used to formulate compiler optimization problems have to match the complexities of the high–level programming model and of the underlying target system. Scalable parallel systems typically have multi–level memory hierarchies and able to exploit coarse–grain and fine–grain parallelism. Most likely, future systems will have even deeper memory hierarchies and more granularities of parallelism. As a result, future compiler optimizations will have to use more and more complex, multi–level computation and performance models in order to keep up with the complexities of their future target systems. Most of the optimization problems encountered in highly optimizing compilers are already NP–hard, and there is little hope that most newly encountered optimization formulations will not be at least NP–hard as well. To face this "complexity crisis", new methods are needed to evaluate the benefits of a compiler optimization formulation. A crucial step in this evaluation process is to compute the optimal solution of the formulation. Using ad–hoc methods to compute optimal solutions to NP–complete problems may be prohibitively expensive. Recent improvements in mixed integer and 0–1 integer programming suggest that this technology may provide the key to efficient, optimal and near–optimal solutions to NP–complete compiler optimization problems. In fact, early results indicate that integer programming formulations may be efficient enough to be included in not only evaluation prototypes, but in production programming environments or even production compilers. This paper discusses the potential benefits of integer programming as a tool to deal with NP–complete compiler optimization formulations in compilers and programming environments.

APA, Harvard, Vancouver, ISO, and other styles

3

Hidalgo-Herrero, Mercedes, Pablo Rabanal, Ismael Rodríguez, and Fernando Rubio. "Comparing Problem Solving Strategies for NP-hard Optimization Problems." Fundamenta Informaticae 124, no. 1-2 (2013): 1–25. http://dx.doi.org/10.3233/fi-2013-822.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Žerovnik, Janez. "Heuristics for NP-hard optimization problems - simpler is better!?" Logistics & Sustainable Transport 6, no. 1 (November 1, 2015): 1–10. http://dx.doi.org/10.1515/jlst-2015-0006.

Full text

Abstract:

Abstract We provide several examples showing that local search, the most basic metaheuristics, may be a very competitive choice for solving computationally hard optimization problems. In addition, generation of starting solutions by greedy heuristics should be at least considered as one of very natural possibilities. In this critical survey, selected examples discussed include the traveling salesman, the resource-constrained project scheduling, the channel assignment, and computation of bounds for the Shannon capacity.

APA, Harvard, Vancouver, ISO, and other styles

5

Arora, Sanjeev. "Approximation schemes for NP-hard geometric optimization problems: a survey." Mathematical Programming 97, no. 1 (July 2003): 43–69. http://dx.doi.org/10.1007/s10107-003-0438-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Toktoshov, Gulzhigit Y., Anastasiya N. Yurgenson, and Denis A. Migov. "COMPLEXITY ANALYSIS OF OPTIMIZATION PROBLEMS OF UTILITYCOMMUNICATIONS NETWORKS." T-Comm 14, no. 9 (2020): 17–23. http://dx.doi.org/10.36724/2072-8735-2020-14-9-17-23.

Full text

Abstract:

The problems of optimizing engineering communications networks according to various criteria, such as, minimum total construction costs, reliability, and compatibility are considered. A new technique for modeling utility networks based on the hypernet model, which allows one to take into account the nesting of one structure in another and the interdependence of indicators of the elements of these structures, is proposed. This approach makes the considered in these paper optimizations problems universal, and allows to take into account the interaction of the designed types of networks with each other. In addition, by combining the problems presented in this paper, various variations of optimization problems can be obtained. In this case, multicriterial tasks are stated, such as design networks of minimum cost, taking into account their reliability; design networks of minimum cost, taking into account their compatibility and reliability, and others. Note that all these problems are NP-hard, for the solution of which do not exist polynomial exacts algorithms. In particular, it was shown that the optimization problem in the simplest hypernet formulation is NP-hard. The possibility of applying accurate and approximate methods for solving them, and assessing the accuracy of these methods, were examined.

APA, Harvard, Vancouver, ISO, and other styles

7

Horng, Shih-Cheng, and Shieh-Shing Lin. "Coupling Elephant Herding with Ordinal Optimization for Solving the Stochastic Inequality Constrained Optimization Problems." Applied Sciences 10, no. 6 (March 19, 2020): 2075. http://dx.doi.org/10.3390/app10062075.

Full text

Abstract:

The stochastic inequality constrained optimization problems (SICOPs) consider the problems of optimizing an objective function involving stochastic inequality constraints. The SICOPs belong to a category of NP-hard problems in terms of computational complexity. The ordinal optimization (OO) method offers an efficient framework for solving NP-hard problems. Even though the OO method is helpful to solve NP-hard problems, the stochastic inequality constraints will drastically reduce the efficiency and competitiveness. In this paper, a heuristic method coupling elephant herding optimization (EHO) with ordinal optimization (OO), abbreviated as EHOO, is presented to solve the SICOPs with large solution space. The EHOO approach has three parts, which are metamodel construction, diversification and intensification. First, the regularized minimal-energy tensor-product splines is adopted as a metamodel to approximately evaluate fitness of a solution. Next, an improved elephant herding optimization is developed to find N significant solutions from the entire solution space. Finally, an accelerated optimal computing budget allocation is utilized to select a superb solution from the N significant solutions. The EHOO approach is tested on a one-period multi-skill call center for minimizing the staffing cost, which is formulated as a SICOP. Simulation results obtained by the EHOO are compared with three optimization methods. Experimental results demonstrate that the EHOO approach obtains a superb solution of higher quality as well as a higher computational efficiency than three optimization methods.

APA, Harvard, Vancouver, ISO, and other styles

8

Horng, Shih-Cheng, and Shieh-Shing Lin. "Embedding Ordinal Optimization into Tree–Seed Algorithm for Solving the Probabilistic Constrained Simulation Optimization Problems." Applied Sciences 8, no. 11 (November 3, 2018): 2153. http://dx.doi.org/10.3390/app8112153.

Full text

Abstract:

Probabilistic constrained simulation optimization problems (PCSOP) are concerned with allocating limited resources to achieve a stochastic objective function subject to a probabilistic inequality constraint. The PCSOP are NP-hard problems whose goal is to find optimal solutions using simulation in a large search space. An efficient “Ordinal Optimization (OO)” theory has been utilized to solve NP-hard problems for determining an outstanding solution in a reasonable amount of time. OO theory to solve NP-hard problems is an effective method, but the probabilistic inequality constraint will greatly decrease the effectiveness and efficiency. In this work, a method that embeds ordinal optimization (OO) into tree–seed algorithm (TSA) (OOTSA) is firstly proposed for solving the PCSOP. The OOTSA method consists of three modules: surrogate model, exploration and exploitation. Then, the proposed OOTSA approach is applied to minimize the expected lead time of semi-finished products in a pull-type production system, which is formulated as a PCSOP that comprises a well-defined search space. Test results obtained by the OOTSA are compared with the results obtained by three heuristic approaches. Simulation results demonstrate that the OOTSA method yields an outstanding solution of much higher computing efficiency with much higher quality than three heuristic approaches.

APA, Harvard, Vancouver, ISO, and other styles

9

Yu, Fa Hong, Wei Zhi Liao, and Mei Jia Chen. "An Novel Estimation of Distribution Algorithm for TSP." Applied Mechanics and Materials 373-375 (August 2013): 1089–92. http://dx.doi.org/10.4028/www.scientific.net/amm.373-375.1089.

Full text

Abstract:

Estimation of distribution algorithms (EDAs) is a method for solving NP-hard problem. But it is hard to find global optimization quickly for some problems, especially for traveling salesman problem (TSP) that is a classical NP-hard combinatorial optimization problem. To solve TSP effectively, a novel estimation of distribution algorithm (NEDA ) is provided, which can solve the conflict between population diversity and algorithm convergence. The experimental results show that the performance of NEDA is effective.

APA, Harvard, Vancouver, ISO, and other styles

10

Toth, Paolo. "Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems." European Journal of Operational Research 125, no. 2 (September 2000): 222–38. http://dx.doi.org/10.1016/s0377-2217(99)00453-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Paschos, Vangelis. "An overview on polynomial approximation of NP-hard problems." Yugoslav Journal of Operations Research 19, no. 1 (2009): 3–40. http://dx.doi.org/10.2298/yjor0901003p.

Full text

Abstract:

The fact that polynomial time algorithm is very unlikely to be devised for an optimal solving of the NP-hard problems strongly motivates both the researchers and the practitioners to try to solve such problems heuristically, by making a trade-off between computational time and solution's quality. In other words, heuristic computation consists of trying to find not the best solution but one solution which is 'close to' the optimal one in reasonable time. Among the classes of heuristic methods for NP-hard problems, the polynomial approximation algorithms aim at solving a given NP-hard problem in poly-nomial time by computing feasible solutions that are, under some predefined criterion, as near to the optimal ones as possible. The polynomial approximation theory deals with the study of such algorithms. This survey first presents and analyzes time approximation algorithms for some classical examples of NP-hard problems. Secondly, it shows how classical notions and tools of complexity theory, such as polynomial reductions, can be matched with polynomial approximation in order to devise structural results for NP-hard optimization problems. Finally, it presents a quick description of what is commonly called inapproximability results. Such results provide limits on the approximability of the problems tackled.

APA, Harvard, Vancouver, ISO, and other styles

12

Wong, W. S. "Matrix representation and gradient flows for NP-hard problems." Journal of Optimization Theory and Applications 87, no. 1 (October 1995): 197–220. http://dx.doi.org/10.1007/bf02192047.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Manyem, Prabhu. "Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap." Optimization 62, no. 9 (September 2013): 1227–46. http://dx.doi.org/10.1080/02331934.2011.625027.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Nemirovskii, A. "Several NP-hard problems arising in robust stability analysis." Mathematics of Control, Signals, and Systems 6, no. 2 (June 1993): 99–105. http://dx.doi.org/10.1007/bf01211741.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Choi, Vicky. "Different adiabatic quantum optimization algorithms." Quantum Information and Computation 11, no. 7&8 (July 2011): 638–48. http://dx.doi.org/10.26421/qic11.7-8-7.

Full text

Abstract:

One of the most important questions in studying quantum computation is: whether a quantum computer can solve NP-complete problems more efficiently than a classical computer? In 2000, Farhi, et al. (Science, 292(5516):472--476, 2001) proposed the adiabatic quantum optimization (AQO), a paradigm that directly attacks NP-hard optimization problems. How powerful is AQO? Early on, van-Dam and Vazirani claimed that AQO failed (i.e. would take exponential time) for a family of 3SAT instances they constructed. More recently, Altshuler, et al. (Proc Natl Acad Sci USA, 107(28): 12446--12450, 2010) claimed that AQO failed also for random instances of the NP-complete Exact Cover problem. In this paper, we make clear that all these negative results are only for a specific AQO algorithm. We do so by demonstrating different AQO algorithms for the same problem for which their arguments no longer hold. Whether AQO fails or succeeds for solving the NP-complete problems (either the worst case or the average case) requires further investigation. Our AQO algorithms for Exact Cover and 3SAT are based on the polynomial reductions to the NP-complete Maximum-weight Independent Set (MIS) problem.

APA, Harvard, Vancouver, ISO, and other styles

16

Yu, Dian, Yanrong Tao, and Yue Ma. "Solving TSP Problems with Integer Programming." Journal of Physics: Conference Series 2381, no. 1 (December 1, 2022): 012045. http://dx.doi.org/10.1088/1742-6596/2381/1/012045.

Full text

Abstract:

Abstract The traveling salesman problem (TSP) is one of the NP-hard problems in combinatorial optimization. This paper focuses on finding the optimal planning path using integer programming and adding time allocation to minimize the cost. The use and accuracy of various algorithms are also compared in solving this problem.

APA, Harvard, Vancouver, ISO, and other styles

17

Sabba, Sara, and Salim Chikhi. "A Novel Evolutionary Algorithm for Multidimensional Knapsack Problem." International Journal of Operations Research and Information Systems 6, no. 2 (April 2015): 1–20. http://dx.doi.org/10.4018/ijoris.2015040101.

Full text

Abstract:

Binary optimization problems are in the most case the NP-hard problems that call to satisfy an objective function with or without constraints. Various optimization problems can be formulated in binary expression whither they can be resolved in easier way. Optimization literature supplies a large number of approaches to find solutions to binary hard problems. However, most population-based algorithms have a great tendency to be trapped in local optima particularly when solving complex optimization problems. In this paper, the authors introduce a new efficient population-based technique for binary optimization problems (that we called EABOP). The proposed algorithm can provide an effective search through a new proposed binary mutation operator. The performance of our approach was tested on hard instances of the multidimensional knapsack problem. The obtained results show that the new algorithm is able of quickly obtaining high-quality solutions for most hard instances of the problem.

APA, Harvard, Vancouver, ISO, and other styles

18

YANG, XIAOGUANG, SHUO TAO, RONGJUN LIU, and MAOCHENG CAI. "COMPLEXITY OF SCENARIO-BASED PORTFOLIO OPTIMIZATION PROBLEM WITH VaR OBJECTIVE." International Journal of Foundations of Computer Science 13, no. 05 (October 2002): 671–79. http://dx.doi.org/10.1142/s0129054102001370.

Full text

Abstract:

In this paper we discuss the VaR-related portfolio optimization problems. We give a scenario-based formulation of the portfolio optimization problem with VaR objective and show that the problem is NP-hard.

APA, Harvard, Vancouver, ISO, and other styles

19

Hong, Dawei, and Jean-Camille Birget. "Approximation of some NP-hard optimization problems by finite machines, in probability." Theoretical Computer Science 259, no. 1-2 (May 2001): 323–39. http://dx.doi.org/10.1016/s0304-3975(00)00016-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Zissimopoulos, V. "On the performance guarantee of neural networks for NP-hard optimization problems." Information Processing Letters 54, no. 6 (June 1995): 317–22. http://dx.doi.org/10.1016/0020-0190(95)00051-d.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Coja-Oghlan, Amin. "Solving NP-hard semirandom graph problems in polynomial expected time." Journal of Algorithms 62, no. 1 (January 2007): 19–46. http://dx.doi.org/10.1016/j.jalgor.2004.07.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Karpinski, M. "Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems." Algorithmica 30, no. 3 (January 2001): 386–97. http://dx.doi.org/10.1007/s00453-001-0012-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

BILU, YONATAN, and NATHAN LINIAL. "Are Stable Instances Easy?" Combinatorics, Probability and Computing 21, no. 5 (July 26, 2012): 643–60. http://dx.doi.org/10.1017/s0963548312000193.

Full text

Abstract:

We introduce the notion of a stable instance for a discrete optimization problem, and argue that in many practical situations only sufficiently stable instances are of interest. The question then arises whether stable instances of NP-hard problems are easier to solve, and in particular, whether there exist algorithms that solve in polynomial time all sufficiently stable instances of some NP-hard problem. The paper focuses on the Max-Cut problem, for which we show that this is indeed the case.

APA, Harvard, Vancouver, ISO, and other styles

24

Verbitsky, Oleg. "On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE." Combinatorics, Probability and Computing 4, no. 2 (June 1995): 167–80. http://dx.doi.org/10.1017/s0963548300001553.

Full text

Abstract:

We focus our attention on the class RMAX(2) of NP optimization problems. Owing to recent developments in interactive proof techniques, RMAX(2) was shown to be the lowest class of logical classification that contains problems hard to approximate. Namely, the RMAX(2)-complete problem MAX CLIQUE (of finding the size of the largest clique in a graph) is not approximable in polynomial time within any constant factor unless NP=P.We are interested in problems inside RMAX(2) that are not known to be complete but are still hard to approximate. We point out that one such problem is MAXlog n, n, considered by Berman and Schnitger: given m conjunctions, each of them consisting of log m propositional variables or their negations, find the maximal number of simultaneously satisfiable conjunctions. We also obtain the approximation hardness results for some other problems in RMAX(2). Finally, we discuss the question of whether or not the problems under consideration are RMAX(2)-complete.

APA, Harvard, Vancouver, ISO, and other styles

25

Angelov, Kamen. "Main Architectures Used in ETL as a Tool, Necessary for the Integration of Data in Large Volumes - a Task in the Field of Digital Preservation of Cultural Heritage." Digital Presentation and Preservation of Cultural and Scientific Heritage 6 (September 30, 2016): 129–36. http://dx.doi.org/10.55630/dipp.2016.6.12.

Full text

Abstract:

The digital recording of Cultural Heritage (CH) and its metadata relates to the concept for data warehousing systems and their lifecycle. It uses models and development tools of ETL packages. The tasks used to extract metadata from raw digitized CH data often include hard computing problems, including NP-complete problems. This paper describes the current state of digital preservation of Cultural Heritage with an accent on data integration and performance optimization of processes. We show our vision for further solutions for automated optimization of resource utilization in ETL jobs cutting development cost. In parallel, we describe our experiment that uses quantum computation (in simulation mode) to solve hard combinatorial problems as multiple query optimization.

APA, Harvard, Vancouver, ISO, and other styles

26

Behmanesh, Reza. "Nephron Algorithm Optimization." International Journal of Applied Metaheuristic Computing 7, no. 1 (January 2016): 38–64. http://dx.doi.org/10.4018/ijamc.2016010103.

Full text

Abstract:

A new Meta heuristic algorithm inspired of the biologic nephron performance for optimization of objective functions in Np-hard problems is introduced. The complexity of the problems increases with their size, and hence their solution space increases exponentially. Despite of designing the several search techniques with balanced exploration and exploitation in order to solve such as these problems, there are some drawbacks to make suitable adjustment between exploring and exploiting in performance of the Meta heuristic algorithms. The proposed algorithm in this paper can adjust between intensification and diversification strategies intrinsically, to make efficient optimization technique. For testing Nephron algorithm optimization (NAO), the traveling salesman problem (TSP) is provided as a solution in various sizes. Results indicate that NAO provides robust optimal solutions.

APA, Harvard, Vancouver, ISO, and other styles

27

URAHAMA, KIICHI, and HIROSHI NISHIYUKI. "PERFORMANCE OF THE RELAXATION ALGORITHM FOR MAXIMUM-CUT PROBLEMS." Journal of Circuits, Systems and Computers 06, no. 04 (August 1996): 375–84. http://dx.doi.org/10.1142/s021812669600025x.

Full text

Abstract:

A relaxation algorithm is presented for solving a class of combinatorial optimization problems called set-partitioning tasks. The convergence property of the presented algorithm is investigated theoretically. A performance guarantee is derived theoretically for the present algorithm applied to an NP-hard example problem called the maximum-cut graph partitioning. The experimental examination of its performance manifests its superiority in computational speed to the conventional gradient method.

APA, Harvard, Vancouver, ISO, and other styles

28

Renjith, P., and N. Sadagopan. "Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy." International Journal of Foundations of Computer Science 33, no. 01 (October 20, 2021): 1–32. http://dx.doi.org/10.1142/s0129054121500337.

Full text

Abstract:

For an optimization problem known to be NP-Hard, the dichotomy study investigates the reduction instances to determine the line separating polynomial-time solvable vs NP-Hard instances (easy vs hard instances). In this paper, we investigate the well-studied Hamiltonian cycle problem (HCYCLE), and present an interesting dichotomy result on split graphs. T. Akiyama et al. (1980) have shown that HCYCLE is NP-complete on planar bipartite graphs with maximum degree [Formula: see text]. We use this result to show that HCYCLE is NP-complete for [Formula: see text]-free split graphs. Further, we present polynomial-time algorithms for Hamiltonian cycle in [Formula: see text]-free and [Formula: see text]-free split graphs. We believe that the structural results presented in this paper can be used to show similar dichotomy result for Hamiltonian path problem and other variants of Hamiltonian cycle (path) problems.

APA, Harvard, Vancouver, ISO, and other styles

29

Rubio, Fernando, and Ismael Rodríguez. "Water-Based Metaheuristics: How Water Dynamics Can Help Us to Solve NP-Hard Problems." Complexity 2019 (April 2, 2019): 1–13. http://dx.doi.org/10.1155/2019/4034258.

Full text

Abstract:

Many water-based optimization metaheuristics have been introduced during the last decade, both for combinatorial and for continuous optimization. Despite the strong similarities of these methods in terms of their underlying natural metaphors (most of them emulate, in some way or another, how drops collaboratively form paths down to the sea), in general the resulting algorithms are quite different in terms of their searching approach or their solution construction approach. For instance, each entity may represent a solution by itself or, alternatively, entities may construct solutions by modifying the landscape while moving. A researcher or practitioner could assume that the degree of similarity between two water-based metaheuristics heavily depends on the similarity of the natural water mechanics they emulate, but this is not the case. In order to bring some clarity to this mosaic of apparently related metaheuristics, in this paper we introduce them, explain their mechanics, and highlight their differences.

APA, Harvard, Vancouver, ISO, and other styles

30

Alman, Sam M. "Department of Computer Science and Information Technology, College of Computer Science & Information Technology, Firat University, turkey." Qubahan Academic Journal 1, no. 1 (November 14, 2020): 46–63. http://dx.doi.org/10.48161/qaj.v1n1a8.

Full text

Abstract:

This paper provides uses a new Ant Colony based algorithms called U-Turning Ant colony optimization (U-TACO) for solving one of NP-Hard problems which is widely used in computer science field called Traveling Salesman Problem (TSP). U-Turning Ant colony Optimization based on making partial tour as an initial state for the basic Ant Colony algorithm. This paper provides tables and charts for the results obtained by U-Turning Ant colony Optimization for various TSP problems from the TSPLIB95.

APA, Harvard, Vancouver, ISO, and other styles

31

Deb, Suash, Simon Fong, Zhonghuan Tian, Raymond K. Wong, Sabah Mohammed, and Jinan Fiaidhi. "Finding approximate solutions of NP-hard optimization and TSP problems using elephant search algorithm." Journal of Supercomputing 72, no. 10 (May 24, 2016): 3960–92. http://dx.doi.org/10.1007/s11227-016-1739-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Hunt, Harry B., Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J. Rosenkrantz, and Richard E. Stearns. "NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs." Journal of Algorithms 26, no. 2 (February 1998): 238–74. http://dx.doi.org/10.1006/jagm.1997.0903.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

WU, LONGSHU, QIN WANG, and XIAOBING YANG. "COMPUTATIONAL METHODS FOR LOGISTICS PROBLEMS RELATED TO OPTIMAL TREES." ANZIAM Journal 58, no. 3-4 (March 7, 2017): 333–41. http://dx.doi.org/10.1017/s1446181117000074.

Full text

Abstract:

In recent years, balanced network optimization problems play an important role in practice, especially in information transmission, industry production and logistics management. In this paper, we consider some logistics optimization problems related to the optimal tree structures in a network. We show that the most optimal subtree problem is NP-hard by transforming the connected dominating set problem into this model. By constructing the network models of the most balanced spanning tree problem with edge set restrictions, and by finding the optimal subtrees in special networks, we present efficient computational methods for solving some logistics problems.

APA, Harvard, Vancouver, ISO, and other styles

34

Fattahi, Parviz, Mojdeh Shirazi Manesh, and Abdolreza Roshani. "A New Solution Seed for Job Shop Scheduling Problem." Applied Mechanics and Materials 110-116 (October 2011): 3899–905. http://dx.doi.org/10.4028/www.scientific.net/amm.110-116.3899.

Full text

Abstract:

Scheduling for job shop is very important in both fields of production management and combinatorial optimization. Since the problem is well known as NP-Hard class, many metaheuristic approaches are developed to solve the medium and large scale problems. One of the main elements of these metaheuristics is the solution seed structure. Solution seed represent the coding structure of real solution. In this paper, a new solution seed for job shop scheduling is presented. This solution seed is compared with a famous solution seed presented for the job shop scheduling. Since the problem is well known as NP-Hard class, a Tabu search algorithm is developed to solve large scale problems. The proposed solution seed are examined using an example and tabu search algorithm.

APA, Harvard, Vancouver, ISO, and other styles

35

Nallaperuma, Samadhi, Frank Neumann, and Dirk Sudholt. "Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem." Evolutionary Computation 25, no. 4 (December 2017): 673–705. http://dx.doi.org/10.1162/evco_a_00199.

Full text

Abstract:

Randomized search heuristics are frequently applied to NP-hard combinatorial optimization problems. The runtime analysis of randomized search heuristics has contributed tremendously to our theoretical understanding. Recently, randomized search heuristics have been examined regarding their achievable progress within a fixed-time budget. We follow this approach and present a fixed-budget analysis for an NP-hard combinatorial optimization problem. We consider the well-known Traveling Salesperson Problem (TSP) and analyze the fitness increase that randomized search heuristics are able to achieve within a given fixed-time budget. In particular, we analyze Manhattan and Euclidean TSP instances and Randomized Local Search (RLS), (1+1) EA and (1+[Formula: see text]) EA algorithms for the TSP in a smoothed complexity setting, and derive the lower bounds of the expected fitness gain for a specified number of generations.

APA, Harvard, Vancouver, ISO, and other styles

36

Horoba, Christian. "Exploring the Runtime of an Evolutionary Algorithm for the Multi-Objective Shortest Path Problem." Evolutionary Computation 18, no. 3 (September 2010): 357–81. http://dx.doi.org/10.1162/evco_a_00014.

Full text

Abstract:

We present a natural vector-valued fitness function f for the multi-objective shortest path problem, which is a fundamental multi-objective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems. Furthermore, we present lower bounds for the worst-case optimization time.

APA, Harvard, Vancouver, ISO, and other styles

37

Juan, Angel Alejandro, Canan Gunes Corlu, Rafael David Tordecilla, Rocio de la Torre, and Albert Ferrer. "On the Use of Biased-Randomized Algorithms for Solving Non-Smooth Optimization Problems." Algorithms 13, no. 1 (December 25, 2019): 8. http://dx.doi.org/10.3390/a13010008.

Full text

Abstract:

Soft constraints are quite common in real-life applications. For example, in freight transportation, the fleet size can be enlarged by outsourcing part of the distribution service and some deliveries to customers can be postponed as well; in inventory management, it is possible to consider stock-outs generated by unexpected demands; and in manufacturing processes and project management, it is frequent that some deadlines cannot be met due to delays in critical steps of the supply chain. However, capacity-, size-, and time-related limitations are included in many optimization problems as hard constraints, while it would be usually more realistic to consider them as soft ones, i.e., they can be violated to some extent by incurring a penalty cost. Most of the times, this penalty cost will be nonlinear and even noncontinuous, which might transform the objective function into a non-smooth one. Despite its many practical applications, non-smooth optimization problems are quite challenging, especially when the underlying optimization problem is NP-hard in nature. In this paper, we propose the use of biased-randomized algorithms as an effective methodology to cope with NP-hard and non-smooth optimization problems in many practical applications. Biased-randomized algorithms extend constructive heuristics by introducing a nonuniform randomization pattern into them. Hence, they can be used to explore promising areas of the solution space without the limitations of gradient-based approaches, which assume the existence of smooth objective functions. Moreover, biased-randomized algorithms can be easily parallelized, thus employing short computing times while exploring a large number of promising regions. This paper discusses these concepts in detail, reviews existing work in different application areas, and highlights current trends and open research lines.

APA, Harvard, Vancouver, ISO, and other styles

38

Wu, Kee Rong, and Chung Wei Yeh. "Solution to the 0-1 Multidimensional Knapsack Problem Based on DNA Computation." Applied Mechanics and Materials 58-60 (June 2011): 1767–72. http://dx.doi.org/10.4028/www.scientific.net/amm.58-60.1767.

Full text

Abstract:

We proposed a two-layer scheme of Deoxyribonucleic acid (DNA) based computation, DNA-01MKP, to solve the typical NP-hard combinatorial optimization problem, 0-1 multidimensional knapsack problem (0-1 MKP). DNA-01MKP consists of two layers of procedures: (1) translation of the problem equations to strands and (2) solution of problems. For layer 1, we designed flexible well-formatted strands to represent the problem equations; for layer 2, we constructed the DNA algorithms to solve the 0-1 MKP. Our results revealed that this molecular computation scheme is able to solve the complicated operational problem with a reasonable time complexity of O(n×k), though it needs further experimental verification in the future. By adjusting the DNA-based procedures, the scheme may be used to resolve different NP-hard problems.

APA, Harvard, Vancouver, ISO, and other styles

39

Gao, Lunshan. "An approximation algorithm for solving standard quadratic optimization problems." Journal of Intelligent & Fuzzy Systems 39, no. 3 (October 7, 2020): 4383–92. http://dx.doi.org/10.3233/jifs-200374.

Full text

Abstract:

Standard quadratic optimization problems (StQPs) are NP-hard in computational complexity theory when the matrix is indefinite. This paper describes an approximate algorithm of finding inner optimal values of StQPs. The approximate algorithm fuzzifies variable x ∈ Rn with normalized possibility distributions and simplifies the solving of StQPs. The approximation ratio is discussed and determined. Numerical results show that (1) the new algorithm achieves higher accuracy than the semidefinite programming method and linear programming approximation method; (2) the novel algorithm consumes less than one out of fourth computational time that is consumed by linear programming approximation method; (3) the computational time of the new algorithm does not correlate with the matrix densities whereas the computational times of the branch-and-bound and heuristic algorithms do.

APA, Harvard, Vancouver, ISO, and other styles

40

Eremeev, Anton, and Julia Kovalenko. "Optimal recombination in genetic algorithms for combinatorial optimization problems: Part II." Yugoslav Journal of Operations Research 24, no. 2 (2014): 165–86. http://dx.doi.org/10.2298/yjor131030041e.

Full text

Abstract:

This paper surveys results on complexity of the optimal recombination problem (ORP), which consists in finding the best possible offspring as a result of a recombination operator in a genetic algorithm, given two parent solutions. In Part II, we consider the computational complexity of ORPs arising in genetic algorithms for problems on permutations: the Travelling Salesman Problem, the Shortest Hamilton Path Problem and the Makespan Minimization on Single Machine and some other related problems. The analysis indicates that the corresponding ORPs are NP-hard, but solvable by faster algorithms, compared to the problems they are derived from.

APA, Harvard, Vancouver, ISO, and other styles

41

Jiao, Hong Wei, Jing Ben Yin, and Yun Rui Guo. "Optimization Method for Globally Solving a Kind of Multiplicative Problems with Coefficients." Key Engineering Materials 467-469 (February 2011): 526–30. http://dx.doi.org/10.4028/www.scientific.net/kem.467-469.526.

Full text

Abstract:

Multiplicative problems are a kind of difficult global optimization problems known to be NP-hard. At the same time, these problems have some important applications in engineering, system, finance, economics, and other fields. In this paper, an optimization method is proposed to globally solve a class of multiplicative problems with coefficients. Firstly, by utilizing equivalent transformation and linearization method, a linear relaxation programming problem is established. Secondly, by using branch and bound technique, a determined algorithm is proposed for solving equivalent problem. Finally, the proposed algorithm is convergent to the global optimal solution of original problem by means of the subsequent solutions of a series of linear programming problems.

APA, Harvard, Vancouver, ISO, and other styles

42

Amjad, M. K., S. I. Butt, N. Anjum, I. A. Chaudhry, Z. Faping, and M. Khan. "A layered genetic algorithm with iterative diversification for optimization of flexible job shop scheduling problems." Advances in Production Engineering & Management 15, no. 4 (December 24, 2020): 377–89. http://dx.doi.org/10.14743/apem2020.4.372.

Full text

Abstract:

Flexible job shop scheduling problem (FJSSP) is a further expansion of the classical job shop scheduling problem (JSSP). FJSSP is known to be NP-hard with regards to optimization and hence poses a challenge in finding acceptable solutions. Genetic algorithm (GA) has successfully been applied in this regard since last two decades. This paper provides an insight into the actual complexity of selected benchmark problems through quantitative evaluation of the search space owing to their NP-hard nature. A four-layered genetic algorithm is then proposed and implemented with adaptive parameters of population initialization and operator probabilities to manage intensification and diversification intelligently. The concept of reinitialization is introduced whenever the algorithm is trapped in local minima till predefined number of generations. Results are then compared with various other standalone evolutionary algorithms for selected benchmark problems. It is found that the proposed GA finds better solutions with this technique as compared to solutions produced without this technique. Moreover, the technique helps to overcome the local minima trap. Further comparison and analysis indicate that the proposed algorithm produces comparative and improved solutions with respect to other analogous methodologies owing to the diversification technique.

APA, Harvard, Vancouver, ISO, and other styles

43

Ardelean, Sebastian Mihai, and Mihai Udrescu. "Graph coloring using the reduced quantum genetic algorithm." PeerJ Computer Science 7 (January 3, 2022): e836. http://dx.doi.org/10.7717/peerj-cs.836.

Full text

Abstract:

Genetic algorithms (GA) are computational methods for solving optimization problems inspired by natural selection. Because we can simulate the quantum circuits that implement GA in different highly configurable noise models and even run GA on actual quantum computers, we can analyze this class of heuristic methods in the quantum context for NP-hard problems. This paper proposes an instantiation of the Reduced Quantum Genetic Algorithm (RQGA) that solves the NP-hard graph coloring problem in O(N1/2). The proposed implementation solves both vertex and edge coloring and can also determine the chromatic number (i.e., the minimum number of colors required to color the graph). We examine the results, analyze the algorithm convergence, and measure the algorithm's performance using the Qiskit simulation environment. Our Reduced Quantum Genetic Algorithm (RQGA) circuit implementation and the graph coloring results show that quantum heuristics can tackle complex computational problems more efficiently than their conventional counterparts.

APA, Harvard, Vancouver, ISO, and other styles

44

Mehmood, Nasir, Muhammad Umer, and Ahmad Riaz. "A Survey of Recent Developments for JSSP and FJSSP Using ACO." Advanced Materials Research 816-817 (September 2013): 1133–39. http://dx.doi.org/10.4028/www.scientific.net/amr.816-817.1133.

Full text

Abstract:

Ant Colony Optimization (ACO) is based on swarm intelligence and it is a constructive meta-heuristic which was first presented in 1991. Job Shop Scheduling Problem (JSSP) is very important problem of the manufacturing industry. JSSP is a combinatorial optimization problem which is NP-hard. The exact solution of NP-hard problem is very difficult to find. Therefore heuristics approach is the best approach for such problems. This paper shall overview the application of ant colony optimization on JSSP and Flexible Job Shop Scheduling problems (FJSSP). This paper shalll cover the major areas in which researchers have worked and it shall also recommend the future area of research in the light of this overview. This paper will also cover the quantitative analysis of the research papers which are considered in this survey. Based upon this survey some conclusions are drawn in the end.The significance of this paper is that it has covered all the efforts and major researches in the area of ACO application on JSSP and FJSSP through the inception of ACO metaheuristics. This enables the researchers and scheduling experts to overview chronologically the development of ACO on JSSP and FJSSP.

APA, Harvard, Vancouver, ISO, and other styles

45

Adams, Elspeth, Miguel F. Anjos, Franz Rendl, and Angelika Wiegele. "A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems." INFOR: Information Systems and Operational Research 53, no. 1 (February 2015): 40–48. http://dx.doi.org/10.3138/infor.53.1.40.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Li, Yan Cang, Juan Juan Suo, and Shu Jing Zhou. "Improved ACO for Dimensional Cutting-Stock Problem." Applied Mechanics and Materials 26-28 (June 2010): 277–80. http://dx.doi.org/10.4028/www.scientific.net/amm.26-28.277.

Full text

Abstract:

In order to find an effective method for solving the NP problem-dimensional cutting stock problem, the improved ACO based on entropy was introduced．After introducing the basic knowledge of the improved ACO, the dimensional cutting-stock problem’s mathematical model was set up．And the improved ACO was employed to optimize the problem．Computed results indicate that the ant colony algorithm can approach the theoretical optimal solution，and its astringency is good．This study provides a new approach for the optimization of the NP hard problems.

APA, Harvard, Vancouver, ISO, and other styles

47

N, Buvaneswari, and Rekha S. "Timetable Scheduling using Bipartite Graph." International Journal for Research in Applied Science and Engineering Technology 10, no. 12 (December 31, 2022): 1854–56. http://dx.doi.org/10.22214/ijraset.2022.47641.

Full text

Abstract:

Abstract: In any educational institution, the two most common academic scheduling problems are course timetabling and exam timetabling. A schedule is desirablewhich combines resources like teachers, subjects, students, classrooms in a way to avoid conflicts satisfying various essential and preferential constraints. The timetable scheduling problem is known to be NP Complete but the corresponding optimization problem is NP Hard. This problem is solved using bipartite graph. Hence a heuristic approach ispreferred to find a nearest optimal solution within reasonable running time

APA, Harvard, Vancouver, ISO, and other styles

48

Zharfi, Vahid, and Abolfazl Mirzazadeh. "A Novel Metaheuristic for Travelling Salesman Problem." Journal of Industrial Engineering 2013 (July 18, 2013): 1–5. http://dx.doi.org/10.1155/2013/347825.

Full text

Abstract:

One of the well-known combinatorial optimization problems is travelling salesman problem (TSP). This problem is in the fields of logistics, transportation, and distribution. TSP is among the NP-hard problems, and many different metaheuristics are used to solve this problem in an acceptable time especially when the number of cities is high. In this paper, a new meta-heuristic is proposed to solve TSP which is based on new insight into network routing problems.

APA, Harvard, Vancouver, ISO, and other styles

49

Almufti, Saman. "Vibrating Particles System Algorithm: Overview, Modifications and Applications." ICONTECH INTERNATIONAL JOURNAL 6, no. 3 (September 25, 2022): 1–11. http://dx.doi.org/10.46291/icontechvol6iss3pp1-11.

Full text

Abstract:

Real-world problems are difficult enough to encourages academics to develop innovative, effective problem-solving methods. Generally, metaheuristics algorithms that are inspired by nature, biology, and physics have a flexibility and capacity to adapt to different situations, metaheuristics based on evolutionary computation algorithms have been widely employed to solve complicated, constrained/unconstrained, single/multiple objective, and Non-deterministic polynomial hard (NP-Hard) optimization problems. This paper describes Vibrating Particles System (VPS) as a Physics Based metaheuristic algorithm inspired by the free vibration of an under-damping objects for solving complex and real-world optimization problems. Since the appearance of VPS many modifications for improving the performance of the algorithm and has been applied to various Applications in several fields. At the end of this paper, the improvements are listed.

APA, Harvard, Vancouver, ISO, and other styles

50

Arroyo Montoro, Fernando, Sandra Gómez-Canaval, Karina Jiménez Vega, and Alfonso Ortega de la Puente. "A Linear Time Solution for N-Queens Problem Using Generalized Networks of Evolutionary Polarized Processors." International Journal of Foundations of Computer Science 31, no. 01 (January 2020): 7–21. http://dx.doi.org/10.1142/s0129054120400018.

Full text

Abstract:

In this paper we consider a new variant of Networks of Polarized Evolutionary Processors (NPEP) named Generalized Networks of Evolutionary Polarized Processors (GNPEP) and propose them as solvers of combinatorial optimization problems. Unlike the NPEP model, GNPEP uses its numerical evaluation over the processed data from a quantitative perspective, hence this model might be more suitable to solve specific hard problems in a more efficient and economic way. In particular, we propose a GNPEP network to solve a well-known NP-hard problem, namely the [Formula: see text]-queens. We prove that this GNPEP algorithm requires a linear time in the size of a given instance. This result suggests that the GNPEP model is more suitable to address problems related to combinatorial optimization in which integer restrictions have a relevant role.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!