# Tag Info

9

This is a minimum cost flow problem in the bipartite graph $G=(V,A)$ with $V=N_U \cup N_B$. Add a source node and link it to each vertex $v\in N_U$. On each of these arcs, constrain the flow to be in the range $[a_{min},a_{max}]$. Note that if $a_{min} > |N_B|$ the problem is infeasible. Likewise with a sink node, that you link to each vertex $v \in N_B$, ...

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

6

The best paper we ever read about the implementation of heuristics for the TSP is "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic" by Keld Helsgaun. This 70-page report is really a masterpiece in the field. You can find more details here about Helgaun's research on TSP, and here for extensions to VRP. You can also ...

5

To fix a variable use x.fx(i) = 1. To unfix: x.lo(i) = 0; x.up(i) = 1;. To relax an integer/binary variable you can use: x.prior(i)=INF; Documentation of this can be found at the obvious place: https://www.gams.com/latest/docs/UG_Variables.html. Here is an example of how to use this.

4

There is no magic. Considering that the algorithm is carefully designed, it is a matter of solution quality versus running time. If each run needs a lot of time to converge, running it 30 times could be too long for practical use. If the algorithm converges very fast, in milliseconds, why not running it hundreds of times. Now, if an iterative algorithm has ...

4

Regarding the last question (how to link C++ and CPLEX), CPLEX has a C++ API that is thoroughly documented in the user manual. They also provide quite a few C++ examples (source code).

3

The book [burke2005search] provides a good starting points for different heuristics algorithms. Identify the techniques you need first. Most likely, you can find a reliable open source package. [burke2005search] Burke, E. K., & Kendall, G. (2005). Search methodologies (pp. 1-17). Springer Science+ Business Media, Incorporated.

3

If you are looking for an introductory textbook, I think "Metaheuristics: From Design to Implementation" by El-Ghazali Talbi is a very good option as it covers various design ideas and issues as well as different metaheuristics.

3

You can solve this as a graph coloring problem in a graph with one node per original box and an edge between each pair of nodes for which the corresponding boxes cannot be merged (either because they have different labels or because merging would conflict with a box of a different label). Each color corresponds to a new bounding box, adjacent nodes cannot be ...

2

Assuming the random seed is different every time, genetic algorithms (and by extension stochastic algorithms) are non-deterministic by nature, which is why they need to be run many times until we get "lucky". There is no meaningful "gap" per se in this context, as genetic algorithms can't rigorously bound the problem to generate an ...

2

Now that you have removed the range constraints, the problem decomposes by $j$ and can be solved optimally for each $j$ by a greedy algorithm: set $X_{i,j}=1$ for the $b_\max$ largest (positive) values of $R_{i,j}$.

2

The question is still open and interesting. In my contribution to IPCO-2, Pittsburgh, 1992, I provided a family of examples of a Euclidean instance with a worst case ratio approaching $2.43$ and a non-Euclidean one with ratio approaching $6.5$. An easy example of a Euclidean instance with a bad Farthest Insertion result is constructed by considering an ...

1

Since you are open to a heuristic, I wonder if a restricted decision diagram (DD) might work for you. Decision diagrams are similar to dynamic programs in the sense that each node represents a state of the system and each arc represents a decision that results in a new state that is dependent only on the decision and the state at which it is made. The least ...

1

since you deal with a scheduling problem I encourage you to have a look at CPOptimizer scheduling within CPLEX. See also https://stackoverflow.com/questions/49405659/mip-vs-cp-for-scheduling-problems

1

I do not think it is possible to get a useful evaluation of candidates for $A$. I'm going to tweak your notation slightly, making the time index a superscript, and I'm going to assume that we have permuted indices so that the observed values of $x$ and $y$ come first, followed by the hidden values. We can partition things and write the matrix equation as  \...

1

An introduction to several algorithms can also be found in "Stochastic Local Search - Foundations and Applications" by Holger Hoos and Thomas Stützle. It contains an overview of the main methods, analyses, and some applications. https://www.sciencedirect.com/book/9781558608726/stochastic-local-search

1

Chapter 7 of the book called Artificial Intelligence with Python by Patreek Joshi focuses on the heuristic search methods. Other than that, the following list of references can be considered for more details on Metaheuristics: Clever Algorithms: Nature-Inspired Programming Recipes (by Jason Brownlee) Essentials of Metaheuristics (by Sean Luke) Hands-On ...

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