Different solutions from the pool Solutions
AnsweredHi, I want to retrieve many solutions from the PoolSolutions of an IP(Integer Program), and the problem is that the most of solutions are almost the same with the same objetive value but different variable values.
Variables: "x", and "y" are binary variables and z is an integer variable. The most important variable for me is "y" and as you can see all the solutions have the same solution just with different z values.
Using the bellow code :
cont=0
for aa in range(p.SolCount):
cont+=1
p.Params.SolutionNumber = aa
print("solution: ", cont)
for v in p.getVars():
if v.xn > 1e5:
print ('%s %g' % (v.varName, v.xn))
I get this:
Solution: 1 
x[0,2] 1 
y[0] 1 
y[2] 1 
Solution: 2 
x[0,2] 1 
y[0] 1 
y[2] 1 
z[0,2,0] 4 
z[2,0,0] 4 
Solution: 3 
x[0,2] 1 
y[0] 1 
y[2] 1 
z[0,2,0] 2 
z[2,0,0] 2 
Solution: 4 
x[0,2] 1 
y[0] 1 
y[2] 1 
z[0,2,0] 6 
z[2,0,0] 6 

Hi Mishelle,
Here are a few ideas:
 Can you add any constraints to prevent multiple nonzero values of \( z \) at an optimal solution?
 Set PoolSearchMode to 2. Gurobi will find the \( n \) best solutions to your problem, where \( n \) is determined by the PoolSolutions parameter.
 Let \( y^* \) be the optimal \( y \) vector obtained after solving, and let \( S = \{i \colon y^*_i = 1\} \). You can add a disjunctive cut to cut off all solutions with the same \( y \) variable values as \( y^* \), then resolve the problem. In general, the cut you would add is:
$$\begin{align*}\sum_{i \in S} (1  y_i) + \sum_{i \notin S} y_i &\geq 1.\end{align*}$$
For example, if your solution has \( y^*_0 = 1 \), \( y^*_1 = 0 \), and \( y^*_2 = 1 \), you have \( S = \{0, 2\} \). Thus, you add the inequality \( (1  y_0) + y_1 + (1  y_2) \geq 1 \) to the model. This inequality removes all solutions with \( y = (1, 0, 1) \), but does not affect any other solutions. When you resolve the problem, the new solution will have different \( y \) values (if such a solution exists). You can repeat this process as many times as you want to find a set of solutions with unique \( y \) values.
Thanks,
Eli
1 
Hi Eli,
Thanks for this detailed description of cut implementation.
Is there on top of this a possibility to retrieve something like "the most different" result on a predefined KPI?
Thanks,
Markus0 
I guess this depends on the KPI. "Most different" suggests the KPI should be incorporated into the objective function. As an example: instead of adding the constraint
$$\begin{align*}\sum_{i \in S} (1  y_i) + \sum_{i \notin S} y_i \geq 1,\end{align*}$$
we could maximize the expression
$$\begin{align*}\sum_{i \in S} (1  y_i) + \sum_{i \notin S} y_i\end{align*}$$
to find the solution that is the farthest distance from \( y^* \) (with respect to the L1 norm). To maximize the L1 distance from \( y^* \) from among the optimal solutions to your model, you can use the above expression as the second objective in a hierarchical multiobjective optimization model.
1
Please sign in to leave a comment.
Comments
3 comments