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
1 answer
51 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 ...
OR Junior's user avatar
  • 521
2 votes
2 answers
69 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 ...
Changxin Cao's user avatar
1 vote
0 answers
36 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 ...
Mostafa's user avatar
  • 2,104
1 vote
0 answers
62 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 ...
Maria's user avatar
  • 11
0 votes
0 answers
46 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 ...
KGM's user avatar
  • 2,211
0 votes
0 answers
107 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 ...
IsalanOnkar's user avatar
2 votes
1 answer
132 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 ...
Vala's user avatar
  • 61
0 votes
1 answer
35 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:...
Matheus Diógenes Andrade's user avatar
2 votes
1 answer
92 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 ...
BloodyOrange's user avatar
2 votes
1 answer
284 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 ...
user9050's user avatar
  • 119
3 votes
1 answer
216 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 ...
Dr.PB's user avatar
  • 133
7 votes
0 answers
101 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 ...
Kuifje's user avatar
  • 13.2k
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. @...
Kuifje's user avatar
  • 13.2k
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 ...
Yichuan_Sun's user avatar
1 vote
4 answers
131 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 ...
KGM's user avatar
  • 2,211
0 votes
1 answer
88 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 ...
KGM's user avatar
  • 2,211
7 votes
2 answers
318 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=\{...
Kuifje's user avatar
  • 13.2k
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 ...
Daniele Cuomo's user avatar
2 votes
1 answer
183 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 ...
Andrew's user avatar
  • 163
1 vote
4 answers
146 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 ...
KGM's user avatar
  • 2,211
3 votes
2 answers
149 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 ...
Corey's user avatar
  • 33
5 votes
2 answers
139 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 ...
A.Omidi's user avatar
  • 8,717
3 votes
3 answers
194 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 ...
Optimization team's user avatar
6 votes
2 answers
255 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 ...
Kuifje's user avatar
  • 13.2k
3 votes
0 answers
74 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 ...
Matheus Diógenes Andrade's user avatar
5 votes
3 answers
387 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 ...
husson's user avatar
  • 51
1 vote
2 answers
254 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 ...
Carmen González's user avatar
7 votes
1 answer
167 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 ...
Victor Hugo's user avatar
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(\...
Astrid's user avatar
  • 121
3 votes
1 answer
69 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. ...
Musketeered's user avatar
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 ...
Brannon's user avatar
  • 892
5 votes
1 answer
196 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 ...
Kuifje's user avatar
  • 13.2k
4 votes
1 answer
288 views

Creating constraints dynamically in pyomo abstract model

I have a networkX graph with few nodes and these nodes have attributes such as "demand". ...
Waqas Swati's user avatar
4 votes
3 answers
205 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 ...
Christian Komusiewicz's user avatar
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 ...
Legsleg's user avatar
  • 153
3 votes
1 answer
82 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 ...
Daniele Cuomo's user avatar
2 votes
1 answer
171 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 ...
hmd.pouya's user avatar
6 votes
0 answers
91 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)$ ...
Jin Kazama's user avatar
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\\ &...
Bob Jeans's user avatar
2 votes
2 answers
496 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 ...
Moritz Groß's user avatar
1 vote
1 answer
113 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 ...
lifeispaingulag's user avatar
4 votes
1 answer
206 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) ...
Rutger's user avatar
  • 115
2 votes
1 answer
120 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) ...
derhendrik's user avatar
1 vote
1 answer
276 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 ...
baxbear's user avatar
  • 319
3 votes
0 answers
196 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 ...
Nike Dattani's user avatar
  • 1,278
1 vote
0 answers
87 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$ ...
Ishaan's user avatar
  • 139
3 votes
2 answers
1k 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), ...
Michaël's user avatar
8 votes
3 answers
611 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 ...
Kuifje's user avatar
  • 13.2k
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 ...
Kuifje's user avatar
  • 13.2k
2 votes
0 answers
93 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 ...
GuglielmoSanchini's user avatar