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) &lt;= K \forall (i,j) \in Edges$

$\sum\nolimits_{(i,j) \in Edges} x(i,j)*cost(i,j) &lt;= 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?
You are on a fool's errand: Longest Path is NP-hard, thus there is no LP for solving it.