Relevant bibliographies by topics / NP-Hard optimization problems

Academic literature on the topic '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:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.

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

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
More sources

Dissertations / Theses on the topic "NP-Hard optimization problems"

1

Ono, Satoshi. "In pursuit of NP-hard combinatorial optimization problems." Diss., Online access via UMI:, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Li, Nan. "Algorithms for NP-hard Optimization Problems and Cluster Analysis." Diss., Temple University Libraries, 2017. http://cdm16002.contentdm.oclc.org/cdm/ref/collection/p245801coll10/id/482725.

Full text
Abstract:
Computer and Information Science
Ph.D.
The set cover problem, weighted set cover problem, minimum dominating set problem and minimum weighted dominating set problem are all classical NP-hard optimization problems of great importance in both theory and real applications. Since the exact algorithms, which require exhaustive exploration of exponentially many options, are infeasible in practice, approximation algorithms and heuristic algorithms are widely used to find reasonably good solutions in polynomial time. I propose novel algorithms for these problems. My algorithms for the weighted set cover and minimum weighted dominating set problems are based on a three-step strategy. For the weighted set cover problem, in the first step, we reserve the sets indispensable for the optimal solution and reduce the problem size. In the second step, we build a robust solution with a novel greedy heuristic. Sets are iteratively selected according to a measure which integrates the weight, the coverage gain for the current iteration and the global coverage capacity of each set. It favors the sets that have smaller weights and better extend or consolidate the coverage, especially on the items that are contained in less sets. Since the obtained solution tends to have a robust coverage, in the third step, we further improve it by removing the redundant sets in an efficient way. For the minimum weighted dominating set problem, we first reserve the indispensable vertices for the optimal solution. Then we convert it into a weighted set cover problem to solve it. These two algorithms can be used to solve the set cover problem and minimum dominating set problem by simply considering all the sets or vertices as having the same weights. Extensive experimental evaluations on a large number of synthetic and real-world set cover instances and graphs from many domains demonstrate the superiority of my algorithms over state-of-the-art. Cluster analysis is a fundamental problem in data analysis, and has extensive applications in artificial intelligence, statistics and even in social sciences. The goal is to partition the data objects into a set of groups (clusters) such that objects in the same group are similar, while objects in different groups are dissimilar. Most of the existing algorithms for clustering are designed to handle data with only one type of attributes, e.g. continuous, categorical or ordinal. Mixed data clustering has received relatively less attention, despite the fact that data with mixed types of attributes are common in real applications. I propose a novel affinity learning based framework for mixed data clustering, which includes: how to process data with mixed-type attributes, how to learn affinities between data points, and how to exploit the learned affinities for clustering. In the proposed framework, each original data attribute is represented with several abstract objects defined according to the specific data type and values. Each attribute value is transformed into the initial affinities between the data point and the abstract objects of attribute. I refine these affinities and infer the unknown affinities between data points by taking into account the interconnections among the attribute values of all data points. The inferred affinities between data points can be exploited for clustering. Alternatively, the refined affinities between data points and the abstract objects of attributes can be transformed into new data features for clustering. Experimental results on many real world data sets demonstrate that the proposed framework is effective for mixed data clustering. This work was published in our IJCAI 2017 paper Li & Latecki (2017). Clustering aggregation, also known as consensus clustering or clustering ensemble, aims to find a single superior clustering from a number of input clusterings obtained by different algorithms with different parameters. I formulate clustering aggregation as a special instance of the maximum-weight independent set (MWIS) problem. For a given data set, an attributed graph is constructed from the union of the input clusterings. The vertices, which represent the distinct clusters, are weighted by an internal index measuring both cohesion and separation. The edges connect the vertices whose corresponding clusters overlap. Intuitively, an optimal aggregated clustering can be obtained by selecting an optimal subset of non-overlapping clusters partitioning the data set together. I formalize this intuition as the MWIS problem on the attributed graph, i.e., finding the heaviest subset of mutually non-adjacent vertices. This MWIS problem exhibits a special structure. Since the clusters of each input clustering form a partition of the dataset, the vertices corresponding to each clustering form a maximal independent set (MIS) in the attributed graph. I propose a variant of simulated annealing method that takes advantage of this special structure. My algorithm starts from each MIS, which is close to a distinct local optimum of the MWIS problem, and utilizes a local search heuristic to explore its neighborhood in order to find the MWIS. Extensive experiments on many challenging data sets show that both my algorithm for the maximum-weight independent set problem and my approach to the application of clustering aggregation achieve good performance. This work was published in our NIPS 2012 paper Li & Latecki (2012). Some new results were published in our IJCAI 2017 paper Fan et al. (2017).
Temple University--Theses
APA, Harvard, Vancouver, ISO, and other styles
3

