メインコンテンツへスキップ

Gurobi is returning infeasible solutions

回答済み
Abhinav Patil
  • Gurobi-versary
  • First Comment
  • First Question

I am trying to solve a binary integer programming problem with a given objective function and n variables subject to the constraint that the sum of the n variables is exactly n/2 (n.b.: in practice, n will always be even). That is, exactly half the variables should be 0 and the other half 1. However, Gurobi seems to be incapable of returning solutions where the sum is greater than (n/2) - 1. For example, when n=50, even when I hardcode a constraint asking for a sum of 25, or 26, etc., it will nonetheless return a solution where the sum is 24. I can, however, ask for the sum to be 24 or less, and it will respond correctly. Why is such a basic feasibility restriction being violated? Vexingly, Gurobi does not even inform me it has decided to violate the constraint and I had to discover this myself. The relevant bits of code follow, in Java, with try/catch blocks excised:

GRBVar[] indicator_T_gur = new GRBVar[n];      
for (int i = 0; i < n; i++) {
   indicator_T_gur[i] = model.addVar(0.0, 1.0, 0.0, GRB.BINARY, Integer.toString(i));
}

// set objective (code not here)

GRBLinExpr expr = new GRBLinExpr();
for (int i = 0; i < n; i++) {
    expr.addTerm(1.0, indicator_T_gur[i]);
}

model.addConstr(expr, GRB.EQUAL, n / 2, "c0");
1

コメント

5件のコメント

