Skip to main content

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
2 votes
2 answers
81 views

Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs

I am working on a problem involving finding the shortest path in a Directed Acyclic Graph (DAG), where each edge's cost depends on multiple transportation modes, each with its own setup cost. I am ...
0 votes
0 answers
29 views

Spectral clustering with laplacian matrix eigenvector

I want to separate a given graph in $k$ clusters with the laplacian matrix ($L = D-A$ where $D$ is the degree matrix and $A$ the adjacency matrix). How can the eigenvectors of $L$ be used, along with ...
5 votes
1 answer
232 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\\ &...
2 votes
1 answer
143 views

How to generate random connected planar graph?

I was trying to generate random connected planar graph for dome numerical experiment of some transportation problem. I have three types of nodes: supply, transshipment and demand. I have the number of ...
2 votes
1 answer
52 views

updating cliques for an updated graph

A graph $G$ has nodes $V$ and edges $E$. Let's say I have found the maximum clique or all the cliques in $G$ with any algorithm, such as the Bron-Kerbosch algorithm. After a while, $E$ has been ...
1 vote
0 answers
40 views

Complexity of cardinality constrained maximum weight independent set problem

Given a graph with a set of nodes and edges, the goal of the maximum independent set problem is to find the maximum number of vertices where no two vertices are adjacent. This is well-known NP-hard ...
2 votes
1 answer
180 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 ...
13 votes
1 answer
160 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^...
1 vote
0 answers
64 views

Need help with a model to optimize a trail in directed graph

The graph in the image represents the production sequencing on a machine with production capacity C in volume. Each node N represents a different product with a profit L per volume produced. Every ...
0 votes
0 answers
48 views

Distributed coloring of nodes of sensor ntwork

I have the same graph coloring problem as in Coloring of nodes of a sensor network @RobPratt and @prubin have proposed some very good solutions. This time I am or interested in distributed coloring ...
0 votes
0 answers
146 views

In routing problems, when is it ever necessary to include both 1) subtour elimination constraints, AND 2) elementary paths constraint?

In many routing problems, it is fairly common to include a constraint that ensures all vehicles follow an elementary path, meaning that no vertices are repeated. However, when an elementary path is ...
0 votes
1 answer
38 views

Graphs arcs on AMPL C++ API

I am trying to model a routing instance in AMPL C++ API. The AMPL Book presents a strategy for modeling routing instances via AMPL (Figures 6-2a and 6-2b, Page 95, Chapter 6), as it is presented below:...
2 votes
1 answer
93 views

Is there a name for this problem?

Consider a graph $G = (V,E)$ where $V$ is the set of vertices and $E$ is the set of weighted edges. We want to create $N$ disjoint subsets of $V$ such that the sum of weights inside each subset is ...
6 votes
1 answer
801 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 ...
1 vote
4 answers
134 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 votes
1 answer
291 views

How to do one octomino?

Here are all the 369 octominoes: https://en.wikipedia.org/wiki/Octomino If I have an 8x8 area, how to create one octomino, any of those 369 and any rotation and mirroring is allowed? I have tried ...
3 votes
1 answer
228 views

Graph coloring problem redundant constraints

Say the edges of a 4 nodes graph are 0 1, 1 2 and 1 3. The solution to the colouring problem ...
7 votes
0 answers
105 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 ...
1 vote
1 answer
82 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. @...
7 votes
2 answers
321 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=\{...
0 votes
0 answers
34 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 ...
0 votes
1 answer
89 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 ...
1 vote
1 answer
52 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 ...
2 votes
1 answer
218 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 ...
1 vote
4 answers
148 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 ...
3 votes
2 answers
152 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 ...
7 votes
1 answer
172 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 ...
5 votes
2 answers
152 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 ...
6 votes
2 answers
260 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 ...
3 votes
3 answers
202 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 ...
3 votes
0 answers
77 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 ...
5 votes
3 answers
391 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 ...
1 vote
2 answers
274 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 ...
3 votes
0 answers
152 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 ...
8 votes
1 answer
162 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 state-...
2 votes
0 answers
68 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(\...
3 votes
1 answer
70 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. ...
3 votes
0 answers
47 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 ...
5 votes
1 answer
208 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 ...
4 votes
1 answer
324 views

Creating constraints dynamically in pyomo abstract model

I have a networkX graph with few nodes and these nodes have attributes such as "demand". ...
2 votes
4 answers
1k 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 ...
4 votes
3 answers
206 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
1k 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 ...
5 votes
4 answers
259 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$ ...
3 votes
1 answer
90 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 ...
6 votes
0 answers
94 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)$ ...
2 votes
2 answers
602 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 ...
2 votes
1 answer
116 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
215 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) ...
2 votes
1 answer
133 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) ...