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
5 votes
1 answer
122 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 ...
  • 10.9k
3 votes
1 answer
70 views

Creating constraints dynamically in pyomo abstract model

I have a networkX graph with few nodes and these nodes have attributes such as "demand". ...
4 votes
3 answers
178 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
616 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 ...
  • 151
3 votes
1 answer
67 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 ...
2 votes
1 answer
90 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 ...
6 votes
0 answers
74 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)$ ...
5 votes
1 answer
213 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
2 answers
214 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 ...
1 vote
1 answer
102 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
111 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
62 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) ...
1 vote
1 answer
131 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
69 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,256
1 vote
0 answers
72 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
511 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), ...
8 votes
3 answers
442 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 ...
  • 10.9k
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 ...
  • 10.9k
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 ...
7 votes
3 answers
391 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
26 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 ...
2 votes
1 answer
67 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
219 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, ...
  • 6,206
4 votes
1 answer
135 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 ...
2 votes
1 answer
115 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 ...
  • 533
2 votes
1 answer
177 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
45 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
139 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 ...
6 votes
2 answers
221 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 ...
5 votes
4 answers
230 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$ ...
4 votes
0 answers
212 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 ...
4 votes
1 answer
193 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 ...
5 votes
1 answer
161 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 (...
  • 659
2 votes
2 answers
92 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 $...
4 votes
2 answers
285 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 ...
5 votes
2 answers
280 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 ...
  • 1,256
7 votes
2 answers
522 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 ...
3 votes
2 answers
91 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 ...
  • 927
1 vote
1 answer
191 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 ...
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 ...
  • 31
4 votes
1 answer
78 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?
1 vote
0 answers
45 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?
0 votes
1 answer
401 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 ...
9 votes
2 answers
475 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 "...
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 ...
  • 443
2 votes
0 answers
149 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,...
  • 443
5 votes
2 answers
295 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 ...
3 votes
0 answers
97 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 ...
2 votes
1 answer
92 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 ...
  • 305
1 vote
1 answer
94 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 $...
  • 113