PoolSearchMode with auxiliary variables (extended formulations)?

Answered

Austin Buchanan

• June 07, 2021 23:22

I have become interested in using PoolSearchMode for enumerating all integer feasible solutions of a MIP and have a related question.

For many problems, there are key decision variables, let's call them x. For modeling reasons, it may be convenient to define and use auxiliary variables y. This may give an extended formulation of the form Ax + Gy <= b.

Suppose I am only interested in the different x  solutions, with no interest in the different y's that may come with them. Is there a way to exploit this in Gurobi? Or, is the only approach to apply PoolSearchMode and filter the results to find the distinct x values?

I ask because in my application, a particular x solution may pair with exponentially many y solutions, with significant time savings to be had.

0

• 

  Jaromił Najman

  Gurobi Staff

  • June 14, 2021 09:42
  • Edited

  Hi Austin,

  One way of getting only solutions that differ in the "interesting" variables is to manually filter all the returned solutions in the pool based on your criteria as you already described.

  Another way is the following:

  1. solve the original model
  2. restrict the solution space to the original optimal solution value by adding a new constraint to enforce that, i.e., objective <= optimal solution
  3. set a new objective that only contains the important variables and rewards a different solution than before

  The optimization in step 3 can then be repeated several times to get new solutions that differ in the important variables. You could set an objective like this:

  min x_plus - x_minus

  where \(x_{plus} = \{ x | x = 1 \text{ in original solution} \} \) and \(x_{minus} = \{ x | x = 0 \text{ in original solution} \} \) for all important variables. The above is for binary variables, this works for continuous variables in a similar way, where you would try to reward the difference from the original variables.

  As soon as there is a new solution with a nonzero solution value, you have a new solution differing in the important variables.

  The feature you are asking for is on our future road map and will be implemented in a future release.

   

  Best regards,
  Jaromił

  0
• 

  Austin Buchanan

  • June 14, 2021 14:02

  

  

  

  Hi Jaromił,

  Glad to hear the feature is upcoming! 

  Best,

  Austin

  0
• 

  Maliheh Aramon

  Gurobi Staff

  • November 30, 2021 18:59

  Hi Austin, 

  Gurobi 9.5 was recently released. Included in this release is a new variable attribute named PoolIgnore which can be used to identify variables whose values should be ignored when checking two solutions are distinct in the solution pool.  

  We hope this new variable attribute works well for your application. Please let us know if you find any issues using it. 

  Best regards,

  Maliheh

  0
• 

  Austin Buchanan

  • November 30, 2021 20:22
  • Edited

  

  

  

  Hi Maliheh,

  Thanks for the update. However, it appears that the new functionality in Gurobi 9.5 will not help me. Based on some initial tests, it seems that Gurobi's search process proceeds as usual and simply filters out solutions (x,y) that have the same x. In my intended application, each feasible solution x pairs with exponentially many y's, and the search process should exploit this.

  To illustrate, consider the following toy example.

  max   x_1 + x_2 + ... + x_n
  s.t.  x_1 + x_2 + ... + x_n == 0
                          x_i <= y_i for i=1,2,...,n
        x, y binary.

  This IP has 2^n feasible (and optimal) solutions, all with x=0 and y binary. So, there is really only one feasible solution in the x-space (x=0). However, when I use the new PoolIgnore functionality on the y variables, Gurobi still visits > 2 million BB nodes when n=20. 

  https://github.com/AustinLBuchanan/pool-ignore-test/blob/main/pool_search_test.ipynb

  Austin

  0
• 

  Tobias Achterberg

  Gurobi Staff

  • December 01, 2021 01:26

  Hi Austin,

  yes, your observation is correct. The fix in Gurobi 9.5 just means that those solutions are discarded from the solution pool. It does not mean that they are already pruned in the search tree and thus reducing the amount of search.

  What you describe may lead to an algorithmic improvement that I could try to implement. On the one hand, one could check at a given search tree node whether all variables that are interesting for the solution pool are fixed. If so, and there is already a feasible solution with these values in the pool, and the remaining variables cannot contribute to an improvement in the objective function, then we can prune the tree at this node. On the other hand, one should probably try to avoid branching on the variables that should be ignored for the pool in order to trigger more often the situation above where one can prune the search tree.

   

  Regards,

  Tobias

   

  0

Please sign in to leave a comment.