Model ignores indicator contraints
回答済みHi everyone,
i have the following code snippet (the rest of the code should not be interesting):
int numOfPolygons = 8;
x0 = new GRBVar[numOfPolygons];
y0 = new GRBVar[numOfPolygons];
polygonPicked = new GRBVar[numOfPolygons];
for (int i=0; i<numOfPolygons; i++) {
x0[i] = m.addVar(-GRB.INFINITY, GRB.INFINITY, 0, GRB.CONTINUOUS, "x0_"+i);
y0[i] = m.addVar(-GRB.INFINITY, GRB.INFINITY, 0, GRB.CONTINUOUS, "y0_"+i);
polygonPicked[i] = m.addVar(0, 1, 0, GRB.BINARY, "polygonPicked_"+i);
}
double s = -0.32491969623290656;
double px = 1.790603396872017E-16;
double py = -3.0;
double b = -4.2532540417602;
// lhs = s*x0[6] + s*px - y0[6] - py
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(s, x0[6]);
lhs.addConstant(s*px);
lhs.addTerm(-1, y0[6]);
lhs.addConstant(-py);
double rhs = -b;
// if (polygonPicked[6]==1) --> lhs <= rhs
m.addGenConstrIndicator(polygonPicked[6], 1, lhs, GRB.LESS_EQUAL, rhs, "");
//m.addGenConstrIndicator(polygonPicked[i], 1, lhs, GRB.LESS_EQUAL, rhs, "");
System.out.print(s+"x0+"+s*px+"-y0-"+py+" < "+rhs) //-0.32491969623290656x0+1.790603396872017E-16-y0--3.0 < 4.2532540417602
m.optimize();
System.out.println(polygonPicked[6].get(GRB.DoubleAttr.X)); // 1.0
System.out.println(x0[6].get(GRB.DoubleAttr.X)); // -1.447008760521422
System.out.println(y0[6].get(GRB.DoubleAttr.X)); // -2.0
System.out.println(s*x0[6].get(GRB.DoubleAttr.X)+s*px-y0[6].get(GRB.DoubleAttr.X)-py); //5.470161646914975
The problem is: 5.470161646914975 is greater than 4.2532540417602, but it should be smaller because I set "GRB.LESS_EQUAL".
I don't understand this, because polygonPicked[6].get(GRB.DoubleAttr.X) is 1, so the Indicator Constraint should avoid a solution like this.
Hopefully you can helpf me. What have I done wrong?
Thanks a lot.
-
正式なコメント
-
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?. -
-
-
Hi Peter,
You should try writing out the LP file of this model to check whether it matches your mathematical formulation.
You should also not use small values like these:
double px = 1.790603396872017E-16;
They may just be ignored by the solver because they are too close to zero.
The line
m.addGenConstrIndicator(polygonPicked[i], 1, lhs, GRB.LESS_EQUAL, rhs, "");
seems out of place, because you are using variable \(\texttt{i}\) that was only used within the for-loop above.
I hope that helps to resolve the issue.
Cheers,
Matthias0 -
-
Thanks for your answer Matthias,
the variable i was a mistake in the post, sorry for that. I corrected it now.
In the LP file I can find the correct constraint. For the problematic constraint I can find this line
polygonPicked_6 = 1 -> - 0.3249196962329066 x0_6 - y0_6 <= 1.2532540417602
which is the same like above.
I don't understand this. The problem shouldn't be there.
0 -
-
-
I don't understand your problem. Please check the solution values and try to figure out what seems to be off. You should also try writing (and sharing) a minimal reproducible example code so we can investigate this ourselves.
Cheers,
Matthias0 -
-
Hello again,
It took me some time to create a minimal example (unfortunately it didn't get quite as small as I had hoped, but most of it is just some kind of constants).
I was trying to find the bug, but in my opinion the output just doesn't make sense.The problem is that I get the following as the solution parameters:
polygonPicked = {1, 0}
x0 = {-1.4470087605214221, -1.1473074930075313}
y0 = {-2.0, 1.2349799773212569}However, this cannot be a valid solution!
For example, there is a constraint with the name "c-ContainerLine_3-Polygon_0-Point_0".
The following applies to this constraint, if PolygonPicked[0] is equal to 1:
- 0.3249196962329066 * x0 [0] - y0 [0] <= 1.2532540417602If we now insert the solution parameters, this results in:
2.47016164691497516080294024847586 <= 1.2532540417602,
which is obviously wrong!Although the corresponding IndicatorConstraint is present in the model, it is not fulfilled by the solution. But that can't be correct, can it?
I hope my problem has become clearer now.
//CONSTS
int numOfEntries = 2; // = area.length
double[] area = {11.691342951089924, 11.69134295108992};
int numOfLines = 5; // = slope.length, sense.length, b.length
double[] slope = {
-1.3763819204711734,
0.3249196962329061,
6.617873607995638E15,
-0.32491969623290656,
1.3763819204711734
};
char[] sense = {
GRB.GREATER_EQUAL,
GRB.GREATER_EQUAL,
GRB.GREATER_EQUAL,
GRB.LESS_EQUAL,
GRB.LESS_EQUAL
};
double[] b = {
6.881909602355867,
4.253254041760199,
2.67698610774696E16,
-4.2532540417602,
-6.881909602355867
};
int numOfPolygonPoints = 3;
//double[][][] rhs = new double[numOfLines][numOfEntries][numOfPolygonPoints];
double[][][] rhs = {
{
{-9.881909602355867, -1.8059644770429197, -8.957854727668812},
{-6.083482977512322, -2.915430560430493, -11.646815269124787}
},
{
{-7.253254041760199, -3.597420175143059, -1.9090879083773384},
{-7.063833146961924, -1.607762779435001, -4.088166198883671}
},
{
{-2.67698610774696E16, -4.3963601068146008E16, -9.576121086793198E15},
{-4.08084909932172E16, -3.190835626096142E16, -7.592735978230184E15}
},
{
{1.2532540417601996, 6.597420175143059, 4.909087908377342},
{2.8211924598426408, 7.40331773716941, 2.5352519282685493}
},
{
{3.8819096023558677, 4.805964477042917, 11.957854727668815},
{1.8408422903930348, 8.7109855181649, 10.093900998509666}
}
};
//CREATE VARIABLES
GRBVar[] x0 = new GRBVar[numOfEntries];
GRBVar[] y0 = new GRBVar[numOfEntries];
GRBVar[] polygonPicked = new GRBVar[numOfEntries];
/* Go through each Polygon */
for (int i=0; i<numOfEntries; i++) {
x0[i] = m.addVar(-GRB.INFINITY, GRB.INFINITY, 0, GRB.CONTINUOUS, "x0_"+i);
y0[i] = m.addVar(-GRB.INFINITY, GRB.INFINITY, 0, GRB.CONTINUOUS, "y0_"+i);
polygonPicked[i] = m.addVar(0, 1, 0, GRB.BINARY, "polygonPicked_"+i);
}
/* Maximal one polygon should be picked */
for (int i=0; i<numOfEntries; i+=numOfEntries) {
GRBLinExpr lhs = new GRBLinExpr();
for (int j=i; j<numOfEntries; j++) {
lhs.addTerm(1, polygonPicked[j]);
}
m.addConstr(lhs, GRB.LESS_EQUAL, 1, "c-onlyOneDirection_"+i);
}
// SET OBJECTIVE FUNCTIONS
GRBLinExpr objectiveFunction = new GRBLinExpr();
for (int i=0; i<numOfEntries; i++) {
objectiveFunction.addTerm(area[i], polygonPicked[i]);
}
m.setObjective(objectiveFunction, GRB.MAXIMIZE);
//CONSTRAINTS
for (int k=0; k<numOfLines; k++) {
for (int i=0; i<numOfEntries; i++) {
for (int j=0; j<numOfPolygonPoints; j++) {
/* Create linear expressions for Constr */
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(slope[k], x0[i]);
lhs.addTerm(-1, y0[i]);
/* if (polygonPicked[i] == 1) {create Constr} */
m.addGenConstrIndicator(polygonPicked[i], 1, lhs, sense[k], rhs[k][i][j], "c-ContainerLine_"+k+"Polygon_"+i+"-Point_"+j);
}
}
}
/* Solve */
m.optimize();0 -
-
-
Hi Peter,
There are numerical issues in your model. Please review the coefficients and right-hand sides of these constraints:
c-ContainerLine_2-Polygon_0-Point_0: polygonPicked_0 = 1 ->
6.617873607995638e+15 x0_0 - y0_0 >= -2.67698610774696e+16
c-ContainerLine_2-Polygon_0-Point_1: polygonPicked_0 = 1 ->
6.617873607995638e+15 x0_0 - y0_0 >= -4.3963601068146008e+16
c-ContainerLine_2-Polygon_0-Point_2: polygonPicked_0 = 1 ->
6.617873607995638e+15 x0_0 - y0_0 >= -9.576121086793198e+15
c-ContainerLine_2-Polygon_1-Point_0: polygonPicked_1 = 1 ->
6.617873607995638e+15 x0_1 - y0_1 >= -4.08084909932172e+16
c-ContainerLine_2-Polygon_1-Point_1: polygonPicked_1 = 1 ->
6.617873607995638e+15 x0_1 - y0_1 >= -3.190835626096142e+16
c-ContainerLine_2-Polygon_1-Point_2: polygonPicked_1 = 1 ->
6.617873607995638e+15 x0_1 - y0_1 >= -7.592735978230184e+15These cause final violations in the solution as reported by Gurobi:
Warning: max constraint violation (1.2169e+00) exceeds toleranceFor this specific instance, you can resolve the issue by using aggressive presolving (Presolve=2). This makes Gurobi solve the instance entirely in presolving and no LP needs to be solved. This is most likely not going to work with other, larger instances.
Please consult our Guide on Numerics for further information on how to avoid such issues.
Cheers,
Matthias1 -
投稿コメントは受け付けていません。
コメント
6件のコメント