Canzar, Stefan. "Lagrangian Relaxation - Solving NP-hard Problems in Computational Biology via Combinatorial Optimization." Phd thesis, Université Henri Poincaré - Nancy I, 2008. http://tel.archives-ouvertes.fr/tel-00388521.

Full text
Abstract:
This thesis is devoted to two $\mathcal{NP}$-complete combinatorial optimization problems arising in computational biology, the well-studied \emph{multiple sequence alignment} problem and the new formulated \emph{interval constraint coloring} problem. It shows that advanced mathematical programming techniques are capable of solving large scale real-world instances from biology to optimality. Furthermore, it reveals alternative methods that provide approximate solutions. In the first part of the thesis, we present a \emph{Lagrangian relaxation} approach for the multiple sequence alignment (MSA) problem. The multiple alignment is one common mathematical abstraction of the comparison of multiple biological sequences, like DNA, RNA, or protein sequences. If the weight of a multiple alignment is measured by the sum of the projected pairwise weights of all pairs of sequences in the alignment, then finding a multiple alignment of maximum weight is $\mathcal{NP}$-complete if the number of sequences is not fixed. The majority of the available tools for aligning multiple sequences implement heuristic algorithms; no current exact method is able to solve moderately large instances or instances involving sequences exhibiting a lower degree of similarity. We present a branch-and-bound (B\&B) algorithm for the MSA problem.\ignore{the multiple sequence alignment problem.} We approximate the optimal integer solution in the nodes of the B\&B tree by a Lagrangian relaxation of an ILP formulation for MSA relative to an exponential large class of inequalities, that ensure that all pairwise alignments can be incorporated to a multiple alignment. By lifting these constraints prior to dualization the Lagrangian subproblem becomes an \emph{extended pairwise alignment} (EPA) problem: Compute the longest path in an acyclic graph, that is penalized a charge for entering ``obstacles''. We describe an efficient algorithm that solves the EPA problem repetitively to determine near-optimal \emph{Lagrangian multipliers} via subgradient optimization. The reformulation of the dualized constraints with respect to additionally introduced variables improves the convergence rate dramatically. We account for the exponential number of dualized constraints by starting with an empty \emph{constraint pool} in the first iteration to which we add cuts in each iteration, that are most violated by the convex combination of a small number of preceding Lagrangian solutions (including the current solution). In this \emph{relax-and-cut} scheme, only inequalities from the constraint pool are dualized. The interval constraint coloring problem appears in the interpretation of experimental data in biochemistry. Monitoring hydrogen-deuterium exchange rates via mass spectroscopy is a method used to obtain information about protein tertiary structure. The output of these experiments provides aggregate data about the exchange rate of residues in overlapping fragments of the protein backbone. These fragments must be re-assembled in order to obtain a global picture of the protein structure. The interval constraint coloring problem is the mathematical abstraction of this re-assembly process. The objective of the interval constraint coloring problem is to assign a color (exchange rate) to a set of integers (protein residues) such that a set of constraints is satisfied. Each constraint is made up of a closed interval (protein fragment) and requirements on the number of elements in the interval that belong to each color class (exchange rates observed in the experiments). We introduce a polyhedral description of the interval constraint coloring problem, which serves as a basis to attack the problem by integer linear programming (ILP) methods and tools, which perform well in practice. Since the goal is to provide biochemists with all possible candidate solutions, we combine related solutions to equivalence classes in an improved ILP formulation in order to reduce the running time of our enumeration algorithm. Moreover, we establish the polynomial-time solvability of the two-color case by the integrality of the linear programming relaxation polytope $\mathcal{P}$, and also present a combinatorial polynomial-time algorithm for this case. We apply this algorithm as a subroutine to approximate solutions to instances with arbitrary but fixed number of colors and achieve an order of magnitude improvement in running time over the (exact) ILP approach. We show that the problem is $\mathcal{NP}$-complete for arbitrary number of colors, and we provide algorithms that, given an instance with $\mathcal{P}\neq\emptyset$, find a coloring that satisfies all the coloring requirements within $\pm 1$ of the prescribed value. In light of our $\mathcal{NP}$-completeness result, this is essentially the best one can hope for. Our approach is based on polyhedral theory and randomized rounding techniques. In practice, data emanating from the experiments are noisy, which normally causes the instance to be infeasible, and, in some cases, even forces $\mathcal{P}$ to be empty. To deal with this problem, the objective of the ILP is to minimize the total sum of absolute deviations from the coloring requirements over all intervals. The combinatorial approach for the two-color case optimizes the same objective function. Furthermore, we use this combinatorial method to compute, in a Lagrangian way, a bound on the minimum total error, which is exploited in a branch-and-bound manner to determine all optimal colorings. Alternatively, we study a variant of the problem in which we want to maximize the number of requirements that are satisfied. We prove that this variant is $\mathcal{APX}$-hard even in the two-color case and thus does not admit a polynomial time approximation scheme (PTAS) unless $\mathcal{P}=\mathcal{NP}$. Therefore, we slightly (by a factor of $(1+\epsilon)$) relax the condition on when a requirement is satisfied and propose a \emph{quasi-polynomial time approximation scheme} (QPTAS) which finds a coloring that ``satisfies'' the requirements of as many intervals as possible.
APA, Harvard, Vancouver, ISO, and other styles
4

