SolutionPools with MIQCP problem
Awaiting user inputHi,
I am trying to find multiple solutions to a MIPQCP problem, without an objective.
Using another solver, I know this problem has 109 feasible (and optimal) solutions.
The problem I'm facing using Gurobi is two-fold:
1. When setting the solution-limit close to the full set of feasible solutions (e.g., 100), the solver get's stuck finding solutions
2. When setting the solution limit low (e.g., 35), the solver adds infeasible solutions in the solution pool.
Setting the PoolSearchMode to 1 seems to solve the issue but I do not understand why PoolSearchMode=2 causes this issue.
Kind regards,
Ignace
-
Hello Ignace,
Thank you for reaching out to the community forum.
In order to dig more deeply into your scenario, I do have an initial set of questions:
- You mentioned that the model is type MIQCP. Could you describe the problem that this model is aiming to solve?
- What other solver did you attempt to use to establish that the problem has 109 known feasible solutions?
- Did you adjust any special parameters on that solver? If so, what are they?
- Have you studied the reference here: multiple solutions parameter set?
- When using Gurobi, what set of parameters did you adjust? Only PoolSearchMode?
- How did you determine that the Gurobi solver resulted in infeasible solutions? You mentioned the number 35.
Warm thanks,
Erik H.
0 -
Hi Erik,
Thanks for the quick response.
The model I'm trying to solve is a linear decomposition of the following model: x % y == r; x // y == d, which is implemented through the CPMpy modeling system (see discussion on issue #593). Crucially, the decomposition should adhere to the integer division rules and hence should always round towards zero.
I have attached the `.lp` file generated by Gurobi of the resulting constraints.
A few corrections on my intial post, and the output of `gurobi_cl` when running with certain parameters:
gurobi_cl PoolSearchMode=1 PoolSolutions=110 mod_div.lp
> Outputs solutions where y = 0 (division by zero, so invalid)
gurobi_cl PoolSearchMode=2 PoolSolutions=50 mod_div.lp
> Outputs 50 solutions, all correct
gurobi_cl PoolSearchMode=2 PoolSolutions=100 mod_div.lp
> Timeout
Below I pasted the `mod_div.lp` file:
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
0 y + 0 BV18 + 0 BV19
Subject To
R0: IV19 - d = 0
R1: IV22 - r = 0
R2: BV12 >= 1
R3: - IV30 + IV32 <= -1
R4: - IV29 + IV33 <= 0
R5: - IV28 + x - IV27 = 0
R6: IV18 - IV37 = 0
R7: - IV37 + IV39 <= -1
R8: - IV36 + IV40 <= 0
R9: x - IV35 - IV34 = 0
R10: BV15 >= 1
R11: IV20 + IV43 <= -1
R12: - x + IV42 + IV25 = 0
R13: - IV21 + IV46 <= -1
R14: - x + IV45 + IV26 = 0
R15: - BV12 + BV13 <= 0
R16: - BV12 + BV14 <= 0
R17: - BV15 + BV16 <= 0
R18: - BV15 + BV17 <= 0
qc0: - IV28 + [ IV17 * IV23 ] = 0
qc1: - IV33 + [ IV30 * IV31 ] = 0
qc2: - IV35 + [ IV18 * IV24 ] = 0
qc3: - IV40 + [ IV37 * IV38 ] = 0
qc4: - IV42 + [ IV20 * IV41 ] = 0
qc5: - IV45 + [ IV21 * IV44 ] = 0
GC0: BV13 = 1 -> y - IV17 = 0
GC5: BV13 = 1 -> - IV19 + IV23 = 0
GC6: BV14 = 1 -> y - IV18 = 0
GC10: BV14 = 1 -> - IV19 + IV24 = 0
GC11: BV13 = 0 -> IV17 = -1
GC12: BV14 = 0 -> IV18 = 1
GC13: BV12 = 0 -> IV19 = -5
GC14: BV16 = 1 -> y - IV20 = 0
GC16: BV18 = 1 -> x >= 0
GC17: BV18 = 0 -> x <= -1
GC18: BV18 = 1 -> IV25 >= 0
GC19: BV18 = 0 -> IV25 <= 0
GC20: BV16 = 1 -> - IV22 + IV25 = 0
GC21: BV17 = 1 -> y - IV21 = 0
GC23: BV19 = 1 -> x >= 0
GC24: BV19 = 0 -> x <= -1
GC25: BV19 = 1 -> IV26 >= 0
GC26: BV19 = 0 -> IV26 <= 0
GC27: BV17 = 1 -> - IV22 + IV26 = 0
GC28: BV16 = 0 -> IV20 = -1
GC29: BV17 = 0 -> IV21 = 1
GC30: BV15 = 0 -> IV22 = -4
GC31: BV13 = 0 -> y >= 0
GC32: BV13 = 1 -> y <= -1
GC33: BV14 = 0 -> y <= 0
GC34: BV14 = 1 -> y >= 1
GC35: BV12 = 1 -> BV13 + BV14 >= 1
GC36: BV16 = 0 -> y >= 0
GC37: BV16 = 1 -> y <= -1
GC38: BV17 = 0 -> y <= 0
GC39: BV17 = 1 -> y >= 1
GC40: BV15 = 1 -> BV16 + BV17 >= 1
Bounds
-5 <= IV19 <= 5
-5 <= d <= 5
-4 <= IV22 <= 4
-5 <= r <= 5
-5 <= y <= 5
-5 <= IV17 <= -1
-25 <= IV28 <= 25
-5 <= IV23 <= 5
IV29 <= 5
-5 <= x <= 5
1 <= IV30 <= 5
IV31 <= 5
IV32 <= 4
-4 <= IV27 <= 4
IV33 <= 25
1 <= IV18 <= 5
-25 <= IV35 <= 25
-5 <= IV24 <= 5
IV36 <= 5
1 <= IV37 <= 5
IV38 <= 5
IV39 <= 4
-4 <= IV34 <= 4
IV40 <= 25
-5 <= IV20 <= -1
-45 <= IV42 <= 45
-9 <= IV41 <= 9
IV43 <= 4
-4 <= IV25 <= 4
1 <= IV21 <= 5
-45 <= IV45 <= 45
-9 <= IV44 <= 9
IV46 <= 4
-4 <= IV26 <= 4
Binaries
BV12 BV13 BV14 BV15 BV16 BV18 BV17 BV19
Generals
IV19 d IV22 r y IV17 IV28 IV23 IV29 x IV30 IV31 IV32 IV27 IV33 IV18 IV35
IV24 IV36 IV37 IV38 IV39 IV34 IV40 IV20 IV42 IV41 IV43 IV25 IV21 IV45 IV44
IV46 IV26
General Constraints
GC1: IV29 = ABS ( x )
GC2: IV30 = ABS ( IV17 )
GC3: IV31 = ABS ( IV23 )
GC4: IV32 = ABS ( IV27 )
GC7: IV36 = ABS ( x )
GC8: IV38 = ABS ( IV24 )
GC9: IV39 = ABS ( IV34 )
GC15: IV43 = ABS ( IV25 )
GC22: IV46 = ABS ( IV26 )
End0 -
Hello Ignace,
Thank you for your response.
First, let me express that I am not familiar with the CPMpy implementation, and so I am not sure what conditions (if any are different) are being set there while it is interacting with Gurobi.
I have a few questions for you:
- Are you able to reproduce the results with only using Gurobi alone separate from CPMpy?
- What version of Gurobi are you using?
- In each of the parameter sets that you have explicitly called out ( PoolSearchMode=1 PoolSolutions=110, PoolSearchMode=2 PoolSolutions=50, and PoolSearchMode=2 PoolSolutions=10), are you configuring any other parameter?
- Have you considered https://docs.gurobi.com/projects/optimizer/en/current/reference/parameters.html#numericfocus since you mentioned that there is a linear decomposition of a modulo constraint, and you may be concerned about zero rounding?
- Have you also seen this https://support.gurobi.com/hc/en-us/community/posts/360072283072-Modulo-operation-Constraint?
- Could you share exact steps you took to reproduce scenario PoolSearchMode=1 PoolSolutions=110 that resulted in all solutions y = 0?
Warm thanks,
Erik H.
0
Please sign in to leave a comment.
Comments
3 comments