Boost graph library algorithms - is it possible to use previous solutions to "warm start" a new related problem

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Boost graph library algorithms - is it possible to use previous solutions to "warm start" a new related problem

Boost - Users mailing list
Hello,

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 https://www.ibm.com/us-en/marketplace/ibm-ilog-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.

Thanks.

_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users