3
$\begingroup$

For my research, I am interested in finding the trajectory outlined by the pivots along the way of optimizing an LP problem, but I only know how to use Python PuLP to obtain the optimal solution. Is there any way to also obtain the intermediate solutions using PuLP or any solver? I saw Gurobi has callback functions, how would that work? (It is intended for Mixed Integer Problem, but I have just a regular LP problem.) Other programming languages are also okay.

$\endgroup$
1
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Commented Nov 6, 2022 at 22:32

2 Answers 2

3
$\begingroup$

I doubt that Gurobi has a callback to give you all intermediate solutions and even if it did I am not sure that this would be useful for you. Simplex solvers perturb the problem to avoid degeneracy and switch back and forth between primal and dual simplex (not too mention special algorithms like sifting and folding), so you would probably not be able to do much with these intermediate solutions without exactly understanding their context.

It is probably possible to look into one of the open source solvers code (HiGHs, CLP, SoPlex, GLPK) but because of the aforementioned reasons this is not exactly easy without a deep understanding of how modern simplex solvers work and sadly there are no good textbooks for that.

In the end the question remains, what do you want to do with the intermediate solutions? Do you want primal feasible solutions (i.e. heuristic solutions to an LP), those you can get from the iterations of a primal simplex, but the problem might be perturbed. There might be other ways to get those. Or do you want optimality bounds by looking at dual feasible solutions and maybe stop early? Some simplex solvers allow you to do that by setting a stopping bound before you start to solve. If you elaborate on that, maybe I can give a more helpful answer.

$\endgroup$
3
$\begingroup$

I'm not completely sure that its a viable way to go, but Gurobi has a parameter called IterationLimit. As I understand it, it sets an upper limit on the number of simplex iterations performed during the solution process. So in principle, you can set IterationLimit=1 and then switch between solving and expecting the solution returned. You can read about the parameter here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.