• Gurobi Staff

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ł

Hi Jaromił,

Glad to hear the feature is upcoming!

Best,

Austin

• Gurobi Staff

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

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

• Gurobi Staff

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