Hot answers tagged

11

Let binary decision variable $x_{i,g}$ indicate whether node $i\in\{1,\dots,N\}$ appears in group $g\in\{1,\dots,N\}$, and let binary decision variable $y_{i,j,g}$ indicate whether edge $(i,j)$ appears in group $g$. You want to maximize $$\sum_{i<j}\sum_g w_{i,j} y_{i,j,g}$$ subject to \begin{align} \sum_g x_{i,g} &= 1 &&\text{for all $i$} \...


9

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 ...


7

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 ...


7

A greedy heuristic is natural to try here: Declare all groups to be admissible. Find an admissible group $g$ with the largest weight. Set $u_g=1$. Declare all groups $h$ with $N_h \cap N_g \not= \emptyset$ inadmissible. If some $i$ is still uncovered, go to step 2. For your sample data in the linked question, this greedy heuristic returns groups $$\{11,12,...


6

I don't know whether this will be efficient enough for your real graph sizes, but with binary decision variables $x_{v,k}$ to indicate whether vertex $v$ is assigned label $k$, you can obtain a formulation that looks a lot like the quadratic assignment problem. Let $V_i$ be the set of vertices in layer $i$. The problem is to minimize $$\sum_{(v,w)\in E} \...


6

You can solve this as a quadratic assignment problem. With the same $x$ variables as in @Kuifje's answer, you want to maximize $$\sum_{(u,v)\in A}\sum_{j\in C(u)}\sum_{k\in C(v)}|\omega_j- \omega_k| x_{u,j}x_{v,k} \tag1$$ subject to $$\sum_{j \in C(v)} x_{u,j} = 1 \quad \text{for $v \in V$} \tag2$$ One approach is to call a mixed integer quadratic ...


6

If you are dealing with Voronoi diagrams then perhaps your graph is planar, and in this case there is probably a good heuristic for the problem, but more details should be given I think before going down that road. In the mean time you can try working with a MIP as suggested by @SimonT. For example: Let $x_{vc}$ be a binary variable that takes values $1$ if ...


5

It is NP-hard: Bruno Codenotti, Ivan Gerace, Sebastiano Vigna. Hardness results and spectral techniques for combinatorial problems on circulant graphs, Linear Algebra and its Applications 285 (1-3), pages 123-142, 1998, pdf Other Cayley graphs have been studied by Chris Godsil and Brendan Rooney in the paper Hardness of Computing Clique Number and Chromatic ...


5

One way of addressing this problem would be to discretize the sets $S_v$ for each $v \in V$. That is, define a finite number of points within $S_v$, and for each of these points, define a node. Link these nodes to all of the neighbors of node $v$, but adapt the distance with the actual Euclidian distance. Once you have this new graph, run the classical ...


5

I am pretty sure the answer is NO! Consider the graph consisting of a $K_5$ (the fully connected graph with 5 nodes) and two additional nodes $r_1, r_2$ that have an edge to each of the nodes in the $K_5$. The optimal LP relaxation $S_{hi}$ is taking all nodes with value $\frac{1}{2}$. Adding the extra odd circle constraints one can get an optimal solution $...


4

I recommend extending Paul's single-commodity formulation to a multicommodity formulation with $k$ commodities. Let binary variable $z_{i,r}$ indicate whether node $i\in R \cup N$ is assigned to tree $r\in R$. The idea is to send one unit of commodity $r$ from the dummy source node $0$ to node $i$ iff $z_{i,r}=1$. The problem is to minimize $\sum_e c_e ...


4

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 = \...


4

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 ...


4

To answer the original question, this is not a problem I have seen before. I upvoted Kuifje's answer, because while approximate it should be fairly computationally efficient if the discretization does not create too many points. Another approach that I think would work would be a riff on Benders decomposition. It requires that the convex sets be polyhedral ...


4

A variant of Rob's answer would be a random key genetic algorithm. You can program a GA from scratch, although you're probably better off using an open-source library. Each "chromosome" in the GA would be a permutation of the indices $1,\dots, \vert G \vert$ (or a vector of $\vert G \vert$ real values whose sort order would translate to such a ...


4

Try adding valid constraints $$ y_{i,j} \le \sum_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,k} \quad\text{for $(i,j)$ such that $\hat{y}_i = 0$ and $j \in \tilde{V}\setminus\{i\}$} $$ that enforce the logical implications $$(y_{i,j} \land \lnot\hat{y}_i \land [j \in \tilde{V} \setminus\{i\}]) \implies \bigvee_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,...


3

The definition of a k-truss you are working with seems to deviate from the 'standard' definition. See below for a few different definitions that boil down to the same thing. A k-truss of a graph $G$ is the largest subgraph of $G$ such that each edge is contained in at least $k−2$ triangles in this subgraph. source: Li, Z., Lu, Y., Zhang, WP. et al. ...


3

Maybe this can work? Numbering is same as sorting. Disregard the layers and treat the whole thing as a single graph. Use Cuthill-Mckee (if the bandwidth is low) or other heuristics for the graph bandwidth problem to find the big ordering of nodes. For each layer, filter out the nodes of other layers in the big ordering to get the ordering of nodes in that ...


3

I hacked a random key genetic algorithm for the problem in Java, and ran it against a linearized version of Rob Pratt's MIP model (using CPLEX 20.1 with default parameter settings) on some small random test problems (five layers, three to nine nodes per layer, about 1/4 of all possible edges present). Because the GA stagnated very quickly, I did multiple ...


3

Replace each undirected edge $(i,j)\in E$ with two directed arcs $(i,j),(j,i)\in A$ with the same cost $c_{i,j} = c_{j,i}$. For each $(i,j)\in A$, let binary variable $x_{i,j}$ indicate whether that arc appears in the tree. Let node $1$ (arbitrarily) be the root, and omit all arcs into the root. For each node $i\in N$, let $u_i\in [0,n-1]$ be the MTZ ...


3

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 ...


3

There are flow models for the MST problem that can easily be adapted to the $k$-rooted MST. For each edge $e=(i,j)$ in the graph, create a binary variable $x_e$ (1 if the edge is used in a tree, 0 if not) and two nonnegative variables $y_{ij}, y_{ji}$ representing flows along the edge in either direction. Connect them via the constraints $y_{ij} \le n x_e$ ...


2

I am pretty sure the answer is again NO. And it can be seen with the same graph as in the previous question here. Consider the graph consisting of a $K_5$ (the fully connected graph with 5 nodes) and two additional nodes $r_1, r_2$ that have an edge to each of the nodes in the $K_5$. First note that if we force any of the nodes $r_1, r_2$ to take value $0$ ...


2

I know this is not a typical answer, but I decided to post this tweak to help others when they are facing the same problem. I have added another initiation for the graph method using the same name of the graph g=nx.graph() just before the definition of the sorted nodes, such that the graph will consider the sorted nodes as g.nodes, the code will be such that ...


2

Your problem description is quiet vague. So i picked the simplest solution to his problem i can think off in modeling language JuMP. If you are more detailed about the reality you are working with a better model can be chosen. clients = 24 servers = 3 using JuMP using GLPK class = Model(with_optimizer(GLPK.Optimizer)) cost = rand(clients, servers) # cost ...


2

Treat nodes in 1st and 3nd layer as extra edges in the 2st layer to make a merged layer. Minimize bandwidth of 2nd layer. Repeat for the other layers. layer 2: o o o \ / \ / layer 1: @ @ @ becomes an edge: layer 2: o - o - o ```


2

When the objective function relies on the weights of edges within the subgraphs (as opposed to edges connecting subgraphs), I believe your problem is equivalent to a quadratic multiple knapsack problem. There seems to be a fair bit of literature on that problem (of all of which I am blissfully ignorant).


1

I think these are promising options: floyd-warshall algorithm for dense graphs johnson algorithm for sparse graphs (not sure if it's worth to try and it will work well) dijkstra algorithm parallelized for each vertex Regarding your question, a correct floyd-warshall implementation scans all the pairs.


1

The capacitated max-k-cut formulation models the problem I describe. Besides, it is less constraining, since the equality $\sum_{k=1}^n i_k = |V|$ becomes $\sum_{k=1}^n i_k \geq |V|$, where elements $i_k$ are referred as capacity.


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