22
votes
Combinatorial Optimization: Metaheuristics, CP, IP -- "versus" or "and"?
Here, in approximate order, are my criteria.
Do I need a provably optimal solution (which rules out metaheuristics, other than to generate an initial feasible solution)?
Is this something CPLEX can ...
- 37.8k
22
votes
Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?
The answer to the question is: No.
(Although one can debate what exactly is a "metaheuristic")
The "gold standard" for finding high quality feasible solutions for the TSP is the ...
- 3,168
16
votes
Accepted
Which Python package is suitable for multiobjective optimization
If you use packages like PyOMO, PuLP or pyOpt, you'd have to implement all the operations for multiobjective optimization - e.g. to find nondominated solutions or the different mutation operators - ...
- 1,667
16
votes
Accepted
Python vs. compiled languages in OR research using metaheuristics
Speaking as an occasional reviewer for journals, when I read a paper proposing a new heuristic or metaheuristic my first question is "does it work?", which is independent of the programming ...
- 37.8k
13
votes
Which approaches exist to solve a TSP?
I doubt there is a complete listing of every possible approach to TSPs. You can find a significant amount of information on Bill Cook's site. Bill Cook wrote what I believe many consider the ...
- 37.8k
12
votes
Good resources for solving techniques (Metaheuristics, MILP, CP etc)
You should take a look at a series of three courses at coursera :
Basic Modeling for Discrete Optimization
Solving Algorithms for Discrete Optimization
Advanced Modeling for Discrete Optimization
...
- 2,907
11
votes
Accepted
Online Education for OR and Developing Decision Support Systems
Check Coursera, edX, Udemy, or any other online courses (such as those of Stanford). For example:
Free: Discrete Optimization course on Coursera, covers column generation and an introduction to (meta)...
- 5,864
10
votes
How to implement a "generic" solver for scheduling problems?
As you mentioned about "scheduling/production planning problems", I refer it to manufacturing planning and detailed schedule. Also, I know that there are specific methods to solve other planning and ...
- 8,382
10
votes
Which Python package is suitable for multiobjective optimization
If @dbasson 's excellent answer is not what you're looking for, may I suggest the possibility of using multiobjective optimization capabilities in CPLEX or Gurobi (under Python)?
CPLEX
New ...
- 13.1k
10
votes
Accepted
Verifying optimality of heuristic solutions
Generally, the only way to prove that a given solution is optimal is to obtain a valid lower bound (assuming minimization) that matches the incumbent solution (with $\epsilon$ tolerance, to be ...
- 3,459
10
votes
Book to learn metaheuristics
The most famous book on metaheuristics is probably the Handbook of Metaheuristics:
Michel Gendreau and Jean-Yves Potvin. 2010. Handbook of Metaheuristics (2nd. ed.). Springer Publishing Company, ...
- 1,461
8
votes
Accepted
In Local Search, which reheating techniques have a good track record?
This is where automatic algorithm configuration and design comes to the rescue. In my experience, different combinations of strategies work equally fine, at least when combined with other components ...
- 1,058
8
votes
Are metaheuristics ever practical for continuous optimization?
I haven't seen any good use cases of metaheuristics for continuous variables optimization. That doesn't mean it's not possible, I just think it's not the right tool for the job. Particularly, all ...
- 4,707
8
votes
Do better construction heuristics increase the performance of improvement heuristics?
There are some proofs of the contrary: whatever the starting point, your local search can be stuck in solutions far away from the optimum. Here "local" means that each iteration must be done ...
- 2,925
8
votes
Which approaches exist to solve a TSP?
Some additional sources to help you answer your question:
Cook, W. "In pursuit of the traveling salesman: mathematics at the limits of computation. 2012."
Gutin, Gregory, and Abraham P. ...
- 3,396
7
votes
Integrating genetic algorithm (or other heuristic methods) with CPLEX
I am aware of two ways of combining a (meta-)heuristic with a solver (like cplex).
1) Warm start: use a heuristic to quickly find a good solution and give it to the solver as a starting solution. ...
- 2,401
7
votes
How to implement a "generic" solver for scheduling problems?
Before you even start worrying about algorithms, you need to figure out the solver's architecture. You can do so by posing and answering questions such as the ones I ask below. The answers will be a ...
- 11.9k
7
votes
How to implement a "generic" solver for scheduling problems?
The "generic" aspect of the solver might just mean that management has, um, inflated expectations. That said, and focusing on the use of metaheuristics, I'll throw out a few ideas.
Where possible, ...
- 37.8k
7
votes
Good resources for solving techniques (Metaheuristics, MILP, CP etc)
I really liked the "Discrete Optimization" course at coursera - not sure if they still run it.
- 4,707
7
votes
Difference between exploration and exploitation in Simulated Annealing algorithm
I personally see it as follows. In simulated annealing the likelihood of choosing a solution from the neighborhood is quite high at the beginning. This phase could be regarded as exploration as the ...
- 1,632
7
votes
What is good introductory literature on (meta)heuristics?
This will be opinion based, but I personally like "Handbook of meta heuristics" edited by Michel Gendreau and Jean-Yves Potvin. https://link.springer.com/book/10.1007/978-1-4419-1665-5
There ...
- 6,352
7
votes
Calculate the average of the objective function values resulting from metaheuristics after a defined number of executions
There are multiple ways you can analyze and compare the results of heuristics/randomized search procedures.
Report the average, best and worst
Report the average, and standard deviation
Graphically ...
- 3,396
7
votes
Random solution for capacitated vehcle routing problem (cvrp)
"Random solution" means the decision variables are chosen randomly. It does not usually mean ignoring feasibility constraints. So, in the case of CVRP, it would mean choosing the cities for ...
- 13.1k
7
votes
Random solution for capacitated vehcle routing problem (cvrp)
Usually such statements mean that you should device a construction heuristic, which relies on some level of randomness. That is, if you run your construction procedure twice you should not (...
- 6,352
7
votes
Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?
Take a look at the Concorde https://www.math.uwaterloo.ca/tsp/concorde.html.
If it's a TSP problem, not a variant, Concorde can solve it and it is a beast.
When you say "versions of the ...
7
votes
Does this game that I invented correspond to a valid optimization problem?
Your game does not fall into classical discrete optimization as the objective is unknown. As soon as the blackbox function is fully know (or one supposes a model with fixed parameters for it) it would ...
- 3,975
7
votes
Accepted
Metaheuristics vs Column generation for VRP
Please note that it is difficult to say something generic about all VRP variants. There are certainly a lot of counter examples of what I wrote below.
First, column generation is mainly used within ...
- 2,495
7
votes
Python vs. compiled languages in OR research using metaheuristics
I think this is a false dichotomy.
Surely, C++ is the classical language for fast programs (besides FORTRAN, maybe).
But nowadays, Java is very fast as well. Julia is also an option, fast and aimed ...
- 1,110
6
votes
Good resources for solving techniques (Metaheuristics, MILP, CP etc)
For a basic introduction to OR, you can take a look at the open course on Caseine. There is many exercises, some that make you use CPLEX.
- 521
6
votes
Good resources for solving techniques (Metaheuristics, MILP, CP etc)
I'm bringing my comment here:
In case you are looking for some code to see how these types of problems are implemented, check out this repo. I created a small production planning example for the sake ...
- 5,864
Only top scored, non community-wiki answers of a minimum length are eligible