Suppose we are given a simple, undirected graph G with n vertices and for every edge e of G define the binary variable x_e which is subject to some additional constraints.

I would like to express the diameter of the graph induced by the picked edges (possibly using the objective function) as a linear program. One way to do this is to introduce, for every pair of vertices s,t of G and edge e, the binary variable y_{s,t,e} indicating that e is an edge on a path from s to t. From here it is not hard to find appropriate constraints to enforce this meaning on y_{s,t,e} and be able to express the diameter of G.

Unfortunately, this approach produces a large number of binary variables and makes modeling problems in this way hopeless for graphs of reasonable order.

Hence, I am wondering

What would be a simple and efficient way to express the diameter of the graph induced by the edges of G selected by the variables x_e?

asked 09 Jun '16, 15:35

Jernej's gravatar image

Jernej
154
accept rate: 0%


You could try adding a multicommodity flow structure. For each distinct pair of nodes, assign a "commodity" (indexed by \(k\)) to flow between them. Arbitrarily make one node the source, with supply 1, and the other the sink, with demand 1. Let \(y^k_e \in [0, 1]\) be the flow of commodity \(k\) over edge \(e\), constrained by \(y^k_e \le x_e\) (you can only use selected edges). Add the usual flow balance constraints for each commodity at each node. Use an auxiliary variable \(z^k = \sum_e d_e y^k_e\) to track the total distance covered by commodity \(k\), where \(d_e\) is the length of edge \(e\). Finally, use variable \(\delta\) to represent the diameter of the graph, constrained by \(\delta \ge z^k \forall k\).

There are two issues with this approach (beside the possibility of an excessive number of variables and constraints, if the graph has too many nodes). First, a selection of edges that results in a disconnected graph will be an infeasible solution. I don't know if that's what you want. Second, there's no guarantee that \(z^k\) is the length of a shortest path between the node pair indexed by \(k\). That's survivable as long as something in the model puts downward pressure on \(\delta\), in which case \(\delta\) should be the correct diameter and at least one \(k\) for which \(\delta = z^k\) should have \(z^k\) be the length of an actual shortest path. (For other \(k\), \(z^k\) might overestimate shortest path length, but it won't affect \(\delta\).)

link

answered 10 Jun '16, 11:04

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 10 Jun '16, 11:06

If your motivation is to constrain the diameter to be no more than \(d\), you might consider omitting the \(y\) variables and instead dynamically imposing violated "no-good" cuts of the form \(\sum_{e \in P} x_e \le |P|-1\), where \(P\) is a path of length \(d+1\).

link

answered 09 Jun '16, 17:40

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

edited 09 Jun '16, 17:41

Right. Though I would like to avoid dynamic cuts

(09 Jun '16, 17:47) Jernej

On second thought, my suggestion is too restrictive in the sense that it cuts off valid solutions. It is OK to have long paths if you also have at least one short enough path between each pair of nodes.

(14 Nov '16, 00:27) Rob Pratt

Your binary-variable-intense approach would, I think, require that \(y_{s,t,e}\) indicate that edge \(e\) is on a (unique) shortest path from \(s\) to \(t\). If you include inefficient paths, or even multiple shortest paths, I don't see a way to get the diameter accurately.

I can suggest a method using Benders decomposition, but I really have no idea if it would be efficient. I'll assume that the diameter is \(\infty\) if the graph is disconnected. Add a variable \(d \ge 0\) to your model (which becomes the Benders master), representing the graph diameter. Given a proposed incumbent \((\hat{x}, \hat{d})\), compute the shortest distances between all pairs of nodes in the graph induced by \(\hat{x}\). Let \(\delta\) be the largest of those distances, assuming the induced graph is connected. If \(\hat{d} \ge \delta\), accept the incumbent. Otherwise, let \(S = \sum_{e:\hat{x}_e = 0} x_e \). If the graph is connected, add the constraint \( d \ge \delta (1 - S) \) to the master. If the graph is disconnected, add the constraint \( S \ge 1 \) instead.

The cuts generated by the subproblem don't look all that deep to me, and I think finding all shortest distances is \(O(n^3)\) where \(n\) is the number of vertices, so it may not prove to be an efficient approach.

link

answered 09 Jun '16, 17:58

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 09 Jun '16, 18:12

Hm is there any slick way to avoid dynamic constraints? What I was looking for is whether there are some MTZ type constraints?

(10 Jun '16, 02:56) Jernej
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×101

Asked: 09 Jun '16, 15:35

Seen: 1,198 times

Last updated: 14 Nov '16, 00:27

OR-Exchange! Your site for questions, answers, and announcements about operations research.