2

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.)

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Shuxue Jiaoshou
  • 155
  • 7
  • 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. – A.Omidi Sep 18 '22 at 08:34
  • Yes, I know, but my question is specifically about re-optimisation (warm start) using GLPK. – Shuxue Jiaoshou Sep 18 '22 at 11:16
  • Are you interested all, just some, or some specific alternative optima? – Sune Sep 18 '22 at 13:28
  • To Sune -- I am interested in all OEP (optimal extreme points). – Shuxue Jiaoshou Sep 18 '22 at 21:33
  • 1
    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: https://yetanothermathprogrammingconsultant.blogspot.com/2016/01/finding-all-optimal-lp-solutions.html (there I enumerate all optimal bases, but this can be adapted to enumerate all feasible bases). – Erwin Kalvelagen Sep 20 '22 at 14:06
  • I was hoping to avoid Integer Programming since it is NP-hard! But thanks anyway.. I'm now also looking at CDD software developed by Komei Fukuda at ETH Zurich. – Shuxue Jiaoshou Sep 22 '22 at 02:57
  • Had too many problems installing polymake in Ubuntu Linux.. so had to abandon that. – Shuxue Jiaoshou Sep 24 '22 at 06:39

0 Answers0