Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [heuristics]

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

0
votes
1answer
61 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 ...
1
vote
2answers
740 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
1answer
41 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 ...
5
votes
1answer
150 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/...
0
votes
1answer
262 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 ...
0
votes
2answers
173 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 ...
8
votes
3answers
3k 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 ...
0
votes
1answer
168 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 ...
0
votes
1answer
74 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 ...
4
votes
1answer
183 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 ...
4
votes
1answer
161 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 ...
3
votes
2answers
180 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 ...
10
votes
2answers
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 ...
5
votes
2answers
447 views

What heuristics can be used to minimize the asymptotic matrix bandwidth of a 5-point Laplacian discretization?

I can see that there are multiple heuristics to achieve a matrix with minimum bandwidth. As heuristics, they can't guarantee an optimal solution in polynomial time (after all, the problem is NP-...