Boost logo

Boost Users :

Subject: [Boost-users] Boost graph library algorithms - is it possible to use previous solutions to "warm start" a new related problem
From: F1E2D3 F1E2D3 (3d2e1f_at_[hidden])
Date: 2017-10-29 11:03:35


I am primarily an Operations Researcher, and prior to boost, was writing my
own C++ code for specific network flow problems. I am now hoping to
transition to boost::graph completely for my network flow problem solution
needs. However, I have one major concern.

In linear programming (I use CPLEX as my primary linear
programming (LP) solver), once a problem is solved, say a Dijkstra's
shortest path problem, the solver maintains the optimal basis. Then, if
some problem parameter changes, the linear program need not be solved from
scratch, but the current basis is first tested for optimality for the new
problem as well.

An example of this would be an increase in the cost of an arc that does not
feature on the optimal path from source to destination in a shortest path
problem. This increase in cost does not change the optimal path, and hence,
it would be wasteful to solve this problem again from scratch.

Does boost::graph have this capability that LP solvers have?

I posted this question first on stack overflow and am posting it here now.
The question was not completely answered there. A working code and small
example are provided there. I am giving the link below.

Any help will be appreciated.


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at