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
4 votes
1 answer
93 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) ...
user avatar
  • 73
2 votes
1 answer
54 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) ...
user avatar
1 vote
1 answer
82 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 ...
user avatar
  • 267
3 votes
0 answers
44 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 ...
user avatar
  • 1,246
1 vote
0 answers
69 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$ ...
user avatar
  • 101
3 votes
2 answers
356 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), ...
user avatar
8 votes
3 answers
421 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 ...
user avatar
  • 10.1k
11 votes
5 answers
1k 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 ...
user avatar
  • 10.1k
2 votes
0 answers
81 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 ...
user avatar
7 votes
3 answers
366 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 ...
user avatar
  • 179
2 votes
0 answers
24 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 ...
user avatar
2 votes
1 answer
65 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 ...
user avatar
  • 171
4 votes
1 answer
143 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, ...
user avatar
  • 5,744
4 votes
1 answer
128 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 ...
user avatar
2 votes
1 answer
104 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 ...
user avatar
  • 533
2 votes
1 answer
133 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 ...
user avatar
  • 131
3 votes
0 answers
43 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 ...
user avatar
  • 131
5 votes
0 answers
131 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 ...
user avatar
6 votes
2 answers
210 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 ...
user avatar
5 votes
4 answers
204 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$ ...
user avatar
4 votes
0 answers
202 views

Simplified risk game: writing a pratical Minimax objective for mixed integer programming

Problem To ensure fairness of the game, I am writing a bot that plays against itself. I have trouble rewriting a minimax objective to a practical maximization in mixed integer programming. The amount ...
user avatar
4 votes
1 answer
175 views

How to partition a graph with optimal number of groups?

I have a graph with $N=12$ nodes. Some nodes may not have any edge between them. every edge has a weight. How to find the optimal partitioning of the graph so that total weight in the system is ...
user avatar
5 votes
1 answer
145 views

Quickest shortest path algorithm