Awasthi, Abhishek [Verfasser], Oliver [Akademischer Betreuer] Kramer, and Jörg [Akademischer Betreuer] Lässig. "Optimization of NP-hard Scheduling Problems by Developing Timing Algorithms and Parallelization / Abhishek Awasthi ; Oliver Kramer, Jörg Lässig." Oldenburg : BIS der Universität Oldenburg, 2016. http://d-nb.info/1123210772/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Awasthi, Abhishek Verfasser], Oliver [Akademischer Betreuer] [Kramer, and Jörg [Akademischer Betreuer] Lässig. "Optimization of NP-hard Scheduling Problems by Developing Timing Algorithms and Parallelization / Abhishek Awasthi ; Oliver Kramer, Jörg Lässig." Oldenburg : BIS der Universität Oldenburg, 2016. http://d-nb.info/1123210772/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Fallgren, Mikael. "Optimization of Joint Cell, Channel and Power Allocation in Wireless Communication Networks." Doctoral thesis, KTH, Optimeringslära och systemteori, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-40274.

Full text
Abstract:
In this thesis we formulate joint cell, channel and power allocation problems within wireless communication networks. The objectives are to maximize the user with mini- mum data throughput (Shannon capacity) or to maximize the total system throughput, referred to as the max-min and max-sum problem respectively. The complexity is stud- ied together with proposed optimization- and heuristic-based approaches. In the first paper an overall joint cell, channel and power allocation max-min prob- lem is formulated. We show that the decision problem is NP-hard and that the op- timization problem is not approximable unless P is equal to NP, for instances with a sufficiently large number of channels. Further, it follows that for a feasible binary cell and channel allocation, the remaining continuous power allocation optimization problem is still not approximable unless P is equal to NP. In addition, it is shown that first-order optimality conditions give global optimum of the single channel power al- location optimization problem, although the problem is in general not convex. In the following two papers heuristics for solving the overall problem are proposed. In the second paper we consider the single channel problem with convex combinations of the max-min and the max-sum objective functions. This variable utility provides the ability of tuning the amount of fairness and total throughput. The third paper investi- gates the multiple channel setting. On a system with three cells, eight mobile users and three channels, we perform an exhaustive search over feasible cell and channel alloca- tions. The exhaustive search is then compared to the less computationally expensive heuristic approaches, presenting potential earnings to strive for. A conclusion is that several of the proposed heuristics perform very well. The final paper incorporates fixed relay stations into the overall joint cell, channel and power allocation max-min problem. The complexity is inherited from the formula- tion without relay stations. Further, we propose a heuristic channel allocation approach that shows good performance, compared to an optimization based approach, in numer- ical simulations on the relay setting.
Financial support by the Swedish Foundation for Strategic Research (SSF) QC 20110915
APA, Harvard, Vancouver, ISO, and other styles
7

