New answers tagged computational-complexity
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