I want to do a shortest path algorithm. My direct and not acyclic graph contains only positive numbers. I have to do the scan for all pairs of nodes in complete depth in python. My graph is big (...
user avatar
  • 659
2 votes
2 answers
89 views

Graph partitioning/cutting problem

Let $G = (V,E)$ be an undirected graph, with $e \in E$ has positive weight $w_e$. Given a set of integers $I = \{i_1,\dots,i_n\}$ such that $\sum_{k=1}^n i_k = |V|$. I want to find a partition $P$ of $...
user avatar
4 votes
2 answers
245 views

Any Solution for $k$-means with minimum and maximum cluster size constraint?

I am looking for an efficient approach to $k$-means clustering with minimum cluster size constraints. The clusters are non overlapping, so, one point can belong to only one cluster. $N$ be the number ...
user avatar
5 votes
2 answers
179 views

MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?

I missed the opportunity to ask this on OR.SE by 24 days! I asked it at CS.SE on 6 May 2019 and OR.SE entered Private Beta on 30 May 2019. It's a problem about minimizing a sum of terms that are ...
user avatar
  • 1,246
7 votes
2 answers
502 views

Can a generic ILP solver find graph matchings as fast as a specialized algorithm?

Finding a maximum matching, or a maximum-weight matching, is a well-known problem, which has polynomial-time combinatorial algorithms. It can also be formulated as an integer linear program. In ...
user avatar
3 votes
2 answers
84 views

IP model for k-rooted spanning forest

I am looking for an IP model for finding a $k$-rooted minimum spanning forest on an undirected graph $G$. Given a set of roots $R$ and a set of nodes $N$ $(R\cap N=\emptyset)$, I would find a forest ...
user avatar
  • 907
1 vote
1 answer
178 views

Minimum vertex cover and linear programming 2

This is a modified version of the algorithm that I have proposed here. Suppose we have a graph G. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for ...
user avatar
3 votes
0 answers
40 views

Power grid distribution and recipient bias

I have a strong feeling that this problem I'm trying to solve has already been done by someone much smarter than me at one point and I'm more looking at where I can research a topic further rather ...
user avatar
  • 31
4 votes
1 answer
77 views

Does anybody know the complexity of finding a maximum clique in circulant graphs?

I would be interested in knowing if finding a maximum clique in circulant graphs is NP-hard? Does anybody have any pointers or papers to suggest?
user avatar
1 vote
0 answers
32 views

Create randomly an undirected connected graph using Matlab [closed]

I want to create randomly an undirected connected graph $G=(V,E)$ with $n$ nodes and $m$ edges using Matlab. How can I do this?
user avatar
0 votes
1 answer
271 views

Miller-Tucker-Zemlin subtour elimination constraints to obtain a minimum spanning tree

I need Miller-Tucker-Zemlin subtour elimination formulation for symmetric traveling salesman problem (STSP) to use to construct a minimum spanning tree. Ie, I need Miller-Tucker-Zemlin formulation ...
user avatar
9 votes
2 answers
453 views

How to maximize "contrast" between nodes on a graph?

I have an undirected graph such as the one shown below. I can make up to 3 choices about the color of each node. The edge weights are equal to the difference between the nodes, given by the "...
user avatar
2 votes
1 answer
1k views

Ordering Nodes of a graph according to their degree

In an undirected graph, I would like to order its nodes according to their degree. However, to do this I have to enter the edges of the graph first. When I do this, NetworkX in Python reads the nodes ...
user avatar
  • 443
2 votes
0 answers
112 views

Node ordering in Graph optimization

I'm solving a network optimization problem which is modeled as a graph $G=(V,E)$. Solving this problem using Pulp and NetworkX in Python and ordering the graph's nodes in a certain order (i.e. (1,2,3,...
user avatar
  • 443
5 votes
2 answers
280 views

Shortest path problem with underlying continuous variables

I recently got interested in the following variation of the shortest path problem. I've looked in the literature for days but I couldn't find any paper studying this problem. I'd like to ask if you ...
user avatar
3 votes
0 answers
87 views

Simplex method on graphs: How do I find a basic solution using the Ford-Fulkerson algorithm?

I'm tasked with solving a minimal cost flow problem. I'm asked to first use the Ford-Fulkerson algorithm on my graph to find a basic solution that will then be used to do the simplex method on that ...
user avatar
2 votes
1 answer
84 views

Algorithm / Method for determining N nodes to disconnect group of nodes

Hell everyone I have been trying to read through this forum for the methodology to approach a graph/network problem. The idea is I have an undirected graph, and every node is capable of talking to any ...
user avatar
  • 305
1 vote
1 answer
81 views

Handy way to index set of tuples in AMPL

I am dealing with a discrete math optimization problem on a complete graph. My variables are the arcs but I want to delete the arcs that "cost too much". I have $n$ nodes which means I have $...
user avatar
  • 113
6 votes
1 answer
337 views

What is intended when we use "robustness", "resilience" and "reliability" in Operations Research?

I will use an example to detail my question but I would like you to keep in mind that I wanted to define: Robustness, Resillience, Reliability in the most general case within Operations Research. ...
user avatar
  • 533
4 votes
1 answer
62 views

What is the name of the graph where any edge is part of a cycle?

I wonder if there is a special category for this kind of graphs, I am thinking of a bidirectional graph but it would also be interesting in the cases when it is undirected. I am thinking of something ...
user avatar
6 votes
3 answers
592 views

How to find all descendant vertices of all vertices in a big DAG (Directed acyclic graph)?

A simple algorithm may be traverse all vertices, and perform DFS for every vertex. However, the computational complexity is $O(n(n+m))$, where $n$ and $m$ are the number of vertices and edges in the ...
user avatar
2 votes
0 answers
53 views

Is this a common generalization of the independent set problem?

Suppose a minimum weighted independent set in a conflict graph with $n$ vertices. The basic version is where each vertex $i$ is associated with a weight $c_i$. i.e., there is a vector $C$ for the ...
user avatar
  • 2,034
3 votes
1 answer
260 views

social network analysis - relations between people with weights

I asked this question on datascience.stackexchange but they directed me here. I have a social network represented as a set of people $S$ and individual weights for each of person (weight is the cost ...
user avatar
  • 39
1 vote
1 answer
100 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 ...
user avatar
2 votes
0 answers
109 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} ...
user avatar
4 votes
1 answer
119 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 ...
user avatar
  • 1,229
8 votes
1 answer
69 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 ...
user avatar
  • 907
4 votes
2 answers
151 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.
user avatar