Eberle, Stefan. "A Polynomial Algorithm for a NP-hard to solve Optimization Problem." Diss., lmu, 2009. http://nbn-resolving.de/urn:nbn:de:bvb:19-99427.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Pokorný, Pavel. "Využití optimalizace v řízení výroby." Master's thesis, Vysoké učení technické v Brně. Fakulta podnikatelská, 2008. http://www.nusl.cz/ntk/nusl-221771.

Full text
Abstract:
The Master’s thesis deals with production scheduling in an industrial company. It uses the means of artificial intelligence to develop an appropriate production schedule in a generalized Flow-shop Programming problem. This problem can be solved by application which is a result of this thesis and was prepaired with use of the software Matlab 7.1 and its Genetic Algorithm and Direct Search toolbox. There is a part devoted to the use of advanced production systems (APS) and the concept of the operative production planning in praxis as well. The thesis pays attention to various optimization models in production scheduling and supply chain management too.
APA, Harvard, Vancouver, ISO, and other styles
9

Sultanova, Nargiz. "A class of Increasing Positively Homogeneous functions for which global optimization problem is NP-hard." University of Ballarat, 2009. http://archimedes.ballarat.edu.au:8080/vital/access/HandleResolver/1959.17/16160.

Full text
Abstract:
It is well known that global optimization problems are, generally speaking, computationally infeasible, that is solving them would require an unreasonably large amount of time and/or space. In certain cases, for example, when objective functions and constraints are convex, it is possible to construct a feasible algorithm for solving global optimization problem successfully. Convexity, however, is not a phenomenon to be often expected in the applications. Nonconvex problems frequently arise in many industrial and scienti¯c areas. Therefore, it is only natural to try to replace convexity with some other structure at least for some classes of nonconvex optimization problems to render the global optimization problem feasible. A theory of abstract convexity has been developed as a result of the above considerations. Monotonic analysis, a branch of abstract convex analysis, is analogous in many ways to convex analysis, and sometimes is even simpler. It turned out that many problems of nonconvex optimization encountered in applications can be described in terms of monotonic functions. The analogies with convex analysis were considered to aid in solving some classes of nonconvex optimization problems. In this thesis we will focus on one of the elements of monotonic analysis - Increasing Positively Homogeneous functions of degree one or in short IPH functions. The aim of present research is to show that finding the solution and ²-approximation to the solution of the global optimization problem for IPH functions restricted to a unit simplex is an NP-hard problem. These results can be further extended to positively homogeneous functions of degree ´, ´ > 0.
Master of Mathematical Sciences (Research)
APA, Harvard, Vancouver, ISO, and other styles
10

Bonotto, Edison Luiz. "Otimização por Nuvem de Partículas e Busca Tabu para Problema da Diversidade Máxima." Universidade Federal da Paraíba, 2017. http://tede.biblioteca.ufpb.br:8080/handle/tede/9036.

