New answers tagged

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