Questions tagged [graphs]

For questions related to graphs, a mathematical object consisting of a set of nodes with edges connecting certain pairs of them.

Filter by
Sorted by
Tagged with
1
vote
0answers
30 views

Find minimum cost problem

The problem below aims to find the minimum cost for the network architecture: We want to build a network where client terminals are connected to servers by cabling which is very expensive. The network ...
1
vote
0answers
72 views

Simplex - Network flow problem : Arc from 1 to P with infinite capacity

The Network - Maximum flow problem below aims to find the maximum flow using simplex method : With the LP as follow : LP : \begin{Bmatrix} Z(Max) = \sum_{i=1}^{m} fi \\ Af =0 \end{Bmatrix} ...
4
votes
1answer
74 views

Clustering a large ride-matching problem

Background: We are solving a large scale vehicle to person ride-matching problem. The problem is essentially simple (match every person with a vehicle, if possible), yet the problem size is quite ...
8
votes
1answer
55 views

Covering problem on a network (?)

I have this problem described in natural language, and I was wondering whether it is relatable to any known problem. I have a directed acyclic graph. Each node can host a "probe". If node $i$ hosts ...
4
votes
2answers
133 views

Maximum Flow Problem : Can someone refer me to accessible valuable resources

Can anyone please refer/suggest me some accessible papers, works, books, websites, documentation related to The Maximum Flow Problem.
7
votes
1answer
1k views

How to use the least number of colours to colour different routes of a bus route such that no two intersecting routes will have the same colour

I would like to know of a method in which if provided say 10 routes with details regarding which route intersects with which another route, we can use the least number of colours to colour the routes, ...
3
votes
2answers
98 views

Could DOcplex.CP recognize that it solves the graph coloring minimization problem?

I created a graph coloring DOcplex.CP model inspired by this example. However, I do not know the number of colors in advance. The goal is to minimize the number of colors (i.e., get as close as ...
4
votes
0answers
139 views

Minimum vertex cover and linear programming

Cross-posted on MathOverflow. Suppose we have a graph G. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the ...
6
votes
1answer
68 views

Maximum weight b-matching with global cardinality constraint

Suppose $A$ is an $n$-by-$n$ symmetric matrix whose entries are all nonnegative. $A_{ii} = 0$ for all $i$. We want to find an $n$-by-$n$ binary ($0/1$ valued) matrix $X$ that maximizes $$\sum_{ij} A_{...
7
votes
2answers
142 views

The general meaning of “constraint relaxation” in the context of the Shortest Path Problem

I've read that in the context of the Shortest Path Problem, the use of the term "relaxation" ("relaxing edges") [...][the use of the term "relaxation"] is historical. The outcome of a relaxation ...
12
votes
1answer
129 views

Re-calculating shortest path in slightly altered graph

I was wondering if someone has come across this before and/or has a smart idea for the following: I have a directed graph $G$ with costs $c$ associated with the arcs, and I know the shortest path $P^...
8
votes
0answers
60 views

Multiple shipments with FILO order

I am trying to solve a problem statement with the help of jsprit. There is a depot. Identical items need to be delivered or picked up. An item can have two states: Bad or good. Bad items need to be ...
15
votes
1answer
213 views

Was there something specific that caused graph cuts to lose popularity in the last 5 years?

Almost every graph-cut paper I look at seems to have exactly the same pattern of monotonic growth in citations and then monotonic decline starting around 5 years ago: For privacy I've cut the all ...
6
votes
1answer
193 views

Network flow model - How can I turn this diagram into a matrix that when converted to RREF solves for max flow?

I have the following network flow model diagram and I have already calculated maximum flow using the R package igraph to be 28. However, what I would like to know ...
9
votes
1answer
592 views

A variant of the Shortest Path Problem

Consider a layerwise directed acyclic graph DAG, $G=(V,E)$ and two vertices $s$ and $t$. $s$ is connected to all vertices in $L_0$, $L_0$ is connected to all vertices in $L_1$ and so forth. Consider ...
14
votes
3answers
2k views

A variant of the Multiple Traveling Salesman Problem

I am trying to find a reference (or a reformulation) of a variant of the multiple Traveling Salesman Problem, where multiple agents need to visit each vertex in a graph with minimal cost. Most of the ...
7
votes
1answer
85 views

References for “metric” network flow problems

Network flow problems are very well studied in the literature (e.g., see the Network Flows book), and the first DIMACS challenge was dedicated to these problems. Very efficient implementation of ...
10
votes
2answers
320 views

Many-to-many Breadth First Search

There is a directed social network with large number of nodes and arcs and there are many instances of the network (nodes are same but arcs change in each instance). You can think of it as a ...
10
votes
3answers
646 views

Graph problems as integer programs

Suppose I give a solver (CPLEX, Gurobi, SCIP or anything else) an IP which is a reformulation of a stable set problem (or vertex cover problem or coloring problem) of some graph, is there a way I can ...
1
vote
2answers
197 views

Is there any way to generate all the possible undirected graphs with unlabeled nodes?

I am looking for an efficient algorithm to generate all of the unique graphs for a given number of nodes. For small instances, the total number of graphs are as follows: n=2 G=2 n=3 G=4 n=4 G=11 ...
13
votes
5answers
201 views

Connectivity of two nodes in an arbitrary undirected graph

Is there an efficient way to model the connectivity of two nodes in an arbitrary undirected graph? I would like to have a binary variable representing this connectivity: 1 if there exists a path ...
23
votes
4answers
486 views

What are the tradeoffs between “exact” and Reinforcement Learning methods for solving optimization problems

Exact methods, e.g., models that utilize an MIP approach with a specified objective and constraints, have advantages like the following: Using off the shelf solvers Optimality gap provability ...
11
votes
2answers
119 views

Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

I have been trying to implement a variant of LNS on a graph for TSP. One of the ways that I can define a neighborhood for TSP is to find $k$-shortest path between two nodes. But the choice of these ...