Full text
Abstract:
Submitted by Maike Costa (maiksebas@gmail.com) on 2017-06-29T14:15:20Z No. of bitstreams: 1 arquivototal.pdf: 1397036 bytes, checksum: 303111e916d8c9feca61ed32762bf54c (MD5)
Made available in DSpace on 2017-06-29T14:15:20Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1397036 bytes, checksum: 303111e916d8c9feca61ed32762bf54c (MD5) Previous issue date: 2017-01-31
The Maximu m Diversity Problem (MDP) is a problem of combinatorial optimization area that aims to select a pre-set number of elements in a given set so that a sum of the differences between the selected elements are greater as possible. MDP belongs to the class of NP-Hard problems, that is, there is no known algorithm that solves in polynomial time accurately. Because they have a complexity of exponential order, require efficient heuristics to provide satisfactory results in acceptable time. However, heuristics do not guarantee the optimality of the solution found. This paper proposes a new hybrid approach for a resolution of the Maximum Diversity Problem and is based on the Particle Swarm Optimization (PSO) and Tabu Search (TS) metaheuristics, The algorithm is called PSO_TS. The use of PSO_TS achieves the best results for known instances testing in the literature, thus demonstrating be competitive with the best algorithms in terms of quality of the solutions.
O Problema da Diversidade Máxima (MDP) é um problema da área de Otimização Combinatória que tem por objetivo selecionar um número pré-estabelecido de elementos de um dado conjunto de maneira tal que a soma das diversidades entre os elementos selecionados seja a maior possível. O MDP pertence a classe de problemas NP-difícil, isto é, não existe algoritmo conhecido que o resolva de forma exata em tempo polinomial. Por apresentarem uma complexidade de ordem exponencial, exigem heurísticas eficientes que forneçam resultados satisfatórios em tempos aceitáveis. Entretanto, as heurísticas não garantem otimalidade da solução encontrada. Este trabalho propõe uma nova abordagem híbrida para a resolução do Problema da Diversidade Máxima e está baseada nas meta-heurísticas de Otimização por Nuvem de Partículas (PSO) e Busca Tabu(TS). O algoritmo foi denominado PSO_TS. Para a validação do método, os resultados encontrados são comparados com os melhores existentes na literatura.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "NP-Hard optimization problems"

1

Du, Ding-Zhu, Panos Pardalos, Xiaodong Hu, and Weili Wu. "NP-Hard Problems and Approximation Algorithms." In Introduction to Combinatorial Optimization, 199–257. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-10596-8_8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Woeginger, Gerhard J. "Exact Algorithms for NP-Hard Problems: A Survey." In Combinatorial Optimization — Eureka, You Shrink!, 185–207. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/3-540-36478-1_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

dos Santos Leal, Liara Aparecida, Dalcidio Moraes Claudio, Laira Vieira Toscani, and Paulo Blauth Menezes. "A Categorical Approach to NP-Hard Optimization Problems." In Computer Aided Systems Theory - EUROCAST 2003, 62–73. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-45210-2_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Cai, Liming, David Juedes, and Iyad Kanj. "The Inapproximability of Non NP-hard Optimization Problems." In Algorithms and Computation, 438–46. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/3-540-49381-6_46.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Sahai, Tuhin. "Dynamical Systems Theory and Algorithms for NP-hard Problems." In Advances in Dynamics, Optimization and Computation, 183–206. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-51264-4_8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Håstad, J. "Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?" In Automata, Languages and Programming, 235. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-45022-x_20.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Cohen, Aviad, Alexander Nadel, and Vadim Ryvchin. "Local Search with a SAT Oracle for Combinatorial Optimization." In Tools and Algorithms for the Construction and Analysis of Systems, 87–104. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-72013-1_5.

Full text
Abstract:
AbstractNP-hard combinatorial optimization problems are pivotal in science and business. There exists a variety of approaches for solving such problems, but for problems with complex constraints and objective functions, local search algorithms scale the best. Such algorithms usually assume that finding a non-optimal solution with no other requirements is easy. However, what if it is NP-hard? In such case, a SAT solver can be used for finding the initial solution, but how can one continue solving the optimization problem? We offer a generic methodology, called Local Search with SAT Oracle (), to solve such problems. facilitates implementation of advanced local search methods, such as variable neighbourhood search, hill climbing and iterated local search, while using a SAT solver as an oracle. We have successfully applied our approach to solve a critical industrial problem of cell placement and productized our solution at Intel.
APA, Harvard, Vancouver, ISO, and other styles
8

