Questions tagged [heuristics]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers

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 "...
Peter's user avatar
  • 109
0 votes
1 answer

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. ...
Tianxun Zhou's user avatar
0 votes
2 answers

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 ...
dineshdileep's user avatar
1 vote
2 answers

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 ...
Siavash R's user avatar
1 vote
1 answer

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 ...
Libor's user avatar
  • 393
5 votes
1 answer

Striking examples of success of local search algorithms

In N queens problem, trying to find solution by backtracking encounters difficulties quite fast (even for SWI-Prolog,
John Donn's user avatar
  • 223
0 votes
1 answer

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 ...
Cror2014's user avatar
  • 101
0 votes
2 answers

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 ...
megamind's user avatar
10 votes
3 answers

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 ...
Prokop Hapala's user avatar
0 votes
1 answer

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 ...
Hani Gotc's user avatar
  • 175
0 votes
1 answer

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 ...
Ayman Elmasry's user avatar
4 votes
1 answer

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 ...
user1387's user avatar
4 votes
1 answer

Expectation-Maximization and local maxima

The E-M algorithm does not guarantee convergence to global maxima. Following Applet shows this nicely: Is it possible to generate data set, that guarantees reaching ...
Urank's user avatar
  • 81
3 votes
2 answers

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 ...
Nico Liu's user avatar
  • 131
10 votes
2 answers

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 ...
Tim's user avatar
  • 1,281
7 votes
2 answers

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-...
Paul's user avatar
  • 12k