New answers tagged

7

Here are my notes about the various discrete optimization methods. Combinatorial branch-and-bound Manual implementation Provides a bound Works well when the bound is good Rarely used nowadays Mixed-Integer (Non)-Linear Programming Model-and-run, very good commercial solvers Provides a bound Works well when the (N)LP relaxation (possibly with cuts) is ...


6

You have to keep in mind that MIPs can return the optimal solution, provided enough computation time is given. So if time is not an issue, I would always go for a MIP. Also, MIPs are more flexible in the sense that you can very easily add new constraints, modify the objective function, etc. On the other hand, with metaheuristics such as local search, there ...


8

This is a variant of the minimum $k$-cut problem. The node set is $\mathbb{X}$, the edge weights are $1-d(x,y)$, and $k=S$. Also related to the wedding planner problem, where $\mathbb{X}$ is the set of guests, $S$ is the number of tables, and $H$ is the maximum number of guests per table. Here, $d(x,y)$ measures whether $x$ and $y$ dislike each other. See ...


Top 50 recent answers are included