Uma, R. N., and Joel Wein. "On the Relationship Between Combinatorial and LP-Based Approaches to NP-Hard Scheduling Problems." In Integer Programming and Combinatorial Optimization, 394–408. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/3-540-69346-7_30.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Karpinski, Marek. "Polynomial time approximation schemes for some dense instances of NP-hard optimization problems." In Randomization and Approximation Techniques in Computer Science, 1–14. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. http://dx.doi.org/10.1007/3-540-63248-4_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Gupta, Moha, Puneet Garg, and Prerna Agarwal. "Ant Colony Optimization Technique in Soft Computational Data Research for NP-Hard Problems." In Artificial Intelligence for a Sustainable Industry 4.0, 197–211. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-77070-9_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "NP-Hard optimization problems"

1

Murthy, Garimella Rama. "Optimization of Quadratic Forms: NP Hard Problems: Neural Networks." In 2013 International Symposium on Computational and Business Intelligence (ISCBI). IEEE, 2013. http://dx.doi.org/10.1109/iscbi.2013.51.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Abdelhafiez, Ehab A., and Fahd A. Alturki. "A new optimization algorithm for solving NP-hard problems." In 2010 2nd International Conference on Mechanical and Electrical Technology (ICMET). IEEE, 2010. http://dx.doi.org/10.1109/icmet.2010.5598491.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Weissenberg, Julien, Hayko Riemenschneider, Ralf Dragon, and Luc Van Gool. "Dilemma First Search for effortless optimization of NP-hard problems." In 2016 23rd International Conference on Pattern Recognition (ICPR). IEEE, 2016. http://dx.doi.org/10.1109/icpr.2016.7900285.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Babicz, Dora, Attila Tihanyi, Miklos Koller, Csaba Rekeczky, and Andras Horvath. "Simulation of an Analogue Circuit Solving NP-Hard Optimization Problems." In 2019 IEEE International Symposium on Circuits and Systems (ISCAS). IEEE, 2019. http://dx.doi.org/10.1109/iscas.2019.8702694.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Shafransky, Yakov M., T.-C. Edwin Cheng, and C.-T. Daniel Ng. "An approach for proving the NP-hardness of optimization problems with hard computable objectives." In Workshop on dynamic scheduling problems. Polish Mathematical Society, 2016. http://dx.doi.org/10.14708/isbn.978-83-937220-7-5p75-78.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Savsani, Vimal, Poonam Savsani, and Prashant Arya. "Effect of Applying Advanced Optimization Techniques for the One-Dimensional Cutting Stock Problem." In ASME 2014 International Mechanical Engineering Congress and Exposition. American Society of Mechanical Engineers, 2014. http://dx.doi.org/10.1115/imece2014-36095.

Full text
Abstract:
The one-dimensional cutting stock problem is a linear optimization problem that is categorized as NP-Hard. This problem has a large number of applications in a number of different industries. Though a number of traditional methods have been applied to solve this problem, these methods are not as effective as advanced optimization techniques to find the global optimum of NP-Hard problems. In this paper, a combination of three such advanced methods has been used to solve the Cutting Stock Problem: the firefly algorithm (FFA), the bat algorithm (BA) and the teaching-learning based optimization (TLBO). The results of provided by these algorithms are compared on the basis of the optimality of the solution and for three individual case studies as well as by the convergence of the algorithms. It was found that the teaching-learning based optimization technique performed well in both the optimality as well as the convergence.
APA, Harvard, Vancouver, ISO, and other styles
7

Zhu, Weihang, James Curry, Anjali Mishra, and Victor Zaloom. "Sequence Dependent Parallel Machine Scheduling Using Parallel Ant Colony Optimization With Graphics Hardware Acceleration." In ASME 2009 International Manufacturing Science and Engineering Conference. ASMEDC, 2009. http://dx.doi.org/10.1115/msec2009-84145.

