New answers tagged graphs
2
I had the following model lying around:
$$\begin{aligned}
\min&\sum_{i,k}\color{darkred}d_{i,k}\\
& \color{darkred}d_{i,k} \ge \sum_c \left(\color{darkblue}p_{i,c}-\color{darkred}\mu_{k,c}\right)^2-\color{darkblue}M(1-\color{darkred}x_{i,k}) \\
& \sum_k\color{darkred}x_{i,k} = 1 && \forall i\\
& \color{darkred}n_k = \...
3
It depends on what you want to achieve exactly. You could, for example, want to minimize the average distance between a point and the "center" of the cluster. This requires that you first define this center. Assuming it is one of the points, then intoduce a binary variable $y_j$ that takes value $1$ if and only if point $j$ is the center of one of ...
2
Maxcut with CPLEX CPOptimizer in https://github.com/AlexFleischerParis/howtowithopl/blob/master/maxcutcpo.mod
using CP;
execute
{
// time limit 10 s
cp.param.timelimit=10;
}
int n=400;
range r=1..n;
// Random graph
float edge_prob=0.5;
int weight_range=10;
int big=100000;
tuple t
{
int i;
int j;
}
{t} s={<i,j> | ordered i,j in r};
int ...
3
Have a look at MQLib, which contains efficient implementations of many published algorithms. Their paper is awesome too.
You can find a lot of code for QUBO online, one of the most publicized being qbsolv from Dwave. It is meant as a demonstrator of how much better quantum algorithms are, and the method is very basic.
In general, I would take any hype on ...
8
This is where decomposition algorithms (specifically Dantzig-Wolfe can be quite useful).
My thesis work and subsequent OSS in COIN provides APIs to do this kind of thing:
https://projects.coin-or.org/Dip
The basic idea is that the oracle is the graph implementation while the side constraints are modeled as the master constraints in the decomposition ...
6
In general ILP solvers are not as efficient in solving the Maximum Matching problem. A comparison of efficient matching algorithm implementations, as well as an ILP formulation for the Maximum Cardinality Matching Problem and the Minimum Weight perfect matching problem can be found in Figures 5 and 6 of this paper:
Dimitrios Michail, Joris Kinable, Barak ...
Top 50 recent answers are included
