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

Solution to Optimisation problem

回答済み
Vinzenz Tütsch
編集済み
  • Gurobi-versary
  • First Comment
  • First Question

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
``

0

コメント

5件のコメント

日付 投票
  • 正式なコメント
    Simranjit Kaur
    • Gurobi Staff
    This post is more than two 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 try Gurobot, our chatbot interface offering instant, expert-level support.
  • Riley Clement
    • Gurobi Staff

    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.0

    Can you provide some more details on how you are running this (including Gurobi version)?

    - Riley

    0
  • Vinzenz Tütsch
    • Gurobi-versary
    • First Comment
    • First Question

    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
  • Riley Clement
    • Gurobi Staff

    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
  • Vinzenz Tütsch
    • Gurobi-versary
    • First Comment
    • First Question

    Hi Riley, 

    Thanks for opening a request and your help. 

    0

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

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

新規投稿