DM811 – Heuristics for Combinatorial Optimization

Search Methods

• • Complete Tree Search

  • Incomplete Tree Search

    • greedy best-first

    • search

    • Limited Discrepancy Search

  • Local Search

  • Random Picking

  • Random Walk

  • Iterative Improvement (First, Best)

  • Very Large Scale Neighborhood Techniques

    • Variable Depth Search,

    • Ejection Chains,

    • Dynasearch,

    • Assignment Neighborhoods

    • Cyclic Exchange Neighborhoods

  • Variable Neighborhood Descent/Search (and extensions)

  • Attributed Based Hill Climber

  • Walk SAT & Min-conflict Heuristics

  • Randomized Iterative Improvement

  • Novelty

  • Probabilistic Iterative Improvement (Metropolis Algorithm)

Combinatorial Problems

• Routing (cyclic permutations)

  • Traveling Salesman Problem (TSP)

  • Capacited Vehicle Routing

• Assignment

  • Propositional Satisfiability (SAT and MAX-SAT)

  • Constraint Satisfaction Problem (CSP and MAX-CSP)

  • Vertex Graph Coloring Problem (GCP)

  • Bin Packing and 2-Dimensional Bin Packing

  • p-median

  • Graph Partitioning

  • Generalized Assignment

• Scheduling (linear permutations)

  • Quadratic Assignment Problem (QAP)

  • Linear Ordering – Feedback Arc Set

  • The Single Machine Total Weighted Tardiness Problem (SMTWTP)

• Subsets

  • Max Independent Set

  • Set Covering, Packing, Partitioning (related Combinatorial Auctions and Crew Scheduling)

Experimental Analysis and Parameter Tuning

• Performance Indicators

• Data Visualization: Histograms, Empirical Cumulative Distribution Functions, Boxplots, Scatterplots

• Experiment Organization

• Algorithm comparison: F-Race

• Effective coding