Full text
Abstract:
This paper studies the effectiveness of using parallel Ant Colony Optimization for sequence dependent parallel machine scheduling on a Graphics Processing Unit (GPU) hardware platform. Parallel machine scheduling is a traditional NP-hard combinatorial optimization problem. In this research, a hybrid ant colony optimization method that combines the ‘Apparent Tardiness Cost with Setups’ (ATCS) dispatching rule with massive ants is proposed to solve the parallel machine scheduling problem quickly and efficiently. The computational results demonstrate that the proposed method is effective and solve the problems order of magnitude faster with a GPU accelerated implementation.
APA, Harvard, Vancouver, ISO, and other styles
8

Biswas, Arpan, and Christopher Hoyle. "A Literature Review: Solving Constrained Non-Linear Bi-Level Optimization Problems With Classical Methods." In ASME 2019 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2019. http://dx.doi.org/10.1115/detc2019-97192.

Full text
Abstract:
Abstract Bi-level optimization is an emerging scope of research which consists of two optimization problems, where the lower-level optimization problem is nested into the upper-level problem as a constraint. Bi-level programming has gained much attention recently for practical applications. Bi-level Programming Problems (BLPP) can be solved with classical and heuristic optimization methods. However, applying heuristic methods, though easier to formulate for realistic complex design, are likely to be too computationally expensive for solving bi-level problems, especially when the problem has high function evaluation cost associated with handling large number of constraint functions. Thus, classical approaches are investigated in this paper. As we present, there appears to be no universally best classical method for solving any kind of NP-hard BLPP problem in terms of accuracy to finding true optimal solutions and minimal computational costs. This could cause a dilemma to the researcher in choosing an appropriate classical approach to solve a BLPP in different domains and levels of complexities. Therefore, this motivates us to provide a detailed literature review and a comparative study of the work done to date on applying different classical approaches in solving constrained non-linear, bi-level optimization problems considering continuous design variables and no discontinuity in functions.
APA, Harvard, Vancouver, ISO, and other styles
9

Quan, Ning, and Harrison Kim. "A Tight Upper Bound for Grid-Based Wind Farm Layout Optimization." In ASME 2016 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/detc2016-59712.

Full text
Abstract:
This paper uses the method developed by Billionnet et al. (1999) to obtain tight upper bounds on the optimal values of mixed integer linear programming (MILP) formulations in grid-based wind farm layout optimization. The MILP formulations in grid-based wind farm layout optimization can be seen as linearized versions of the 0-1 quadratic knapsack problem (QKP) in combinatorial optimization. The QKP is NP-hard, which means the MILP formulations remain difficult problems to solve, especially for large problems with grid sizes of more than 500 points. The upper bound method proposed by Billionnet et al. is particularly well-suited for grid-based wind farm layout optimization problems, and was able to provide tight optimality gaps for a range of numerical experiments with up to 1296 grid points. The results of the numerical experiments also suggest that the greedy algorithm is a promising solution method for large MILP formulations in grid-based layout optimization that cannot be solved using standard branch and bound solvers.
APA, Harvard, Vancouver, ISO, and other styles
10

Neumann, Frank, and Carsten Witt. "Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/665.

Full text
Abstract:
Chance constrained optimization problems allow to model problems where constraints involving stochastic components should only be violated with a small probability. Evolutionary algorithms have been applied to this scenario and shown to achieve high quality results. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for chance constrained optimization. We study the scenario of stochastic components that are independent and Normally distributed. Considering the simple single-objective (1+1)~EA, we show that imposing an additional uniform constraint already leads to local optima for very restricted scenarios and an exponential optimization time. We therefore introduce a multi-objective formulation of the problem which trades off the expected cost and its variance. We show that multi-objective evolutionary algorithms are highly effective when using this formulation and obtain a set of solutions that contains an optimal solution for any possible confidence level imposed on the constraint. Furthermore, we prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem. Experimental investigations on instances of the NP-hard stochastic minimum weight dominating set problem confirm the benefit of the multi-objective approach in practice.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'NP-Hard optimization problems' for particular source types:
Journal articles
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!

To the bibliography