Questions tagged [heuristics]

Referring to methods that produce good "approximate" solutions, particularly for np-hard, np-complete, or combinatorial optimization problems.

16 questions
Filter by
Sorted by
Tagged with
25 views

Do the class of Construction Heuristic that does or does not change previous decisions have a name?

I'm writing a paper where I am discussing different types of construction heuristics. One type does not change previous decisions when adding new elements to the solution. I'd call them "...
• 109
645 views

How to generate neighbors for simulated annealing

I am learning about simulated annealing algorithm and want to create a general purpose one for optimizing continuous functions. The problem I have is how to generate the neighbor points as candidates. ...
219 views

Is this a knapsack problem?

I have a set of $K$ keywords. Each of this keywords can have set of bids from $1\$,\dots,N\. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost ...
• 153
1 vote
1k views

GSA Search Algorithm in C++

Is there any version of GSA (Gravitational Search Algorithm)[1] implemented with C++ or even C#? What I found was implemented using MATLAB which is not good for me. [1] Rashedi, Esmat, Hossein ...
1 vote
62 views

Finding optimal point distance to get desired number of random points in an area

I have a random point generator which takes a distance $d$ and fills an area with points such that distance between any two points is no less that $d$: I need to control the number of points in the ...
• 393
259 views

Striking examples of success of local search algorithms

In N queens problem https://en.wikipedia.org/wiki/Eight_queens_puzzle, trying to find solution by backtracking encounters difficulties quite fast (even for SWI-Prolog, http://swish.swi-prolog.org/...
• 223
332 views

Comparing computational complexity of convex optimization and a heuristic algorithm

I am working on a resource allocation problem, which is convex and has several constraints, and I want to compare the computational complexity of the following algorithms. 1) The algorithm that uses ...
• 101
305 views

Statistical analysis of optimization algorithms

If we optimize some parameter using 4 optimization algorithms, 2 of which are population based (say A and B) and 2 trajectory methods (single point search)(say C and D); what statistical test can be ...
5k views

Sort of problems where SOR is faster than Gauss-Seidel?

Is there any simple rule of thumb to say if it is worth to do SOR instead of Gauss-Seidel? ( and possible way how to estimate realxation parameter $\omega$) I mean just by looking on the matrix, or ...
314 views

Find closest Point based on orientation and Euclidean distance

I have a set of points P1(x1,y1), P2(x2,y2), P3(x3,y3), P4(x4,y4), P5(x5,y5) in the Cartesian plane. I am trying to find the closest point to P1 based on the ...
• 175
76 views

Extension of research on optimisation to a relatively complex level [closed]

I'm doing research for academic credential on the use of metaheuristic optimisation of building envelopes/enclosures, focusing on the aspect of its thermal performance. The subject was handled with ...
191 views

What strategies one can use to keep maximum number of non attacking pieces on an $n \times n$ chess board? [closed]

What are the strategies one can use to keep maximum number of non attacking pieces (all pieces other than pawn) on an $n\times n$ board? It is like an $n$-queen problem but here instead of only queen ...
• 41
217 views

Expectation-Maximization and local maxima

The E-M algorithm does not guarantee convergence to global maxima. Following Applet shows this nicely: http://www.cs.cmu.edu/~alad/em/ Is it possible to generate data set, that guarantees reaching ...
• 81
387 views

How to prove that my problem is np-hard

For an assignment i need to program an application to schedule conversations. Something similar to speeddating or Pta meeting. The problem is that i know that this is hard to solve, but i dont know if ...
• 131
4k views

Meaning of (meta)heuristic methods

For optimization, from Wikipedia: In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard ...
• 1,281