Skip to main content

SolutionPools with MIQCP problem

Awaiting user input

Comments

3 comments

  • Erik Halseth
    • Gurobi Staff Gurobi Staff

    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:

     

    1. You mentioned that the model is type MIQCP. Could you describe the problem that this model is aiming to solve?
    2. What other solver did you attempt to use to establish that the problem has 109 known feasible solutions?
    3. Did you adjust any special parameters on that solver? If so, what are they?
    4. Have you studied the reference here: multiple solutions parameter set?
    5. When using Gurobi, what set of parameters did you adjust? Only PoolSearchMode?
    6. How did you determine that the Gurobi solver resulted in infeasible solutions? You mentioned the number 35.

     

    Warm thanks,

     

    Erik H.

    0
  • Ignace Bleukx
    • First Comment
    • Gurobi-versary
    • First Question

    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 )
    End

    0
  • Erik Halseth
    • Gurobi Staff Gurobi Staff

    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:

    1. Are you able to reproduce the results with only using Gurobi alone separate from CPMpy?
    2. What version of Gurobi are you using?
    3. 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?
    4. 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?
    5. Have you also seen this https://support.gurobi.com/hc/en-us/community/posts/360072283072-Modulo-operation-Constraint?
    6. 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.