Questions tagged [graphs]
For questions related to graphs, a mathematical object consisting of a set of nodes with edges connecting certain pairs of them.
98
questions
6
votes
0
answers
89
views
MIP formulation for graph planarity test
In this question, it was asked wether a MIP formulation exists to test for a graph's planarity. The inputs are the graph's nodes and edges, and the output would be a certificate which guarantees that ...
- 12.3k
1
vote
1
answer
75
views
Traffic lights optimization (part 2)
This is a follow up question of this thread, in which it is asked how to model a circular layout of a given set of cliques of a graph, which represent simultaneous movements at an intersection.
@...
- 12.3k
0
votes
0
answers
33
views
How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)
How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following.
Given a graph $G = \{V,E\}$,
we have a distance matrix (the ...
1
vote
4
answers
66
views
Coloring of nodes of a sensor network
It is the same problem as posted at Coloring of nodes in a sensor networks.
Its about coloring a weighted graph.
@RobPratt suggested a very good solution that solves the problem directly.
However, we ...
- 2,191
0
votes
1
answer
67
views
Coloring of nodes in a sensor networks
I have weighted graph for sensor networks with aggregation nodes and sensors. There is a edge between two nodes associated with a weight.
Higher the weight, stronger the interference between the ...
- 2,191
7
votes
2
answers
307
views
Traffic lights optimization
I am interested in the following problem dealing with the optimization of traffic lights on the intersection illustrated below:
The goal is maximize the duration during which each movement $m\in M=\{...
- 12.3k
1
vote
1
answer
47
views
Does cutting a minimum spanning tree generate two minimum Steiner tree?
I am trying to understand whether this intuition is true or false.
Given a minimum spanning tree (MST) of an undirected positive graph $G=(V,E)$.
Consider a MST $T\subseteq G$. Removing any single ...
- 561
1
vote
1
answer
70
views
Smallest graph coloring in Gurobi
I am trying to design an algorithm to label a graph’s nodes with as few colors as possible
such that all pairs of nodes joined by an edge do not have the same color.
This is the code I have written so ...
- 133
1
vote
4
answers
116
views
How to perform clustering of a large number of nodes?
I have a clustering problem with around 400-500 nodes. The edge between any two nodes has a weight (between 0 and 1, 0: can be considered as there is no edge/connection between these two nodes) as ...
- 2,191
3
votes
2
answers
140
views
Vehicle passenger assignment with capacity constraint
Problem Summary
To match passengers (the number of passengers) to capacitated vehicles such that the profit is increased. All the vehicles have the same capacity $c$. It is not important to track ...
- 33
5
votes
2
answers
109
views
Number of simple cycles on the graph
I would like to know if there is an efficient way to formulate simple cycles on the Graph/Digraph. Let's say, there is a grid-form graph for which each vertex is only connected to a limited number of ...
- 7,644
3
votes
3
answers
173
views
Directed trees and the order/score of each node in the tree
Suppose we have a directed tree as follows:
The information regarding the edges are also given to us as a list
like edge_info = [ (a,c) , (a,b) , (b,d) , (b,e) , (b,f) ]
I am trying to find a way to ...
- 1,120
6
votes
2
answers
244
views
How to partition a giant tour into feasible routes?
In vehicle routing problems, the route first cluster second approach starts by computing a "giant" TSP tour (which typically does not satisfy all constraints of the problem), and then ...
- 12.3k
3
votes
0
answers
61
views
Flow problem with flow demands
Recently I found a subproblem in a project I am working with. This problem is a sort of flow variant, as you will see. And I am looking for literature-related articles and also fast approaches for ...
- 1,059
5
votes
3
answers
383
views
Is this arc routing formulation correct?
Let $G=(V,E)$ be a graph. I would like to identify an eulerian cycle in $G$ with minimum cost, with an integer programing approach:
$x_{ij}$ are integer variables that denote the number of times that ...
- 51
1
vote
2
answers
225
views
Graph models - Maximum flow problem and minimum cost flow problem
I'm trying to solve this problem:
An investment agency holds the rights to six investment projects: I1, I2, ..., I6. Projects I1, I2 and I3 are research and
technological development projects and the ...
- 119
7
votes
1
answer
145
views
Name of graph algorithm arising while using the Ryan Foster Branching
I'm using the Ryan-Foster branching in my Branch and Price algorithm for a pickup and delivery problem, but I'm having trouble keeping track of all the pairs as I go down the search tree.
Let's say ...
- 173
2
votes
0
answers
52
views
Multi-objective optimization with known variable dependencies (via a graph) -- what is this called?
Suppose that I am trying to solve a standard multi-objective optimization problem:
$$
\min_{
\begin{array}{c}
\textbf{x} \in S
\end{array}
}
\left [ f_1(\textbf{x}),f_2(\...
- 121
3
votes
1
answer
66
views
How to write a constraint to define valid agglomerations of sites?
I am currently attempting to use a MIP to optimize the agglomeration of sites to fit a minimum size.
Take for example the following simplified situation of 9 sites which could be any range of sizes.
...
- 31
3
votes
0
answers
46
views
Looking for Balas' original JSP-as-digraph paper
I'm looking for E. Balas' original paper "Finding a Minimaximal Path in a Disjunctive PERT Network". Is this paper available via the web? Google and my campus library are unable to help me ...
- 762
5
votes
1
answer
159
views
Flow problem with side constraints: how to eliminate subtours?
I am working on a flow problem with side constraints. More specifically, I have a usual flow problem, with constraints that require some arcs to have exactly one unit of flow on them. This makes the ...
- 12.3k
4
votes
1
answer
176
views
Creating constraints dynamically in pyomo abstract model
I have a networkX graph with few nodes and these nodes have attributes such as "demand".
...
- 69
4
votes
3
answers
200
views
Is this ILP formulation for Group Closeness Centrality a column generation approach?
I want to solve the Group Closeness Centrality problem where the input is a graph $G=(V,E)$ and integer $k$ and we want to find a vertex set $S$ of size $k$ minimizing the total distance of the ...
9
votes
2
answers
929
views
Gurobi finishes with 'infeasible' although optimal solution exists
I am using Gurobi (in Python through gurobipy) to solve an IP on tournament graphs.
I am searching for a non-zero minimal integer weighting such that for every vertex the sum of weights put on the ...
- 153
3
votes
1
answer
79
views
Reformulating undirected to directed edges for MCF
As stated in this paper, there is a technique to reformulate a multi-commodity flow problem (MCF) with undirected edges to its equivalent version with directed edges.
By quoting them:
The ...
- 561
2
votes
1
answer
110
views
Finding Diverse Paths using Constraint Programming
I am working on a graph problem and want to find some link-disjoint paths between given node pairs. I was wondering if there is an efficient way to achieve this in CP. I checked OR-Tools (routing and ...
- 21
6
votes
0
answers
86
views
Graph coloring problem while counting cliques
Let $G$ be a graph with a set of nodes $V$ and a set of edges $E$.
Let $G'$ be a graph with the same set of nodes $V$ but a second set of edges $E'$.
For a set of nodes $X\subset V$, we denote $f(X)$ ...
- 93
5
votes
1
answer
222
views
Additional resources for this type of problem formulation
I'm working on a problem with the following formulation:
\begin{align}
\min&\quad\sum_{i \in N} \sum_{j \in J} V_{ij}x_{ij}
\\
\text{s.t.}&\quad \sum_j x_{ij} = 1 \quad \forall i \in N\\
&...
- 93
2
votes
2
answers
302
views
How to model Max-Cut as ILP
I want to model Max-Cut in IBM's CPLEX, but I fail at modeling the objective function.
My attempt is to use is to sum the XOR of inclusion for vertices of each edge, as exactly then an edge is ...
- 131
1
vote
1
answer
106
views
Graph Theory problem
I just got sent a problem that I haven't found any model for thus I do not know how to proceed in solving it, if anybody can show me a similar problem so I can use it as a starting point or if they ...
4
votes
1
answer
163
views
Efficiently updating latest finish times via Critical-Path-Method
For a Resource-Constrained-Project-Scheduling problem, I need to calculate Critical-Path-Method (CPM) values for each of the activities. These values are:
Earliest Start (ES)
Earliest Finish (EF)
...
- 115
2
votes
1
answer
84
views
Logic for Re-Labeling Nodes in a Directed Acyclic Graph
We are currently working at the intersection of metaheuristics and machine learning.
As part of the scheduling problem that we are trying to solve, we have a project network (directed acylic graph) ...
- 121
1
vote
1
answer
217
views
Solving Graph Partitioning Problems with Gurobi and Pyomo
I am trying to solve a graph partitioning problem for a large number of structurally similar random graphs with an 0-1 LP.
Most of these problems are solved within 0.x seconds. Some graphs take the ...
- 287
3
votes
0
answers
136
views
What can traditional graph cut methods do well, that deep learning cannot?
I have been fascinated by the rise and fall of graph cut algorithms in recent years, which I described in this question: Was there something specific that caused graph cuts to lose popularity in the ...
- 1,264
1
vote
0
answers
79
views
Bipartite matching
If I have two matrix
$$A = \begin{bmatrix}
1 & 2 \\
2 & 3
\end{bmatrix} $$ and $$B = \begin{bmatrix}
3 & 4 \\
5 & 3
\end{bmatrix} $$
We have to make a matching between $A$ and $B$ ...
- 139
3
votes
2
answers
757
views
Simple example of finding Hamiltonian path using Google OR-Tools?
I'd like to test how good/fast OR-Tools is in finding hamiltonian paths on some (big) directed graphs.
But I can't find simple enough (for me) examples.
Something like these ones (or even simpler), ...
- 59
8
votes
3
answers
494
views
How to tackle this VRP variant?
I am currently working on the following problem, which is a variation of a vehicle routing problem. I am looking for different ideas to tackle it.
Problem description
A set of nodes with a given ...
- 12.3k
11
votes
5
answers
2k
views
How to compute all paths between two given nodes in a network?
In this post, Erwin Kalvelagen describes a method to compute all paths between two nodes in a given network, such that:
no arc is used more than once
a given path does not contain more than $M$ arcs
...
- 12.3k
2
votes
0
answers
89
views
Order picking optimization: creating links between sectors of the warehouse
In the Conference Paper A Generic Approach for Order Picking Optimization Process in Different Warehouse Layouts, I cannot understand the process described on page 4:
That is done by creating new ...
7
votes
3
answers
583
views
Combining Multiple Cost Values in Shortest Path Problem
I am trying to solve a shortest path problem through Dijkstra's algorithm. However in my case, cost between nodes (nodes $i$ and $j$) are more than one- two nodes are compared based on two different ...
- 179
2
votes
0
answers
30
views
Are the operations in the Graph Edit Distance problem of interest?
In the graph edit distance (GED), we are looking to find the cost of modifying one graph $G_1$ to another graph $G_2$. Is the sequence of operations that take $G_1$ from $G_2$ of interest in this ...
- 333
2
votes
1
answer
71
views
Maximal Matching in a constrained, unweighted Bipartite Graph
Suppose a set of partially connected nodes:
All nodes are in set A xor in Set B (i.e. Bipartite Graph)
All nodes have a datetime property.
Connections in the ...
- 171
4
votes
1
answer
326
views
The difference between subtour-elimination constraints in the symmetric and asymmetric TSP
We know that there are lots of formulations for traveling salesman problem. Some of them are based on the directed graph (asymmetric) and others are based on the undirected graph (symmetric). Also, ...
- 7,644
4
votes
1
answer
165
views
Constrain Mixed-Integer problem such that a graph is fully connected
I have a problem (see my questions about Architectural layouts which poses an interesting abstract question) where there exists an implicit (symmetric) graph whose values in the adjacency matrix are ...
- 3,945
1
vote
1
answer
143
views
Linearization of constraints in a ILP
I have been working on a Graph Theory problem for my thesis and got stuck about the linearization of some constraints. I am hiding everything, constraints, variables and so on, of my problem not ...
- 583
2
votes
1
answer
276
views
Can't understand K-Truss Graph properties
Cross-posted on Mathematics SE.
Since I have to implement an algorithm in the language of linear algebra, I'm trying to understand K-Truss Graphs which are defined as such
The k-truss is a subset of ...
- 131
3
votes
0
answers
48
views
Graph matching with apriori information about the matches?
Given two graphs with n vertices each, where apriori information regarding the similarity of each pair of vertices (between the source and target nodes) is given, is there a known concept for finding ...
- 131
5
votes
0
answers
174
views
Reduction from Steiner Tree to TSP
The Steiner Tree version that I am considering is the following: given an undirected weighted graph $G=(V,E)$ and a subset of vertices $T \subseteq V$, find a minimum tree that connects all the ...
- 111
6
votes
2
answers
247
views
Heuristic solution to the graph partitioning problem
I am working on a graph partitioning problem. A static column generation based solution was proposed in How to partition a graph with optimal number of groups?
But I need some MILP solver to solve ...
- 2,191
5
votes
4
answers
251
views
Numbering the vertices of an $n$-layer graph so that edges have similar numbered vertices on their ends
Consider a graph whose vertices can be partitioned into $n$ layers. Edges exist only between vertices in successive layers. So, there are edges between layers $1$ and $2$, between layers $2$ and $3$ ...
- 343