| Heuristics | Solution methods are usually specified/adapted for the problem (Aim is to generate a good solution that is feasible with a reasonable computation time)
The quality of the solution is not guaranteed to be globally optimal, might generate local optimum.
Often based on the problem and necessarily on the mathematical model
Useful in difficult combinatorial optimization problems and in finding feasible solutions for pessimistic bounds (Bra vid problem där många faktorer spelar roll och för att hitta lower och upper bounds, pessimistisk i detta fall betyder att bounds troligtvis inte stämmer, alltså kanske inte går att uppnå så bra lösning) |
| Why and when to use heuristic | Whenever optimization problems have long computation times and requires huge amount of memory.
The input data includes uncertainties.
Easier for readers with little background to understand rather than having a mathematical model |
| Different types of heuristics | Constructive heuristics, Local search methods, Metaheuristics, Approximation algorithms |
| Constructive heuristics.. | Successfully constructs a feasible solution
Often used for first time solutions
A common type is “greedy algorithm”
Starts with no prior solutions and finishes when feasible solution is found
Called greedy because it only looks for what’s best in the next step
Examples for TSP: Nearest neighbor, Nearest insertion, Nearest merger |
| Local search methods.. | Starts with a feasible solution and iteratively improves the solution
A common type is “nearest neighbour” |
| Metaheuristics.. | Heuristics with built in methods to prevent them from getting stuck at local optima
A common type is “Tabu-search” |
| Approximation algorithms.. | Gives a guarantee on how far the objective function value is from the optimal value
Often bad in practical cases but interesting for the theoretical |
| Nearest Neighbor.. | 1. Start in any node.
2. Go to nearest neighboring node that is not included.
3. Continue until all nodes are included. |
| Nearest Insertion.. | 1. Start in any node, creating a subtour T
2. Find the node k closest to any node in T
3. Put k in the best place in the tour T
4. Continue until all nodes are included |
| Local search in convex problem.. | We can find Global optimum if we design an intelligent search method |
| Local search in non-convex problem.. | We will most likely get stuck in a local optima
Solution will depend on the starting point and Neighborhood definition |
| Branch & Bound is a.. | Solution strategy for integer programming problems where the idea is to split the feasible region into smaller regions and solve a relaxed problem in each subproblem. |
| Branch & Bound (trädsökning) steps? | 1. First step is to solve the relaxed subproblem
2. Branch on which variable
3. ≥ or ≤
4. Depth or breadth first |
