What is wrong with my LP exercise (longest path cost for a graph)

I have to do a linear programming exercise but i have some problems regarding the result. I have a graph with N nodes and E edges, that is not acyclic, and each edge is associated to a cost. I have also two nodes (marked as B and E), and I have to find the maximum path cost from B to E. Also, each edge can be used at most k times and the total cost of the path must be at most C.

I have inserted also the constraint regarding the balance of each node as follow (where E are the edges and x[i,j] tells me how many times an edges is been used, and the two nodes B and E):

$\sum\nolimits_{j |(j,i) \in Edges} x(j,i) -\sum\nolimits_{j | (i,j) \in Edges} x(i,j) =0$

$\sum\nolimits_{j | (j,B) \in Edges} x(j,B) -\sum\nolimits_{j | (B,j) \in Edges} x(B,j) =-1$

$\sum\nolimits_{j | (j,E) \in Edges} x(j,E) -\sum\nolimits_{j | (E,j) \in Edges} x(E,j) =1$

The objective function is: $max \sum\nolimits_{(i,j) \in Edges} x(i,j)*cost(i,j)$

Other constraints:

$x(i,j) <= K \forall (i,j) \in Edges$

$\sum\nolimits_{(i,j) \in Edges} x(i,j)*cost(i,j) <= C$

When i run the LP solver the solution that it gives me, of course it includes a path from B to E, but also an other cyclic path that not includes nodes B and E.

Any suggestion?

• 1) What is ampl? 2) Tool support questions are offtopic here. 3) Have you tried executing the algorithm yourself? That'll help debugging. 4) You can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction.
– Raphael
Jan 28 '16 at 18:28
• AMPL is a only a tool, but i am interesting only in the contraints shown above and how can i change in order to make the model proper. Jan 28 '16 at 18:38
• You should be able to go further in diagnosing this yourself. The solution includes another path. Well, does that other solution satisfy all of the inequalities? See if you can articulate why you are you unhappy with it. What additional inequalities could you add to rule out that unwanted solution? Then, edit the question to include that information. We discourage "please check my answer" or "please debug my answer" questions here, as they're unlikely to help anyone else ever again in the future.
– D.W.
Jan 28 '16 at 18:49
• Ok, now i'll describe all the model, thank you for the suggestion Jan 28 '16 at 18:54
• This is roughly the equivalent of finding a cycle cover of a graph when you're looking for a Hamiltonian cycle. Jun 4 '20 at 5:47

1 Answer

You are on a fool's errand: Longest Path is NP-hard, thus there is no LP for solving it.

• If "each edge can be used at most k times" is to be non-trivial, then his problem must also allow re-use of nodes, in which case I don't see a reduction from his problem to the standard Longest Path problem. ​ ​
– user12859
Jan 28 '16 at 22:41
• @RickyDemer The reduction from HamPath only needs $k=1$, doesn't it? What am I missing? (We want to reduce normal Longest Path to this one in order to show that this one is hard, and $k=1$ seems to work as well.)
– Raphael
Jan 29 '16 at 8:02
• "each edge can be used at most 1 time" would follow automatically from "each node can be used at most 1 time". ​ (I did have the relevant direction of reduction backwards.) ​ ​ ​ ​
– user12859
Jan 29 '16 at 8:06
• So is there no solution for my problem? Jan 29 '16 at 8:52
• @Dan11 There is, but (as far as I can tell) probably not a fast and general and exact one. See here for some ideas.
– Raphael
Jan 29 '16 at 9:40