# Tag Info

## Hot answers tagged graphs

24

As far as I understand it, all machine learning approaches used for solving (combinatorial) optimization problems, and in particular reinforcement learning, work as follows: Use a greedy algorithm to iteratively construct a solution (e.g., by iteratively selecting edges into a path or a tour), and "learn" the ranking (i.e., the ordering) of the next items ...

14

Wouldn't eliminating all outgoing arcs from the red node except to the blue node, and eliminating all arcs from the green node except to the yellow node, or in general, eliminating all arcs from $a$ except those to $b$ already do the job?

14

Reinforcement learning is set of the algorithms which are used to solve Markov Decision Processes and its variants, e.g. Partially Observed MDP (POMDP). Most of the problems that we deal with them in the industrial engineering departments and in a larger extent in the Informs community, can be modeled as a MDP or POMDP. Although, in MDP we assume that we ...

14

Recognize that each route can be viewed as being a node on a graph. Edges connect nodes if the routes the nodes represent intersect. This is the canonical graph coloring problem for which there are a number of exact and approximate algorithms. Specifically, you're trying to find a constructive algorithm for determining the chromatic number. For 10 routes ...

11

This paper by Pisinger and Ropke is particularly useful when working on (A)LNS, and provides great guidance and an overview of operators/neighborhoods. I would suggest this paper by Vidal et al. for more genetic search inspired aspects.

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$} \...

10

From the question and the comments I gather that you really only have one pair between with connectivity could be established (by activating edges) and whether this is the case or not should be indicated by a binary variable. How about sending one unit of flow between the two nodes? In, say, the source node you send the one unit either along an exisiting/...

10

CPLEX has a parameter (RootAlgorithm) that lets you select the method for solving an LP (or for solving the root node relaxation of an ILP). The default setting is to let CPLEX choose, which usually (but not always) results in it using dual simplex. One of the choices is "network simplex", which you might try for a graph problem. I don't know whether CPLEX ...

9

Often such problems have side constraints, and this patent covers that more general case, using Dantzig-Wolfe decomposition with the network subproblem (MST, TSP, etc.) expressed compactly (not algebraically) and solved with a specialized solver. This functionality is implemented in SAS but currently undocumented. Please contact me if you are interested in ...

9

You can model your problem by defining separate variables for each traveling salesman. Below I will use 'vehicle' instead of 'traveling salesman', which is more common in this setting. Defining separate variables Let $n$ be the number of customers and let $m \le n$ be the number of vehicles. For each vehicle $k = 1, \dots, m$, define the variables $$x_{ij}^k ... 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 ... 8 Y. Kaempfer and L. Wolf, in their recent paper [1] applied ML techniques to solve the Multiple Traveling Salesmen Problem (mTSP). They provide a mathematical model for problem formulation which can be modified to cover what you need in the solution to your problem. You can replace the constraint (2d) which is:$$\forall 2\leq j \leq n: \sum\limits_{i=1}^{n}...

8

In DP Bertsekas Network Optimization (that can be downloaded for free) there's an exercise at Page 104 (Finding an initial price vector) where you can find a method for solving shortest paths in dynamic graphs. Basically, it resorts to using the price vectors from the first iteration to warm start the method at the second. Many years ago I implemented that ...

8

A main reason to use Reinforced Learning (RL) is because you don't know the dynamics (update rules) of the system. If you don't know the details of how the system will update, you will not be able to construct tight constraints for MIPs. For example, you may be able to write an MIP for the system with constraint $Ax = b$. However, the values of some ...

8

Since your graph is directed you can first compute the strongly connected components in linear time $O(n+m)$, contract the components, and then run BFS on the contracted graph. For each strongly connected component with $c$ nodes this saves you $c-1$ BFS calls. Also, the resulting graph is a DAG, so processing it in reverse topological order the reachable ...

8

These common neighborhoods for TSP/VRP might be useful: 2-opt, 3-opt, ..., k-opt change 1 visit: remove 1 visit from a chain and insert it somewhere else in a chain swap 2 visits change a subchain of visits: remove a number of sequential visits from a chain and insert it somewhere else in a chain, sometimes reversed swap 2 subchains ruin&recreate

8

Such a graph is called bridgeless.

8

I think these terms are all rather vague and imprecise, and different people use them slightly differently. Some papers try to draw clear lines between them—for example, in my dissertation in 2003, I draw a distinction between robust (i.e., perform well with respect to uncertainties in the data, such as demand) and reliable (i.e., perform well when parts of ...

7

See http://oeis.org/A000088, which gives a different number (34) for n = 5.

7

I suspect there are a few specific problems for which the answer is "yes," and I hope others will answer to provide examples of those. But in general I believe the answer is "no." For example, if you formulate the minimum-spanning tree problem as an IP and try to solve it with a general-purpose solver, it will be much slower than just using Prim's or ...

7

Graph cuts were mainly used in computer vision, where since 2011 deep neural networks have taken over the field. The decline from 2015 on is attributable to a time delay in picking up neural networks. Specifically, graph cuts were used for inferring maximum probable states in Markov Random Fields (MRF), with input costs coming from hand-tuned features. ...

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 Here is one suggestion : Network Flows: Theory, Algorithms, and Applications by Ahuja, Magnanti, Orli. The maximum flow problem is delt with in chapters 6-8, but I suggest you read the ones before if you are not familiar with flows in general. Also, James Orlin (one of the authors, teaches at MIT) has a webpage where you can find solutions to some of the ... 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 ... 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 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} \...

5

I'd like to add a few more ideas that could be important for solving this problem. I agree that a multiple-vehicle integer programming formulation may be a reasonable approach. In an arc-based model, decision variables $x^k_{ij}$ specify that vehicle/salesperson $k$ travels between $i$ and $j$ on its subtour. In such a formulation, you should create multiple ...

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

5

I am not sure. But this is an obvious case where parallelization will help (per source node, and instance).

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