Different solutions from the pool Solutions

Answered

Mishelle Cordero

• July 07, 2020 23:24

Hi, 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 > 1e-5:
                    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

0

• 

  Eli Towle

  Gurobi Staff

  • July 08, 2020 02:22
  • Edited

  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 re-solve 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 re-solve 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
• 

  Markus Groissböck

  • January 15, 2021 11:25

  

  

  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,
  Markus

  0
• 

  Eli Towle

  Gurobi Staff

  • January 19, 2021 00:01

  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 multi-objective optimization model.

  1

Please sign in to leave a comment.