# Tag Info

21

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 handle (since I have a license for CPLEX and I'm familiar with it)? If CPLEX can handle it, should I consider a heuristic, metaheuristic or constraint solver to ...

12

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 They use MiniZinc as modeling language.

11

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)heuristic Optimization with Metaheuristics in Python on Udemy Lectures of Introduction to Meta-heuristics Artificial Intelligence: Reinforcement Learning in ...

9

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 - that could take some time. An alternative is using DEAP for that, it's a Python framework for evolutionary algorithm and they have NSGA-II implemented. It's quite ...

8

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 that have a stronger impact in the algorithm (see my work at [1]); it could even be that in certain cases reheating is not necessary. However, following the ...

8

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 forms of Local Search (Tabu Search, Late Acceptance, Simulated Annealing) with real continuous variables feel like using a hammer on a screw. That being said, ...

8

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 function of the goals of the project, the help & know-how of the people who employ you and, crucially, what you can realistically do in 6 months. Keep in ...

8

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 scheduling problems. (E.g. vehicle routing problem variants). Planning and Scheduling, specifically in the real application, will need to survey from some ...

8

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 multiobjective optimization features in CPLEX V12.9.0 Optimization problems with multiple linear objective functions can be specified in CPLEX. To solve them, CPLEX ...

7

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. This can help pruning the branch and bound tree considerably. (e.g. "Designing sustainable energy regions using genetic algorithms and location-allocation ...

7

I really liked the "Discrete Optimization" course at coursera - not sure if they still run it.

7

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 algorithm usually takes relatively big steps in the solution space. Later the likelihood decreases and by doing so the algorithm stays within a certain region of ...

7

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 is also "Metaheuristics for Business Analytics" if you are teaching business school students. https://www.springer.com/gp/book/9783319681177

7

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 represent the results as a boxplot. When computing the average, you need to be careful when there are instances that could not be solved by the heuristic. This ...

7

"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 a given route, as well as their sequence on the route, randomly. There are various ways to deal with the capacity constraint -- for example, if the next ...

7

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 (necessarily) get the same solution. I would in most cases, if not stated explicitly, expect the solution to be feasible to the problem (in your case it should probably ...

6

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.

6

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 of tutorial and solved it by 2 commercial solvers (Gurobi and CPLEX) and PuLP as the open-source package. I used a simple script and then a more robust (for ...

6

Personally I use them all the time, regardless of variable type, typically for low-dimensional (<= 100 variables) black-box optimization problems of unknown structure where I want an approximate solution quickly. For example, this solver uses a GA and accepts continuous and discrete variables: https://support.sas.com/documentation/onlinedoc/or/132/...

6

For heuristics you can take a look at this course. Also the book "How to solve it : Modern heuristics" by Zbigniew Michalewicz and David B. Fogel. Reinforcement Learning has similiarities with approximate dynamic programming, these video lectures by D. P. Bertsekas may be useful.

6

Heuristics are useful to solve continuous optimization problems, in particular: Large-scale problems, whatever their nature. Because even if the problem has nice properties (convexity, smoothness), its large scale may prevent the nice algorithms (for example, Augmented Lagrangian or Interior Point methods) to converge to quality solutions in reasonable ...

6

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, use a (well-crafted) third-party library to do the actual metaheuristic computations, rather than writing your own. It's likely to be faster than what you would ...

6

Generally speaking the most generic scheduling problem is the RCPSP. However, even that tends to need extensions for many practical problems. See Hartmann, Sönke, and Dirk Briskorn. "A survey of variants and extensions of the resource-constrained project scheduling problem." European Journal of operational research 207.1 (2010): 1-14. for a structured ...

6

Here is a somewhat greedy heuristic. First, to simplify notation a bit, let $$f_{c}(x)=\frac{1}{d_c}\sum_{n=1}^N B_{n,c}x_n\, \forall c.$$ So we want to maximize $$t=\min_c f_c(x)$$ subject to $$\sum_n x_n = M.\quad (1)$$ Now start with some arbitrary (let's say randomly generated) $x$ satisfying (1). Calculate all the $f_c(x)$, and for each $n$ calculate ...

6

Unlike the problem from the linked post, the objective here is “flat” at the initial solution in the sense that increasing some $x_n$ by 1 unit will not change the objective value, which is initially 0. The LP rounding approaches still apply if you linearize the $\min_c$, which you can do by introducing $t$ with $t\le s_c/d_c$.

6

Those two are also called Diversification (Exploration) and Intensification (Exploitation). In SA, Diversification relates to the larger values of the probability of accepting an inferior neighbor solution, while Intensification relates to the smaller values. Since the probability is dependent to the difference between the objective of the current and ...

6

There is no problem in starting your ALNS with an infeasible (what you call "incomplete") solution. ALNS consists of destroying a part of the solution and then repairing it, at each iteration. Generally, destroying is done by removing a number of tours in the incumbent solution. But you can adapt the method by selecting a number of tours plus some ...

6

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 in polynomial time. Check the seminal paper "On the Complexity of Local Search for the Traveling Salesman Problem" by Papadimitriou and Steiglitz on ...

5

Institute of Applied Optimization Metaheuristic Optimization - prerequisite: Java programming Coursera Practical Reinforcement Learning - related

5

Introduce binary variables $y_n$ and constraints \begin{align} x_n &\le M y_n &&\text{for all $n$}\\ \sum_n y_n &\le 3 \end{align}

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