2
$\begingroup$

My question is kind of related to this 2015 post at Stackoverflow.

About Simplex method tableau pivoting in Linear Programming -- this is proving to be difficult in GLPK.. I am using Linux, GLPK 5.0 version, in C language.. I want to do this so as to obtain multiple (alternate) basic optimal solutions (Optimal BFS, or Optimal Extreme Points).

Is it sufficient to specify the variable entering the basis? Or do I need to specify both the entering variable and the variable leaving the basis?

What I have tried so far:

probA = glp_create_prob();
glp_read_lp(probA, NULL, "Model-Old.lp");   // Read original LP model (in CPLEX LP format)
glp_read_sol(probA, "basic-solution-old.txt");  // Load basic solution created earlier
glp_set_col_stat(probA, 2, GLP_BS);   // Set variable x2 to enter the basis
glp_set_col_stat(probA, 4, GLP_NL);   // Set x4 to leave the basis (and become zero)
glp_simplex(probA, GLP_OFF);   // Turn off Pre-solver and solve the new problem.

Unfortunately the above doesn't work (I have tried with different entering and leaving variables).. How can I fix the code above? Or is there a better way to do re-optimisation in GLPK (with C language)? Thanks.

Edit: I looked up my favourite book in Linear Programming, by George Hadley (this was the textbook we followed 35 years ago, in 1987!).. In Section 5-7 (Page 166), he describes a method to reach alternate optimal BFS by pivoting.. I'm trying to implement this (don't know if there are better approaches now).

(I've just been reading this answer a few months ago from Henrik Friberg.)

$\endgroup$
7
  • $\begingroup$ One possible way to achieve multiple optimal solutions is, you would need to check the optimal tableau of the simplex iterations. (usually the last one). If there exist non-basic variables with the zero reduced cost it might be a signal to existing such a solution. $\endgroup$
    – A.Omidi
    Commented Sep 18, 2022 at 8:34
  • $\begingroup$ Yes, I know, but my question is specifically about re-optimisation (warm start) using GLPK. $\endgroup$ Commented Sep 18, 2022 at 11:16
  • $\begingroup$ Are you interested all, just some, or some specific alternative optima? $\endgroup$
    – Sune
    Commented Sep 18, 2022 at 13:28
  • $\begingroup$ To Sune -- I am interested in all OEP (optimal extreme points). $\endgroup$ Commented Sep 18, 2022 at 21:33
  • 1
    $\begingroup$ Interestingly, you can enumerate all basic feasible solutions by encoding the basis with binary variables (1=basic,0=non-basic). Then use no-good constraints to forbid a previous solution. See: yetanothermathprogrammingconsultant.blogspot.com/2016/01/… (there I enumerate all optimal bases, but this can be adapted to enumerate all feasible bases). $\endgroup$ Commented Sep 20, 2022 at 14:06

0

Your Answer

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