Skip to main content
23 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 ...
prubin's user avatar
  • 39.3k
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 ...
Philipp Christophel's user avatar
17 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 - ...
dhasson's user avatar
  • 1,687
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 ...
prubin's user avatar
  • 39.3k
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 ...
prubin's user avatar
  • 39.3k
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 ...
Antarctica's user avatar
  • 2,917
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)...
EhsanK's user avatar
  • 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 ...
A.Omidi's user avatar
  • 8,950
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 ...
Mark L. Stone's user avatar
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 ...
Richard's user avatar
  • 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, ...
PeterD's user avatar
  • 1,636
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 ...
Alberto Franzin's user avatar
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 ...
Geoffrey De Smet's user avatar
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 ...
Hexaly's user avatar
  • 2,986
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. ...
Joris Kinable's user avatar
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. ...
PSLP's user avatar
  • 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 ...
Nikos Kazazakis's user avatar
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, ...
prubin's user avatar
  • 39.3k
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.
Geoffrey De Smet's user avatar
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 ...
PeterBe's user avatar
  • 1,652
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 ...
Sune's user avatar
  • 6,552
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 ...
Joris Kinable's user avatar
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 ...
LarrySnyder610's user avatar
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 (...
Sune's user avatar
  • 6,552
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 ...
Juan Pablo Mesa's user avatar
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 ...
worldsmithhelper's user avatar
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 ...
fontanf's user avatar
  • 2,623
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 ...
J Fabian Meier's user avatar
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.
mrBen's user avatar
  • 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 ...
EhsanK's user avatar
  • 5,864

Only top scored, non community-wiki answers of a minimum length are eligible