Testing cutting planes from tableau

Answered

Robert Hildebrand

• August 13, 2020 16:31

I'd like to be able to test the performance of cut generating functions that require access to the rows in the tableau.  

Is there a way to recover the tableau of the LP relaxation?  Most importantly, at the root node, but at other nodes would be great too.

Since I assume you wouldn't show us the version of the problem after presolve, this would just be with presolve turned off.

Also, do you have any code structure setup for testing cutting planes that academics can have access to?

 

0

• 

  Jaromił Najman

  Gurobi Staff

  • September 16, 2020 13:12

  Hi Robert,

  Excuse the late reply. It is not possible to access the cutting planes. However, it is possible to access the presolved model via the Model.presolve() function.

  I am not sure what you mean by "any code structure setup for testing cutting planes". You can add your cuts via callbacks, see Model.cbCut(). Is this what you are looking for?

  Best regards,
  Jaromił

  0
• 

  Robert Hildebrand

  • September 16, 2020 14:41

  

  

  

  1. Thanks.  I didn't know that you could access the presolved model.  That's exciting.

   

  2. Then the question is, if we solve the LP relaxation, is there a way to look at the tabluea.  That is, 

   

  If we have basic variables x_B and non-basic variables x_N,, and x = (x_B, x_N), A = (A_B, A_N)

  (A_B, A_N) (x_B, x_N) = b

  the tabluea records

  x_B = A_B^{-1} b - A_B^{-1} A_N x_N

  I would like to recover the set of basic variables B, and the coefficients A_B^{-1}b, and of A_B^{-1}A_N.

  From this, we can compute a variety of cutting planes to add to the formulation.

  It would also be nice to recover this data within a branch and bound tree, so that we can consider adding cuts at each node.

   

  3.  "any code structure setup for testing cutting planes" - by this I just mean, do you have a database of problem instances that are easy to load and ready to test general techniques on?  

  Of course, I can download all the MIPLIB instances and load those and run some performance measures on them.   But I figure that GUROBI has a whole testing playground that outputs lots of performance measures.  And I'm wondering if you want to make something like that available to basically fasttrack research on general purpose techniques for using GUROBI.

   

  Thanks for your answers!

   

   

   

  0
• 

  Jaromił Najman

  Gurobi Staff

  • September 17, 2020 07:21

  Hi Robert,

  1. Great to hear that we could provide some new insights.

  2. You can obtain variable and constraint basis information via the attributes VBasis and CBasis. With these attributes, you should be able to extract the information you need.

  3. We are testing Gurobi regularly on MIPLIB instances. I think they provide a very good start for testing own algorithms. Please understand that we cannot share more information on our internal test set.

  Best regards,
  Jaromił

  0
• 

  Robert Hildebrand

  • November 19, 2020 16:47

  

  

  

  Is there a python version of  GRBBinvRowi? 

  https://www.gurobi.com/documentation/7.5/refman/c_grbbinvrowi.html

  This is what I want to get access to.   I suppose, if not, I could the B^{-1} matrix based on the VBasis and then create the tableau rows myself.

   

  0
• 

  Jaromił Najman

  Gurobi Staff

  • November 20, 2020 09:09
  • Edited

  Hi Robert,

  The Advanced Simplex Routines are not available in the Python API.

  Best regards,
  Jaromił

  0

Please sign in to leave a comment.