I am trying to use GLPK for solving an LP problem. My problem is the routing problem in a computer network. Given network topology and each link capacity and the traffic demand matrix for each source-destination pair in the network, I want to minimize maximum link utilization in the network. This is an LP problem and I know how to use GLPK to get the optimum solution.
My problem is that I want to get the sub-optimal solutions also. Is there any way that I can get say top 10 suboptimal solutions by GLPK?
Best
For a pure LP (with only continuous variables), the concept of finding "next best" solutions is very difficult (just move an epsilon away, and you have another solution). We can define this differently: find "next best" corner points (a.k.a. bases). This is not so easy to do, but there is a somewhat complex way by encoding bases using binary variables (link).
If the problem is actually a MIP (with binary variables) it is easier to find "next best" solutions. Some advanced solvers have built-in facilities for this (called: solution pool). Note: glpk does not have this option. Alternatively, we can also do this by adding a cut that forbids the best-found solution and then resolve (link). In this case we exploited some structure. A general cut for 0-1 variables is derived here. This can also be done for general integer variables, but then things get a bit messy.