Solution to Optimisation problem
Answered
Hello
I have a simple optimization problem that includes a 2-norm constraint on a vector. When I read the .lp problem below and solve it with gurobi, then I get the answer that some norm variables take the value 1.0, when the 2-norm of the vector [0,0,0,0,0,1,-1,0] should be sqrt(2).
However, if I add a lower bound to the norm variables, such as (lb = -100) (which wouldn't make much sense), then it gives me the correct norm, i.e. sqrt(2). The lower bound I added with:
```
norm[intersection_1_1] >= -100
norm[intersection_1_2] >= -100
norm[intersection_2_1] >= -100
```
And the solution I get is
```
Best objective 2.000000000000e+00, best bound 2.000000000000e+00, gap 0.0000% norm[intersection_1_1] 1.0 norm[intersection_1_2] 1.0 norm[intersection_2_1] 0.0 z[0] -0.0 z[1] -0.0 z[2] -0.0 z[3] -0.0 z[4] -0.0 z[5] 0.0 z[6] 1.0 z[7] 0.0 diff[intersection_1_1,0] 0.0 diff[intersection_1_1,1] 0.0 diff[intersection_1_1,2] 0.0 diff[intersection_1_1,3] 0.0 diff[intersection_1_1,4] 0.0 diff[intersection_1_1,5] 1.0 diff[intersection_1_1,6] -1.0 diff[intersection_1_1,7] 0.0 diff[intersection_1_2,0] 0.0 diff[intersection_1_2,1] 0.0 diff[intersection_1_2,2] 0.0 diff[intersection_1_2,3] 0.0 diff[intersection_1_2,4] 0.0 diff[intersection_1_2,5] 0.0 diff[intersection_1_2,6] -1.0 diff[intersection_1_2,7] 1.0 diff[intersection_2_1,0] 0.0 diff[intersection_2_1,1] 0.0 diff[intersection_2_1,2] 0.0 diff[intersection_2_1,3] 0.0 diff[intersection_2_1,4] 0.0 diff[intersection_2_1,5] 0.0 diff[intersection_2_1,6] 0.0 diff[intersection_2_1,7] 0.0
```
I don't know where the issue is and would appreciate any help to solve it. Thanks
```
Minimize
[ 2 norm[intersection_1_1] ^2 + 2 norm[intersection_1_2] ^2
+ 2 norm[intersection_2_1] ^2 ] / 2
Subject To
z_constr: z[0] + z[1] + z[2] + z[3] + z[4] + z[5] + z[6] + z[7] = 1
diff_intersection_1_1[0]: z[0] + diff[intersection_1_1,0] = 0
diff_intersection_1_1[1]: z[1] + diff[intersection_1_1,1] = 0
diff_intersection_1_1[2]: z[2] + diff[intersection_1_1,2] = 0
diff_intersection_1_1[3]: z[3] + diff[intersection_1_1,3] = 0
diff_intersection_1_1[4]: z[4] + diff[intersection_1_1,4] = 0
diff_intersection_1_1[5]: z[5] + diff[intersection_1_1,5] = 1
diff_intersection_1_1[6]: z[6] + diff[intersection_1_1,6] = 0
diff_intersection_1_1[7]: z[7] + diff[intersection_1_1,7] = 0
diff_intersection_1_2[0]: z[0] + diff[intersection_1_2,0] = 0
diff_intersection_1_2[1]: z[1] + diff[intersection_1_2,1] = 0
diff_intersection_1_2[2]: z[2] + diff[intersection_1_2,2] = 0
diff_intersection_1_2[3]: z[3] + diff[intersection_1_2,3] = 0
diff_intersection_1_2[4]: z[4] + diff[intersection_1_2,4] = 0
diff_intersection_1_2[5]: z[5] + diff[intersection_1_2,5] = 0
diff_intersection_1_2[6]: z[6] + diff[intersection_1_2,6] = 0
diff_intersection_1_2[7]: z[7] + diff[intersection_1_2,7] = 1
diff_intersection_2_1[0]: z[0] + diff[intersection_2_1,0] = 0
diff_intersection_2_1[1]: z[1] + diff[intersection_2_1,1] = 0
diff_intersection_2_1[2]: z[2] + diff[intersection_2_1,2] = 0
diff_intersection_2_1[3]: z[3] + diff[intersection_2_1,3] = 0
diff_intersection_2_1[4]: z[4] + diff[intersection_2_1,4] = 0
diff_intersection_2_1[5]: z[5] + diff[intersection_2_1,5] = 0
diff_intersection_2_1[6]: z[6] + diff[intersection_2_1,6] = 1
diff_intersection_2_1[7]: z[7] + diff[intersection_2_1,7] = 0
Bounds
-2 <= diff[intersection_1_1,0] <= 2
-2 <= diff[intersection_1_2,0] <= 2
-2 <= diff[intersection_2_1,0] <= 2
-2 <= diff[intersection_1_1,1] <= 2
-2 <= diff[intersection_1_2,1] <= 2
-2 <= diff[intersection_2_1,1] <= 2
-2 <= diff[intersection_1_1,2] <= 2
-2 <= diff[intersection_1_2,2] <= 2
-2 <= diff[intersection_2_1,2] <= 2
-2 <= diff[intersection_1_1,3] <= 2
-2 <= diff[intersection_1_2,3] <= 2
-2 <= diff[intersection_2_1,3] <= 2
-2 <= diff[intersection_1_1,4] <= 2
-2 <= diff[intersection_1_2,4] <= 2
-2 <= diff[intersection_2_1,4] <= 2
-2 <= diff[intersection_1_1,5] <= 2
-2 <= diff[intersection_1_2,5] <= 2
-2 <= diff[intersection_2_1,5] <= 2
-2 <= diff[intersection_1_1,6] <= 2
-2 <= diff[intersection_1_2,6] <= 2
-2 <= diff[intersection_2_1,6] <= 2
-2 <= diff[intersection_1_1,7] <= 2
-2 <= diff[intersection_1_2,7] <= 2
-2 <= diff[intersection_2_1,7] <= 2
Binaries
z[0] z[1] z[2] z[3] z[4] z[5] z[6] z[7]
General Constraints
normconstr_intersection_1_1: norm[intersection_1_1] = NORM ( 2 ) (
diff[intersection_1_1,0] , diff[intersection_1_1,1] ,
diff[intersection_1_1,2] , diff[intersection_1_1,3] ,
diff[intersection_1_1,4] , diff[intersection_1_1,5] ,
diff[intersection_1_1,6] , diff[intersection_1_1,7] )
normconstr_intersection_1_2: norm[intersection_1_2] = NORM ( 2 ) (
diff[intersection_1_2,0] , diff[intersection_1_2,1] ,
diff[intersection_1_2,2] , diff[intersection_1_2,3] ,
diff[intersection_1_2,4] , diff[intersection_1_2,5] ,
diff[intersection_1_2,6] , diff[intersection_1_2,7] )
normconstr_intersection_2_1: norm[intersection_2_1] = NORM ( 2 ) (
diff[intersection_2_1,0] , diff[intersection_2_1,1] ,
diff[intersection_2_1,2] , diff[intersection_2_1,3] ,
diff[intersection_2_1,4] , diff[intersection_2_1,5] ,
diff[intersection_2_1,6] , diff[intersection_2_1,7] )
End
``
-
Hi Vinzenz,
I can't seem to reproduce your issue. Solving the LP file you posted, with Gurobi v11, the running:
for v in m.getVars():
print(v.varname, v.X, v.lb)I get the following output:
norm[intersection_1_1] 1.4142135623730931 0.0
norm[intersection_1_2] 0.0 0.0
norm[intersection_2_1] 1.4142135603441 0.0Can you provide some more details on how you are running this (including Gurobi version)?
- Riley
0 -
Hi Riley,
Thanks for your answer. I'm using Gurobi 11.0.0.
I'll share some code, so you can see what I do exactly. It is not exactly the same problem, but a condensed version that gives me the same error:
import gurobipy as gp
from gurobipy import GRB
import numpy as np
env = gp.Env(empty=True)
env.setParam("OutputFlag", 0)
env.start()
# Create a new model
model = gp.Model("norm_objective_example", env=env)
x1 = np.array([0, 1, 0, 0, 0, 0, 0, 0])
x2 = np.array([0, 0, 1, 0, 0, 0, 0, 0])
n = len(x1)
# Define the variables
z = model.addVars(n, vtype=GRB.BINARY, name="z")
diff = model.addVars(2, n, vtype = GRB.CONTINUOUS, lb=-2, ub=2, name="diff")
norm = model.addVars(2, vtype = GRB.CONTINUOUS, name="norm")
# Add constraints
model.addConstr(z.sum() == 1)
for i in range(n):
model.addConstr(diff[0, i] == x1[i] - z[i])
model.addConstr(diff[1, i] == x2[i] - z[i])
# Add the norm constraint
model.addGenConstrNorm(norm[0], diff.select(0, "*"), 2.0, "normconstr0")
model.addGenConstrNorm(norm[1], diff.select(1, "*"), 2.0, "normconstr1")
# Set the objective
model.setObjective(norm[0] + norm[1], GRB.MINIMIZE)
# Optimize the model
model.optimize()
print("Z:", [z_val.X for z_val in z.select()])
print("Diff 1:", [dif.X for dif in diff.select(0, "*")])
print("Diff 2:", [dif.X for dif in diff.select(1, "*")])
print("Norm 0:", norm[0].X)
print("Norm 1:", norm[1].X)Z: [-0.0, 0.0, 1.0, -0.0, -0.0, -0.0, -0.0, -0.0] Diff 1: [0.0, 1.0, -1.0, 0.0, 0.0, 0.0, 0.0, 0.0] Diff 2: [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0] Norm 0: 1.0 Norm 1: 0.0
0 -
Hi Vinzenz,
Thanks for the simplified model, I can confirm I can replicate your results with v11.
I note that when output is turned on the log indicates there are issues with the solution:
Warning: max constraint violation (4.1421e-01) exceeds tolerance
Warning: max general constraint violation (4.1421e-01) exceeds tolerance
(model may be infeasible or unbounded - try turning presolve off)Setting Presolve=0 as suggested gives the expected answer. Additionally the mention of "infeasible or unbounded" immediately brings to mind dual reductions and setting DualReductions=0 also resolves the issue.
But this outcome is still not ideal, and there does not seem to be an issue with v10 so I will open a support request for this, as it will make it easier for us to look into this internally. You will receive a notification shortly.
- Riley
0 -
Hi Riley,
Thanks for opening a request and your help.
0
Please sign in to leave a comment.
Comments
4 comments