日付 投票
  • 正式なコメント
    Simranjit Kaur
    • Gurobi Staff
    編集済み
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Eli Towle
    • Gurobi Staff

    Hi Abhinav,

    I wasn't able to replicate this. Your code seems to behave as expected for any integer value of n (when taking into account integer division).

    • Are you recompiling the Java code after making changes to it? If so, could you post a complete minimal working example of the code that does not behave as expected?
    • You can examine the model visually after writing an LP file with (e.g.) GRBModel.write("model.lp"). This is useful for making sure the model the right constraints are being added to the model. If you try this, you should change the variable names to something nonnumeric, i.e., "x" + Integer.toString(i).

    Thanks,

    Eli

    0
  • Abhinav Patil
    • Gurobi-versary
    • First Comment
    • First Question

    Hi Eli,

     

    Thank you for your message. It is difficult to post a minimal working example because of the complexity of the other pieces of code not included here but I will try to do so ASAP. I printed the model file and I have pasted it below. As you can see, the restriction that the sum of the variables be twelve (i.e. n/2) is clearly present. Nonetheless, when I ran this and asked Gurobi to return up to 1000 optimal and non-optimal solutions, it returned 8 solutions with sum = (n/2) - 1 and 992 solutions that actually met the criterion, i.e. sum = n/2. The most optimal solution fell in the latter category, i.e. it was infeasible.

     

    \ LP format - for model browsing. Use MPS format to capture full model detail.
    Minimize
    [ 3.1399967810167586e+06 w0 ^2 + 3.2255692477860283e+06 w0 * w1
    + 1.4875920223413866e+06 w0 * w2 + 2.1248289548024428e+06 w0 * w3
    + 3.4632926412964482e+06 w0 * w4 + 2.3866478809016431e+06 w0 * w5
    + 2.1225923828341383e+06 w0 * w6 + 3.2302819496047543e+06 w0 * w7
    - 7.2561037383694639e+06 w0 * w8 - 3.3522104207593007e+06 w0 * w9
    + 5.0055219022411797e+06 w0 * w10 + 5.3082910418805927e+06 w0 * w11
    - 1.4955370552992821e+06 w0 * w12 - 3.1438294723215601e+06 w0 * w13
    - 4.786654371751396e+06 w0 * w14 + 4.0899094445776162e+06 w0 * w15
    + 3.891611304153021e+06 w0 * w16 - 4.0013709618129018e+06 w0 * w17
    + 2.7322501383829042e+06 w0 * w18 - 1.1111023066756792e+07 w0 * w19
    - 786651.8482496147 w0 * w20 - 5.8189382372789187e+06 w0 * w21
    - 9.8997939306332301e+06 w0 * w22 + 5.0185151492168242e+06 w0 * w23
    + 828368.4425381735 w1 ^2 + 764066.2419664105 w1 * w2
    + 1.0913678279626726e+06 w1 * w3 + 1.7788378490362929e+06 w1 * w4
    + 1.2258448888341303e+06 w1 * w5 + 1.0902190659949793e+06 w1 * w6
    + 1.6591574522171109e+06 w1 * w7 - 3.7269250113133891e+06 w1 * w8
    - 1.7217831098871042e+06 w1 * w9 + 2.5709672084059371e+06 w1 * w10
    + 2.7264773719678391e+06 w1 * w11 - 768147.019076847 w1 * w12
    - 1.6147531945749593e+06 w1 * w13 - 2.4585511097725309e+06 w1 * w14
    + 2.1006846584071042e+06 w1 * w15 + 1.9988335374897742e+06 w1 * w16
    - 2.0552089736901566e+06 w1 * w17 + 1.4033552640734343e+06 w1 * w18
    - 5.7069125886120815e+06 w1 * w19 - 404045.0018560792 w1 * w20
    - 2.9887591519847708e+06 w1 * w21 - 5.0847935665286416e+06 w1 * w22
    + 2.5776408805139638e+06 w1 * w23 + 176188.8768734 w2 ^2
    + 503325.1341392426 w2 * w3 + 820377.6728965265 w2 * w4
    + 565344.2655150783 w2 * w5 + 502795.3395487583 w2 * w6
    + 765182.5771282162 w2 * w7 - 1.7188110032050246e+06 w2 * w8
    - 794064.7438365293 w2 * w9 + 1.1856977839031289e+06 w2 * w10
    + 1.2574171180536749e+06 w2 * w11 - 354259.756893564 w2 * w12
    - 744703.8912429897 w2 * w13 - 1.1338528912149377e+06 w2 * w14
    + 968809.3788239908 w2 * w15 + 921836.9211571328 w2 * w16
    - 947836.5642295198 w2 * w17 + 647209.8209577535 w2 * w18
    - 2.6319564042365672e+06 w2 * w19 - 186340.4798519104 w2 * w20
    - 1.3783781806092192e+06 w2 * w21 - 2.345042925372838e+06 w2 * w22
    + 1.1887755976547443e+06 w2 * w23 + 359466.776722688 w3 ^2
    + 1.1718012782162859e+06 w3 * w4 + 807519.7008029411 w3 * w5
    + 718176.8117654986 w3 * w6 + 1.0929623654698953e+06 w3 * w7
    - 2.4550947656298564e+06 w3 * w8 - 1.1342167303613273e+06 w3 * w9
    + 1.6936128622934236e+06 w3 * w10 + 1.7960544696249659e+06 w3 * w11
    - 506013.3273529837 w3 * w12 - 1.0637112643133127e+06 w3 * w13
    - 1.6195592726747415e+06 w3 * w14 + 1.3838163884270736e+06 w3 * w15
    + 1.3167224294451757e+06 w3 * w16 - 1.3538594895967783e+06 w3 * w17
    + 924453.8467200407 w3 * w18 - 3.759402505195858e+06 w3 * w19
    - 266162.7926842001 w3 * w20 - 1.9688313898165335e+06 w3 * w21
    - 3.349584451417102e+06 w3 * w22 + 1.6980091132000585e+06 w3 * w23
    + 954968.8069564066 w4 ^2 + 1.3161892542794147e+06 w4 * w5
    + 1.1705678528691027e+06 w4 * w6 + 1.7814368111798356e+06 w4 * w7
    - 4.0015981598301656e+06 w4 * w8 - 1.8486779592388046e+06 w4 * w9
    + 2.7604466467425255e+06 w4 * w10 + 2.9274178582520643e+06 w4 * w11
    - 824759.2019388949 w4 * w12 - 1.7337599743424775e+06 w4 * w13
    - 2.6397455185842761e+06 w4 * w14 + 2.2555044273624849e+06 w4 * w15
    + 2.1461469123059106e+06 w4 * w16 - 2.2066771996270316e+06 w4 * w17
    + 1.5067820858368278e+06 w4 * w18 - 6.1275101708724499e+06 w4 * w19
    - 433822.9857074812 w4 * w20 - 3.2090297192599326e+06 w4 * w21
    - 5.4595411813147198e+06 w4 * w22 + 2.7676121662916774e+06 w4 * w23
    + 453510.6645529633 w5 ^2 + 806669.7143028103 w5 * w6
    + 1.2276359033786324e+06 w5 * w7 - 2.757608656715617e+06 w5 * w8
    - 1.2739735826179641e+06 w5 * w9 + 1.9022978483631304e+06 w5 * w10
    + 2.0173621901311553e+06 w5 * w11 - 568363.694736677 w5 * w12
    - 1.1947805159218628e+06 w5 * w13 - 1.8191194624807616e+06 w5 * w14
    + 1.554328617149096e+06 w5 * w15 + 1.478967419409612e+06 w5 * w16
    - 1.5206804644589159e+06 w5 * w17 + 1.0383639630282116e+06 w5 * w18
    - 4.2226316627524653e+06 w5 * w19 - 298959.059127501 w5 * w20
    - 2.2114284793314813e+06 w5 * w21 - 3.7623163101234147e+06 w5 * w22
    + 1.9072358001387392e+06 w5 * w23 + 358710.4333118629 w6 ^2
    + 1.0918119251092738e+06 w6 * w7 - 2.4525105594423758e+06 w6 * w8
    - 1.1330228661025716e+06 w6 * w9 + 1.6918301837185652e+06 w6 * w10
    + 1.794163962122594e+06 w6 * w11 - 505480.7031994074 w6 * w12
    - 1.0625916133452873e+06 w6 * w13 - 1.617854542107095e+06 w6 * w14
    + 1.3823597982687736e+06 w6 * w15 + 1.3153364616621789e+06 w6 * w16
    - 1.3524344317460696e+06 w6 * w17 + 923480.7766030827 w6 * w18
    - 3.7554453987936266e+06 w6 * w19 - 265882.6326083608 w6 * w20
    - 1.9667590191973224e+06 w6 * w21 - 3.3460587150642648e+06 w6 * w22
    + 1.696221807179061e+06 w6 * w23 + 830790.7779576954 w7 ^2
    - 3.7323702164631858e+06 w7 * w8 - 1.7242987124893381e+06 w7 * w9
    + 2.5747235071886256e+06 w7 * w10 + 2.7304608780973097e+06 w7 * w11
    - 769269.3164376421 w7 * w12 - 1.6171124216546724e+06 w7 * w13
    - 2.462143163576494e+06 w7 * w14 + 2.1037538532219543e+06 w7 * w15
    + 2.0017539232337554e+06 w7 * w16 - 2.0582117264832703e+06 w7 * w17
    + 1.4054056292639682e+06 w7 * w18 - 5.7152506447099689e+06 w7 * w19
    - 404635.3297854521 w7 * w20 - 2.9931258635972901e+06 w7 * w21
    - 5.0922226787404688e+06 w7 * w22 + 2.5814069298319118e+06 w7 * w23
    + 4.1919661972496067e+06 w8 ^2 + 3.873250239128639e+06 w8 * w9
    - 5.7835387613966791e+06 w8 * w10 - 6.1333678279871671e+06 w8 * w11
    + 1.7279909462699003e+06 w8 * w12 + 3.6324802822762546e+06 w8 * w13
    + 5.5306522750480603e+06 w8 * w14 - 4.7256110881716581e+06 w8 * w15
    - 4.4964911274848357e+06 w8 * w16 + 4.6233109170914544e+06 w8 * w17
    - 3.1569284661592878e+06 w8 * w18 + 1.2838028449458623e+07 w8 * w19
    + 908922.4949827763 w8 * w20 + 6.7233857932791356e+06 w8 * w21
    + 1.1438535890137862e+07 w8 * w22 - 5.7985515710472371e+06 w8 * w23
    + 894691.5784264359 w9 ^2 - 2.6719076247903714e+06 w9 * w10
    - 2.8335233740674965e+06 w9 * w11 + 798305.7389922807 w9 * w12
    + 1.6781510703960019e+06 w9 * w13 + 2.5550778845643112e+06 w9 * w14
    - 2.1831610056038769e+06 w9 * w15 - 2.0773110415581705e+06 w9 * w16
    + 2.1358998704402307e+06 w9 * w17 - 1.4584533081977274e+06 w9 * w18
    + 5.9309753969904277e+06 w9 * w19 + 419908.4755682506 w9 * w20
    + 3.1061027697048839e+06 w9 * w21 + 5.2844309551955033e+06 w9 * w22
    - 2.6788433162812958e+06 w9 * w23 + 1.9948467515389489e+06 w10 ^2
    + 4.2310182026683651e+06 w10 * w11 - 1.1920304395168549e+06 w10 * w12
    - 2.5058158300915966e+06 w10 * w13 - 3.8152432895968985e+06 w10 * w14
    + 3.2598968614845611e+06 w10 * w15 + 3.1018416540604951e+06 w10 * w16
    - 3.1893265161024746e+06 w10 * w17 + 2.1777630462488243e+06 w10 * w18
    - 8.8561347663147859e+06 w10 * w19 - 627007.4988065625 w10 * w20
    - 4.6380338621010911e+06 w10 * w21 - 7.8907143547155187e+06 w10 * w22
    + 4.000049880305897e+06 w10 * w23 + 2.2434699579680366e+06 w11 ^2
    - 1.2641328171799947e+06 w11 * w12 - 2.6573851804588302e+06 w11 * w13
    - 4.0460160143729304e+06 w11 * w14 + 3.4570783317370415e+06 w11 * w15
    + 3.289462834676466e+06 w11 * w16 - 3.3822393959516603e+06 w11 * w17
    + 2.3094894589443803e+06 w11 * w18 - 9.3918160311449878e+06 w11 * w19
    - 664933.3184650731 w11 * w20 - 4.9185747426470481e+06 w11 * w21
    - 8.3680002088135527e+06 w11 * w22 + 4.2420010063678361e+06 w11 * w23
    + 178075.9057855632 w12 ^2 + 748681.256589764 w12 * w13
    + 1.1399086500888856e+06 w12 * w14 - 973983.662047532 w12 * w15
    - 926760.3306742603 w12 * w16 + 952898.8344140892 w12 * w17
    - 650666.4833228081 w12 * w18 + 2.6460133365549399e+06 w12 * w19
    + 187335.6997990323 w12 * w20 + 1.3857399168305169e+06 w12 * w21
    + 2.3575674906097786e+06 w12 * w22 - 1.1951246914661261e+06 w12 * w23
    + 786916.7104557701 w13 ^2 + 2.3962484896013285e+06 w13 * w14
    - 2.04745080133902e+06 w13 * w15 - 1.9481807094168984e+06 w13 * w16
    + 2.0031275247622507e+06 w13 * w17 - 1.3677925663384607e+06 w13 * w18
    + 5.5622926106318589e+06 w13 * w19 + 393806.0191549869 w13 * w20
    + 2.9130204270548099e+06 w13 * w21 + 4.95593882726161e+06 w13 * w22
    - 2.5123203833812908e+06 w13 * w23 + 1.824210474762623e+06 w14 ^2
    - 3.1173571643942217e+06 w14 * w15 - 2.9662129551848401e+06 w14 * w16
    + 3.0498725226652692e+06 w14 * w17 - 2.0825398848616024e+06 w14 * w18
    + 8.4688983534404039e+06 w14 * w19 + 599591.4599713467 w14 * w20
    + 4.4352348258464411e+06 w14 * w21 + 7.5456911586640533e+06 w14 * w22
    - 3.8251468319850983e+06 w14 * w23 + 1.3317974851098985e+06 w15 ^2
    + 2.5344512968460121e+06 w15 * w16 - 2.6059333861288214e+06 w15 * w17
    + 1.7794055894385797e+06 w15 * w18 - 7.2361663639880344e+06 w15 * w19
    - 512314.9875823655 w15 * w20 - 3.789642492301309e+06 w15 * w21
    - 6.4473411152921999e+06 w15 * w22 + 3.2683588452424258e+06 w15 * w23
    + 1.2057845595710778e+06 w16 ^2 - 2.4795854188835272e+06 w16 * w17
    + 1.6931315962785082e+06 w16 * w18 - 6.8853228176390463e+06 w16 * w19
    - 487475.53557838 w16 * w20 - 3.6059027129050475e+06 w16 * w21
    - 6.1347435453043105e+06 w16 * w22 + 3.1098933608510513e+06 w16 * w23
    + 1.2747600308729466e+06 w17 ^2 - 1.7408849636773379e+06 w17 * w18
    + 7.0795176167278793e+06 w17 * w19 + 501224.3773102227 w17 * w20
    + 3.7076041975576701e+06 w17 * w21 + 6.3077688807598799e+06 w17 * w22
    - 3.1976053145812391e+06 w17 * w23 + 594362.9356425728 w18 ^2
    - 4.8340964066039044e+06 w18 * w19 - 342250.2905469866 w18 * w20
    - 2.5316578189132293e+06 w18 * w21 - 4.307124373575991e+06 w18 * w22
    + 2.1834160458095046e+06 w18 * w23 + 9.8292165724789146e+06 w19 ^2
    + 1.3918018776723202e+06 w19 * w20 + 1.0295290327893823e+07 w19 * w21
    + 1.7515438134268843e+07 w19 * w22 - 8.8791233674068749e+06 w19 * w23
    + 49269.24878519741 w20 ^2 + 728898.6006099643 w20 * w21
    + 1.2400794866899871e+06 w20 * w22 - 628635.0740018538 w20 * w23
    + 2.6958659968994064e+06 w21 ^2 + 9.1729854298592694e+06 w21 * w22
    - 4.6500731899930947e+06 w21 * w23 + 7.8030270971541693e+06 w22 ^2
    - 7.911196934240181e+06 w22 * w23 + 2.0052165702191803e+06 w23 ^2 ] / 2
    Subject To
    c0: w0 + w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8 + w9 + w10 + w11 + w12
    + w13 + w14 + w15 + w16 + w17 + w18 + w19 + w20 + w21 + w22 + w23 = 12
    Bounds
    Binaries
    w0 w1 w2 w3 w4 w5 w6 w7 w8 w9 w10 w11 w12 w13 w14 w15 w16 w17 w18 w19 w20
    w21 w22 w23
    End

    0
  • Eli Towle
    • Gurobi Staff
    編集済み

    Hi Abhinav,

    Thanks for posting the example. When solving this model and printing the solution, I see the following:

    w0 -0.0
    w1 1.0
    w2 -0.0
    w3 1.0
    w4 -0.0
    w5 -0.0
    w6 0.9999957654892611
    w7 -0.0
    w8 -0.0
    w9 1.0
    w10 -0.0
    w11 1.0
    w12 -0.0
    w13 1.0
    w14 1.0
    w15 1.0
    w16 -0.0
    w17 1.0
    w18 -0.0
    w19 -0.0
    w20 1.0
    w21 1.0
    w22 4.234510738895927e-06
    w23 1.0

    How are you checking which variables assume a value of \( 1 \)? Gurobi decides a variable is at an integer value if satisfies the tolerance specified with the IntFeasTol parameter. You can read more about this here.

    In the above case, the value of \( w_6 \) is effectively \( 1 \), and the value of \( w_{22} \) is effectively \( 0 \). Could you try using a tolerance when checking which variables take on a value of \( 1 \)? E.g., if you want to print the names of all such variables, you could do something like

    for (int i=0; i<n; i++) {
        if (indicator_T_gur[i].get(GRB.DoubleAttr.X) > 1 - 1e-5) {
            System.out.println(indicator_T_gur[i].get(GRB.StringAttr.VarName));
        }
    }

    Do you think this could be the issue? Thanks!

    Eli

    0
  • Abhinav Patil
    編集済み
    • Gurobi-versary
    • First Comment
    • First Question

    The answer, as it turns out, is because at some point in the code (not in my excerpt above), I was casting the floats to integers. I was not aware that Gurobi was in fact sometimes generating solutions with small fractional differences from 0 or 1, but I realized that was the case once I wrote the solution to file. Thus this issue is simply an artifact of truncation. Thank you for your help.

    0

投稿コメントは受け付けていません。

お探しのものを見つけられませんでしたか？

新規投稿