10 votes
Accepted

Is there an open-source equivalent to LocalSolver?

The simple answer is no. While I haven't used LocalSolver myself, I sell a solver that solves similar types of problems (Octeract Engine) so I get asked this type of question a lot for my own solver. ...
Nikos Kazazakis's user avatar
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,461
8 votes

Paper suggestions on local search algorithms

Below are some papers from LocalSolver team members that detail local search approaches for diverse combinatorial optimization problems, with some focus on low-level implementation details: T. Benoist,...
Hexaly's user avatar
  • 2,936
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

Is there an open-source equivalent to LocalSolver?

To our knowledge, there is no equivalent of Hexaly (ex LocalSolver) in open source. More generally, there is no equivalent of Hexaly in the market. Hexaly's uniqueness, and thus innovation, comes from ...
Hexaly's user avatar
  • 2,936
7 votes

Can Local Search Operators be formulated as a Mixed Integer Program?

What you describe is a special case of Large Neighborhood Search. Large Neighborhood search is an optimization method that consists in destroying a part of a solution and recreating it with a ...
fontanf's user avatar
  • 2,495
6 votes
Accepted

Learning local search operator selection

In addition to the hyperheuristics mentioned by batwing, you can look for the broader topic of (automatic) algorithm selection and configuration. Generally speaking, algorithm selection is the task of ...
Alberto Franzin's user avatar
5 votes

Learning local search operator selection

I think you may be interested in the topic of hyper-heuristics. Very loosely, given a bunch of local search operators for a problem, the idea is to combine those local search operators to form a short ...
batwing's user avatar
  • 1,458
4 votes

When solving many MILPs how to assign CPU cores to solver instances?

So we know that MILP instances are independent and that the total throughput is to be maximized. In practice, increasing the number of threads used by a solver to solve a MILP instance could ...
rasul's user avatar
  • 2,140
4 votes

Increase the dimension to ease the local search?

Redefining the solution space is a way to make local search heuristics perform better. This is useful for tightly constrained problems where moving from one feasible solution to another is difficult. ...
Hexaly's user avatar
  • 2,936
4 votes

Paper suggestions on local search algorithms

This answer focuses on the "papers that go into the details of implementation on a given optimization problem" part of the question. In "Variable neighborhood search for the $p$-median&...
Sune's user avatar
  • 6,352
4 votes

Paper suggestions on local search algorithms

I'm not an expert in the field, but the paper An effective implementation of the Lin-Kernighan traveling salesman heuristic by Keld Helsgaun was mentioned in another question before.
Robert Schwarz's user avatar
4 votes
Accepted

PSO. Hyperparameter Optimization for Similar Problems

In general you are correct, but the extent to which you are depends heavily on your objective function (and set of constraints, if you have any). As you say, when the problem changes, the landscape ...
Alberto Franzin's user avatar
4 votes

Can Local Search Operators be formulated as a Mixed Integer Program?

I'm not aware of any work on modeling local search heuristics as MIPs. It is certainly possible to come up with a MIP model for each heuristic you mentioned. What is not clear is whether it is worth ...
prubin's user avatar
  • 37.9k
3 votes

Is there an open-source equivalent to LocalSolver?

You might want to try Gecode, although I have no idea whether it will do any better than OR-Tools. If you are not a C++ programmer, you can use MiniZinc to build the model and interface with Gecode. ...
prubin's user avatar
  • 37.9k
3 votes
Accepted

How to do Local search when using Greedy random heuristics for GAP

Shifts and swaps are already good neighborhoods for the Generalized Assignment Problems: Shift: move a task to another worker Swap: swap the workers of two tasks Another neighborhood found in some ...
fontanf's user avatar
  • 2,495
3 votes

How to implement a local search with different operators?

I suggest you take a look at Variable Neighborhood Search (VNS) method. The Wikipedia page has some useful pseudo codes. My answer to OP EDIT: First, I think there is no good or bad algorithm, it ...
Mostafa's user avatar
  • 2,086
3 votes

How to correct this scheduling algorithm?

I'm not sure there is a way to tweak your heuristic that will guarantee finding a feasible solution (assuming one exists). What you might try is a restart approach combined with a modification of your ...
prubin's user avatar
  • 37.9k
3 votes

On what kind of problems a local search may perform better than MIP / CP techniques?

Those that you can't completely explore the branch-and-bound tree within your time limit. 😉 Don't forget you can do local search and large neighbourhood search in a branch-and-bound tree: fix some ...
Edward Lam's user avatar
  • 1,235
3 votes

Paper suggestions on local search algorithms

Blot et al. (2018)1 did an extensive literature review on multi-objective LS algorithms. You may wish to take a look at Ishibuchi and Murata (2004)2 which focuses on issues in evolutionary algorithms. ...
TheSimpliFire's user avatar
  • 5,342
2 votes

Paper suggestions on local search algorithms

For what it's worth, here you can download our paper on Multithreaded Incremental Solving for Local Search (not to be confused with multi-walk solving (AKA multi-bet solving), multi-tentant solving or ...
Geoffrey De Smet's user avatar
2 votes

Learning local search operator selection

Elementary learning approaches to select local search operators dynamically - that is, during the search - work well in practice. Here is what we call "elementary learning approaches". Given ...
Hexaly's user avatar
  • 2,936
2 votes
Accepted

Question re Tabu Search

Your doubt is right: you should NOT go back to your best solution if the current solution is not in the tabu list. You should invert the if statement and see if the tabu search leads to better ...
PeterD's user avatar
  • 1,461
2 votes
Accepted

When solving many MILPs how to assign CPU cores to solver instances?

As far as I know, solution speed for solvers is typically a sublinear function of the number of threads/cores. This makes sense since parallel processing requires additional effort (CPU cycles) to ...
prubin's user avatar
  • 37.9k
2 votes

Book to learn metaheuristics

Two good (free) books are: Essentials of Metaheuristics: https://cs.gmu.edu/~sean/book/metaheuristics/ Clever Algorithms: https://github.com/clever-algorithms/CleverAlgorithms If you want to try ...
Enrique Gabriel Baquela's user avatar
1 vote
Accepted

What methods exist for tree search over a large complex state representation?

Here's a few ideas: Only store the full state in the leaf nodes. Remove it from the parent nodes once all their children are created. Only store the full state in the parent/internal nodes. Each ...
Brannon's user avatar
  • 892
1 vote

Increase the dimension to ease the local search?

In general, increasing the dimension of the neighbourhood of a local search can improve the final results, because a local optimum for a neighbourhood is not necessarily a local optimum for a ...
Alberto Franzin's user avatar
1 vote

Learning local search operator selection

This talk discusses several approaches to integrate machine learning in local search algorithms by identifying good solutions bad solutions promising neighborhoods through offline learning of ...
ktnr's user avatar
  • 491

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