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

addMVar() many times slower than addVars

回答済み
Yonzheng Jerry Chua
First Comment
First Question

Hello, I am running some experiments for a project that I am working on, which looks at simulating linear optimization problems, and it seems that using addMVar() results in a massive difference in time compared to addVars().

 

is there a reason why this is so?

関連するエンティティ

0

コメント

3件のコメント

日付 投票
  • Marika Karbstein
    Gurobi Staff Gurobi Staff

    Do you talk about model building time?
    Can you share more details, i.e., can you provide a small example where addMVar() takes longer than addVars()? 
    Did you check that both of your versions result in the same optimization model?

    0
  • Yonzheng Jerry Chua
    • 編集済み
    First Comment
    First Question

    Hi Marika, yes I am talking about model building time. I have outputted the optimization model and they both result in the same model being formulated. Let me provide an example. 

    This is the time it takes to construct the program using MVar()

    0.1376807689666748

    and this is the time it takes to construct the same program using addVars()

    0.005897998809814453



    The model for addVars is defined by

    \ LP format - for model browsing. Use MPS format to capture full model detail.
    Minimize
      k[0] + k[1] + k[2] + k[3] + k[4]
    Subject To
     L1-norm-reformulation-a[0]: theta[0] - k[0] <= -7
     L1-norm-reformulation-a[1]: theta[1] - k[1] <= -2
     L1-norm-reformulation-a[2]: theta[2] - k[2] <= -3
     L1-norm-reformulation-a[3]: theta[3] - k[3] <= -7
     L1-norm-reformulation-a[4]: theta[4] - k[4] <= 7
     L1-norm-reformulation-b[0]: - theta[0] - k[0] <= 7
     L1-norm-reformulation-b[1]: - theta[1] - k[1] <= 2
     L1-norm-reformulation-b[2]: - theta[2] - k[2] <= 3
     L1-norm-reformulation-b[3]: - theta[3] - k[3] <= 7
     L1-norm-reformulation-b[4]: - theta[4] - k[4] <= -7
     Capacity_Constraint: 6 x[0] + 20 x[1] + 13 x[2] + 48 x[3] + 10 x[4] <= 90
     <=1_Constraint_1: - x[0] >= -1
     nonnegativity_1: x[0] >= 0
     <=1_Constraint_2: - x[1] >= -1
     nonnegativity_2: x[1] >= 0
     <=1_Constraint_3: - x[2] >= -1
     nonnegativity_3: x[2] >= 0
     <=1_Constraint_4: - x[3] >= -1
     nonnegativity_4: x[3] >= 0
     <=1_Constraint_5: - x[4] >= -1
     nonnegativity_5: x[4] >= 0
     additional_constraint_[0]: 10 x[0] + 7 x[1] + x[2] + x[3] + 2 x[4] >= 4.2
     additional_constraint_[1]: 4 x[0] + 4 x[1] + 9 x[2] + 10 x[3] + x[4]
       >= 5.6
     additional_constraint_[2]: 9 x[0] + 4 x[1] + 9 x[2] + 7 x[3] + 4 x[4]
       >= 6.6
     additional_constraint_[3]: 8 x[0] + 10 x[1] + 5 x[2] + x[3] + 3 x[4]
       >= 5.4
     additional_constraint_[4]: 7 x[0] + 6 x[1] + 5 x[2] + 3 x[3] + 4 x[4]
       >= 5
     additional_constraint_[5]: 6 x[0] + 2 x[1] + 2 x[2] + 7 x[3] + 2 x[4]
       >= 3.8
     additional_constraint_[6]: 6 x[0] + 6 x[1] + 10 x[2] + 5 x[3] + x[4]
       >= 5.6
     additional_constraint_[7]: 8 x[0] + 9 x[1] + 2 x[2] + 7 x[3] + 2 x[4]
       >= 5.6
     additional_constraint_[8]: 9 x[0] + 5 x[1] + 10 x[2] + 6 x[3] + 10 x[4]
       >= 8
     additional_constraint_[9]: 4 x[0] + 2 x[1] + x[2] + 4 x[3] + 5 x[4]
       >= 3.2
     dual_feasibility_1: - theta[0] - y[0] + y[5]
       + 10 additional_vars_associated_dual[0]
       + 4 additional_vars_associated_dual[1]
       + 9 additional_vars_associated_dual[2]
       + 8 additional_vars_associated_dual[3]
       + 7 additional_vars_associated_dual[4]
       + 6 additional_vars_associated_dual[5]
       + 6 additional_vars_associated_dual[6]
       + 8 additional_vars_associated_dual[7]
       + 9 additional_vars_associated_dual[8]
       + 4 additional_vars_associated_dual[9] = 0
     dual_feasibility_2: - theta[1] - y[1] + y[6]
       + 7 additional_vars_associated_dual[0]
       + 4 additional_vars_associated_dual[1]
       + 4 additional_vars_associated_dual[2]
       + 10 additional_vars_associated_dual[3]
       + 6 additional_vars_associated_dual[4]
       + 2 additional_vars_associated_dual[5]
       + 6 additional_vars_associated_dual[6]
       + 9 additional_vars_associated_dual[7]
       + 5 additional_vars_associated_dual[8]
       + 2 additional_vars_associated_dual[9] = 0
     dual_feasibility_3: - theta[2] - y[2] + y[7]
       + additional_vars_associated_dual[0]
       + 9 additional_vars_associated_dual[1]
       + 9 additional_vars_associated_dual[2]
       + 5 additional_vars_associated_dual[3]
       + 5 additional_vars_associated_dual[4]
       + 2 additional_vars_associated_dual[5]
       + 10 additional_vars_associated_dual[6]
       + 2 additional_vars_associated_dual[7]
       + 10 additional_vars_associated_dual[8]
       + additional_vars_associated_dual[9] = 0
     dual_feasibility_4: - theta[3] - y[3] + y[8]
       + additional_vars_associated_dual[0]
       + 10 additional_vars_associated_dual[1]
       + 7 additional_vars_associated_dual[2]
       + additional_vars_associated_dual[3]
       + 3 additional_vars_associated_dual[4]
       + 7 additional_vars_associated_dual[5]
       + 5 additional_vars_associated_dual[6]
       + 7 additional_vars_associated_dual[7]
       + 6 additional_vars_associated_dual[8]
       + 4 additional_vars_associated_dual[9] = 0
     dual_feasibility_5: - theta[4] - y[4] + y[9]
       + 2 additional_vars_associated_dual[0]
       + additional_vars_associated_dual[1]
       + 4 additional_vars_associated_dual[2]
       + 3 additional_vars_associated_dual[3]
       + 4 additional_vars_associated_dual[4]
       + 2 additional_vars_associated_dual[5]
       + additional_vars_associated_dual[6]
       + 2 additional_vars_associated_dual[7]
       + 10 additional_vars_associated_dual[8]
       + 5 additional_vars_associated_dual[9] = 0
     big-M-complementary_y[0]: y[0] - 1e+15 delta[0] <= 0
     big-M-complementary_y[1]: y[1] - 1e+15 delta[1] <= 0
     big-M-complementary_y[2]: y[2] - 1e+15 delta[2] <= 0
     big-M-complementary_y[3]: y[3] - 1e+15 delta[3] <= 0
     big-M-complementary_y[4]: y[4] - 1e+15 delta[4] <= 0
     big-M-complementary_y[5]: y[5] - 1e+15 delta[5] <= 0
     big-M-complementary_y[6]: y[6] - 1e+15 delta[6] <= 0
     big-M-complementary_y[7]: y[7] - 1e+15 delta[7] <= 0
     big-M-complementary_y[8]: y[8] - 1e+15 delta[8] <= 0
     big-M-complementary_y[9]: y[9] - 1e+15 delta[9] <= 0
     big-M-complementary_additional_var[0]: additional_vars_associated_dual[0]
       - 1e+15 delta[10] <= 0
     big-M-complementary_additional_var[1]: additional_vars_associated_dual[1]
       - 1e+15 delta[11] <= 0
     big-M-complementary_additional_var[2]: additional_vars_associated_dual[2]
       - 1e+15 delta[12] <= 0
     big-M-complementary_additional_var[3]: additional_vars_associated_dual[3]
       - 1e+15 delta[13] <= 0
     big-M-complementary_additional_var[4]: additional_vars_associated_dual[4]
       - 1e+15 delta[14] <= 0
     big-M-complementary_additional_var[5]: additional_vars_associated_dual[5]
       - 1e+15 delta[15] <= 0
     big-M-complementary_additional_var[6]: additional_vars_associated_dual[6]
       - 1e+15 delta[16] <= 0
     big-M-complementary_additional_var[7]: additional_vars_associated_dual[7]
       - 1e+15 delta[17] <= 0
     big-M-complementary_additional_var[8]: additional_vars_associated_dual[8]
       - 1e+15 delta[18] <= 0
     big-M-complementary_additional_var[9]: additional_vars_associated_dual[9]
       - 1e+15 delta[19] <= 0
     big-M-complementary-A_1[0]: - x[0] + 1e+15 delta[0]
       <= 9.99999999999999e+14
     big-M-complementary-A_1[1]: - x[1] + 1e+15 delta[1]
       <= 9.99999999999999e+14
     big-M-complementary-A_1[2]: - x[2] + 1e+15 delta[2]
       <= 9.99999999999999e+14
     big-M-complementary-A_1[3]: - x[3] + 1e+15 delta[3]
       <= 9.99999999999999e+14
     big-M-complementary-A_1[4]: - x[4] + 1e+15 delta[4]
       <= 9.99999999999999e+14
     big-M-complementary-A_2[5]: x[0] + 1e+15 delta[5] <= 1e+15
     big-M-complementary-A_2[6]: x[1] + 1e+15 delta[6] <= 1e+15
     big-M-complementary-A_2[7]: x[2] + 1e+15 delta[7] <= 1e+15
     big-M-complementary-A_2[8]: x[3] + 1e+15 delta[8] <= 1e+15
     big-M-complementary-A_2[9]: x[4] + 1e+15 delta[9] <= 1e+15
     big-M-complementary-additional_constraints[0]: 10 x[0] + 7 x[1] + x[2]
       + x[3] + 2 x[4] + 1e+15 delta[10] <= 1.0000000000000042e+15
     big-M-complementary-additional_constraints[1]: 4 x[0] + 4 x[1] + 9 x[2]
       + 10 x[3] + x[4] + 1e+15 delta[11] <= 1.0000000000000056e+15
     big-M-complementary-additional_constraints[2]: 9 x[0] + 4 x[1] + 9 x[2]
       + 7 x[3] + 4 x[4] + 1e+15 delta[12] <= 1.0000000000000066e+15
     big-M-complementary-additional_constraints[3]: 8 x[0] + 10 x[1] + 5 x[2]
       + x[3] + 3 x[4] + 1e+15 delta[13] <= 1.0000000000000054e+15
     big-M-complementary-additional_constraints[4]: 7 x[0] + 6 x[1] + 5 x[2]
       + 3 x[3] + 4 x[4] + 1e+15 delta[14] <= 1.000000000000005e+15
     big-M-complementary-additional_constraints[5]: 6 x[0] + 2 x[1] + 2 x[2]
       + 7 x[3] + 2 x[4] + 1e+15 delta[15] <= 1.0000000000000038e+15
     big-M-complementary-additional_constraints[6]: 6 x[0] + 6 x[1] + 10 x[2]
       + 5 x[3] + x[4] + 1e+15 delta[16] <= 1.0000000000000056e+15
     big-M-complementary-additional_constraints[7]: 8 x[0] + 9 x[1] + 2 x[2]
       + 7 x[3] + 2 x[4] + 1e+15 delta[17] <= 1.0000000000000056e+15
     big-M-complementary-additional_constraints[8]: 9 x[0] + 5 x[1] + 10 x[2]
       + 6 x[3] + 10 x[4] + 1e+15 delta[18] <= 1.000000000000008e+15
     big-M-complementary-additional_constraints[9]: 4 x[0] + 2 x[1] + x[2]
       + 4 x[3] + 5 x[4] + 1e+15 delta[19] <= 1.0000000000000032e+15
    Bounds
     theta[0] free
     theta[1] free
     theta[2] free
     theta[3] free
     theta[4] free
    Binaries
     delta[0] delta[1] delta[2] delta[3] delta[4] delta[5] delta[6] delta[7]
     delta[8] delta[9] delta[10] delta[11] delta[12] delta[13] delta[14]
     delta[15] delta[16] delta[17] delta[18] delta[19]
    End

    and the model provided by MVar is as follows:

    \ Model FractionalKnapsackBilevel
    \ LP format - for model browsing. Use MPS format to capture full model detail.
    Minimize
      k[0] + k[1] + k[2] + k[3] + k[4]
    Subject To
     L1-norm-reformulation-a[0]: theta[0] - k[0] <= -7
     L1-norm-reformulation-a[1]: theta[1] - k[1] <= -2
     L1-norm-reformulation-a[2]: theta[2] - k[2] <= -3
     L1-norm-reformulation-a[3]: theta[3] - k[3] <= -7
     L1-norm-reformulation-a[4]: theta[4] - k[4] <= 7
     L1-norm-reformulation-b[0]: - theta[0] - k[0] <= 7
     L1-norm-reformulation-b[1]: - theta[1] - k[1] <= 2
     L1-norm-reformulation-b[2]: - theta[2] - k[2] <= 3
     L1-norm-reformulation-b[3]: - theta[3] - k[3] <= 7
     L1-norm-reformulation-b[4]: - theta[4] - k[4] <= -7
     Capacity_Constraint: 6 x[0] + 20 x[1] + 13 x[2] + 48 x[3] + 10 x[4] <= 90
     primal-feasibility[0]: - x[0] >= -1
     primal-feasibility[1]: - x[1] >= -1
     primal-feasibility[2]: - x[2] >= -1
     primal-feasibility[3]: - x[3] >= -1
     primal-feasibility[4]: - x[4] >= -1
     primal-feasibility[5]: x[0] >= 0
     primal-feasibility[6]: x[1] >= 0
     primal-feasibility[7]: x[2] >= 0
     primal-feasibility[8]: x[3] >= 0
     primal-feasibility[9]: x[4] >= 0
     primal-feasibility[10]: 10 x[0] + 7 x[1] + x[2] + x[3] + 2 x[4] >= 4.2
     primal-feasibility[11]: 4 x[0] + 4 x[1] + 9 x[2] + 10 x[3] + x[4] >= 5.6
     primal-feasibility[12]: 9 x[0] + 4 x[1] + 9 x[2] + 7 x[3] + 4 x[4] >= 6.6
     primal-feasibility[13]: 8 x[0] + 10 x[1] + 5 x[2] + x[3] + 3 x[4] >= 5.4
     primal-feasibility[14]: 7 x[0] + 6 x[1] + 5 x[2] + 3 x[3] + 4 x[4] >= 5
     primal-feasibility[15]: 6 x[0] + 2 x[1] + 2 x[2] + 7 x[3] + 2 x[4] >= 3.8
     primal-feasibility[16]: 6 x[0] + 6 x[1] + 10 x[2] + 5 x[3] + x[4] >= 5.6
     primal-feasibility[17]: 8 x[0] + 9 x[1] + 2 x[2] + 7 x[3] + 2 x[4] >= 5.6
     primal-feasibility[18]: 9 x[0] + 5 x[1] + 10 x[2] + 6 x[3] + 10 x[4] >= 8
     primal-feasibility[19]: 4 x[0] + 2 x[1] + x[2] + 4 x[3] + 5 x[4] >= 3.2
     dual-feasibility[0]: - theta[0] - y[0] + y[5] + 10 y[10] + 4 y[11]
       + 9 y[12] + 8 y[13] + 7 y[14] + 6 y[15] + 6 y[16] + 8 y[17] + 9 y[18]
       + 4 y[19] = 0
     dual-feasibility[1]: - theta[1] - y[1] + y[6] + 7 y[10] + 4 y[11]
       + 4 y[12] + 10 y[13] + 6 y[14] + 2 y[15] + 6 y[16] + 9 y[17] + 5 y[18]
       + 2 y[19] = 0
     dual-feasibility[2]: - theta[2] - y[2] + y[7] + y[10] + 9 y[11] + 9 y[12]
       + 5 y[13] + 5 y[14] + 2 y[15] + 10 y[16] + 2 y[17] + 10 y[18] + y[19]
       = 0
     dual-feasibility[3]: - theta[3] - y[3] + y[8] + y[10] + 10 y[11] + 7 y[12]
       + y[13] + 3 y[14] + 7 y[15] + 5 y[16] + 7 y[17] + 6 y[18] + 4 y[19] = 0
     dual-feasibility[4]: - theta[4] - y[4] + y[9] + 2 y[10] + y[11] + 4 y[12]
       + 3 y[13] + 4 y[14] + 2 y[15] + y[16] + 2 y[17] + 10 y[18] + 5 y[19]
       = 0
     big-M-complementary_y[0]: y[0] - 1e+15 delta[0] <= 0
     big-M-complementary_y[1]: y[1] - 1e+15 delta[1] <= 0
     big-M-complementary_y[2]: y[2] - 1e+15 delta[2] <= 0
     big-M-complementary_y[3]: y[3] - 1e+15 delta[3] <= 0
     big-M-complementary_y[4]: y[4] - 1e+15 delta[4] <= 0
     big-M-complementary_y[5]: y[5] - 1e+15 delta[5] <= 0
     big-M-complementary_y[6]: y[6] - 1e+15 delta[6] <= 0
     big-M-complementary_y[7]: y[7] - 1e+15 delta[7] <= 0
     big-M-complementary_y[8]: y[8] - 1e+15 delta[8] <= 0
     big-M-complementary_y[9]: y[9] - 1e+15 delta[9] <= 0
     big-M-complementary_y[10]: y[10] - 1e+15 delta[10] <= 0
     big-M-complementary_y[11]: y[11] - 1e+15 delta[11] <= 0
     big-M-complementary_y[12]: y[12] - 1e+15 delta[12] <= 0
     big-M-complementary_y[13]: y[13] - 1e+15 delta[13] <= 0
     big-M-complementary_y[14]: y[14] - 1e+15 delta[14] <= 0
     big-M-complementary_y[15]: y[15] - 1e+15 delta[15] <= 0
     big-M-complementary_y[16]: y[16] - 1e+15 delta[16] <= 0
     big-M-complementary_y[17]: y[17] - 1e+15 delta[17] <= 0
     big-M-complementary_y[18]: y[18] - 1e+15 delta[18] <= 0
     big-M-complementary_y[19]: y[19] - 1e+15 delta[19] <= 0
     big-M-complementary-others[0]: - x[0] + 1e+15 delta[0]
       <= 9.99999999999999e+14
     big-M-complementary-others[1]: - x[1] + 1e+15 delta[1]
       <= 9.99999999999999e+14
     big-M-complementary-others[2]: - x[2] + 1e+15 delta[2]
       <= 9.99999999999999e+14
     big-M-complementary-others[3]: - x[3] + 1e+15 delta[3]
       <= 9.99999999999999e+14
     big-M-complementary-others[4]: - x[4] + 1e+15 delta[4]
       <= 9.99999999999999e+14
     big-M-complementary-others[5]: x[0] + 1e+15 delta[5] <= 1e+15
     big-M-complementary-others[6]: x[1] + 1e+15 delta[6] <= 1e+15
     big-M-complementary-others[7]: x[2] + 1e+15 delta[7] <= 1e+15
     big-M-complementary-others[8]: x[3] + 1e+15 delta[8] <= 1e+15
     big-M-complementary-others[9]: x[4] + 1e+15 delta[9] <= 1e+15
     big-M-complementary-others[10]: 10 x[0] + 7 x[1] + x[2] + x[3] + 2 x[4]
       + 1e+15 delta[10] <= 1.0000000000000042e+15
     big-M-complementary-others[11]: 4 x[0] + 4 x[1] + 9 x[2] + 10 x[3] + x[4]
       + 1e+15 delta[11] <= 1.0000000000000056e+15
     big-M-complementary-others[12]: 9 x[0] + 4 x[1] + 9 x[2] + 7 x[3] + 4 x[4]
       + 1e+15 delta[12] <= 1.0000000000000066e+15
     big-M-complementary-others[13]: 8 x[0] + 10 x[1] + 5 x[2] + x[3] + 3 x[4]
       + 1e+15 delta[13] <= 1.0000000000000054e+15
     big-M-complementary-others[14]: 7 x[0] + 6 x[1] + 5 x[2] + 3 x[3] + 4 x[4]
       + 1e+15 delta[14] <= 1.000000000000005e+15
     big-M-complementary-others[15]: 6 x[0] + 2 x[1] + 2 x[2] + 7 x[3] + 2 x[4]
       + 1e+15 delta[15] <= 1.0000000000000038e+15
     big-M-complementary-others[16]: 6 x[0] + 6 x[1] + 10 x[2] + 5 x[3] + x[4]
       + 1e+15 delta[16] <= 1.0000000000000056e+15
     big-M-complementary-others[17]: 8 x[0] + 9 x[1] + 2 x[2] + 7 x[3] + 2 x[4]
       + 1e+15 delta[17] <= 1.0000000000000056e+15
     big-M-complementary-others[18]: 9 x[0] + 5 x[1] + 10 x[2] + 6 x[3]
       + 10 x[4] + 1e+15 delta[18] <= 1.000000000000008e+15
     big-M-complementary-others[19]: 4 x[0] + 2 x[1] + x[2] + 4 x[3] + 5 x[4]
       + 1e+15 delta[19] <= 1.0000000000000032e+15
    Bounds
     theta[0] free
     theta[1] free
     theta[2] free
     theta[3] free
     theta[4] free
    Binaries
     delta[0] delta[1] delta[2] delta[3] delta[4] delta[5] delta[6] delta[7]
     delta[8] delta[9] delta[10] delta[11] delta[12] delta[13] delta[14]
     delta[15] delta[16] delta[17] delta[18] delta[19]
    End

     

     

    and the code used to construct addMVar is as follows:

    def solveFractionalBilevel(self, M):

    m,n = self.A.shape

    model = grb.Model('FractionalKnapsackBilevel')

    model.Params.LogToConsole = 0




    x = model.addMVar(n, vtype = grb.GRB.CONTINUOUS, name = 'x')

    theta = model.addMVar(n, lb = - grb.GRB.INFINITY, vtype = grb.GRB.CONTINUOUS, name = 'theta')

    y = model.addMVar(m, lb=0, vtype = grb.GRB.CONTINUOUS, name = 'y')

    delta = model.addMVar(m, vtype = grb.GRB.BINARY, name = 'delta')

    k = model.addMVar(n, vtype = grb.GRB.CONTINUOUS, name = 'k')




    #construct l1 norm, use epigrapical representation

    model.setObjective(

    grb.quicksum(k[i] foriinrange(n)),

    grb.GRB.MINIMIZE

    )

    model.addConstrs((theta[i] - self.items[i]['value'] <= k[i] foriinrange(n)), name="L1-norm-reformulation-a")

    model.addConstrs((self.items[i]['value'] - theta[i] <= k[i] foriinrange(n)), name="L1-norm-reformulation-b")

    #q^T x <= tau

    model.addConstr(

    grb.quicksum(self.items[i]['weight']*x[i] foriinrange(n))

    <= self.capacity, name='Capacity Constraint')




    model.addMConstr(self.A, x, ">=", self.b, name="primal-feasibility")

    #A^T y = theta

    model.addConstrs( (grb.quicksum(self.A[j,i]*y[j] forjinrange(m)) - theta[i] == 0foriinrange(n)), name='dual-feasibility')




    #complementary constraints

    model.addConstrs((y[i]<= M *(delta[i]) foriinrange(m)), name='big-M-complementary_y')




    model.addConstrs( (grb.quicksum(self.A[i][j]*x[j] forjinrange(n)) - self.b[i] <= M*(1-delta[i]) foriinrange(m)), name = 'big-M-complementary-others')

    model.write('model_MVar_formulation.lp')

    model.optimize()

    model.write('model_MVar_formulation.sol')


    and for the Var formulation:

    def solveHarderKnapsackBilevel(self,M, additional_constraint_lhs, additional_constraint_rhs):

    model = grb.Model('HarderFractionalKnapsackBilevel')

    model.Params.LogToConsole = 0

    time_intitialize_model = time.time()

    x = model.addVars(len(self.items), vtype = grb.GRB.CONTINUOUS, name = 'x')

    theta = model.addVars(len(self.items), lb = - grb.GRB.INFINITY, vtype = grb.GRB.CONTINUOUS, name = 'theta')

    y = model.addVars(2*len(self.items), lb=0, vtype = grb.GRB.CONTINUOUS, name = 'y')

    num_additional_var = len(additional_constraint_rhs)

    #additional variables for more complicated case

    v = model.addVars(num_additional_var, lb = 0, name = 'additional_vars_associated_dual')



    delta = model.addVars(2*len(self.items) + num_additional_var, vtype = grb.GRB.BINARY, name = 'delta')

    k = model.addVars(len(self.items), vtype = grb.GRB.CONTINUOUS, name = 'k')




    #construct l1 norm, use epigrapical representation

    model.setObjective(

    grb.quicksum(k[i] foriinrange(len(self.items))),

    grb.GRB.MINIMIZE

    )

    model.addConstrs((theta[i] - self.items[i]['value'] <= k[i] foriinrange(len(self.items))), name="L1-norm-reformulation-a")

    model.addConstrs((self.items[i]['value'] - theta[i] <= k[i] foriinrange(len(self.items))), name="L1-norm-reformulation-b")

    #q^T x <= tau

    model.addConstr(

    grb.quicksum(self.items[i]['weight']*x[i] foriinrange(len(self.items)))

    <= self.capacity, name='Capacity Constraint')




    I = np.eye(len(self.items))

    foriinrange(len(self.items)):

    model.addConstr(

    grb.quicksum(-I[i, j] * x[j] forjinrange(len(self.items))) >= -1,

    name=f"<=1_Constraint_{i+1}"

    )

    model.addConstr(

    grb.quicksum(I[i,j] * x[j] forjinrange(len(self.items))) >= 0,

    name =f"nonnegativity_{i+1}"

    )

    model.addConstrs( (grb.quicksum(additional_constraint_lhs[i][j]*x[j] forjinrange(len(self.items))) >= additional_constraint_rhs[i] foriinrange(num_additional_var)), name='additional_constraint_')

    #A^T y = theta

    foriinrange(len(self.items)):

    model.addConstr(

    grb.quicksum(-I[j,i]*y[j] + I[j,i]*y[len(self.items)+j] forjinrange(len(self.items))) + grb.quicksum(additional_constraint_lhs[j][i]*v[j] forjinrange(num_additional_var) ) == theta[i], name=f'dual_feasibility_{i+1}'

    )




    #complementary constraints

    model.addConstrs((y[i]<= M *(delta[i]) foriinrange(2*len(self.items))), name='big-M-complementary_y')

    model.addConstrs((v[i]<= M* (delta[i + 2*len(self.items)]) foriinrange(num_additional_var)), name = 'big-M-complementary_additional_var')

    model.addConstrs((grb.quicksum(-I[i,j]*x[j] forjinrange(len(self.items))) +1 <= M * (1-delta[i]) foriinrange(len(self.items))), name="big-M-complementary-A_1")


    model.addConstrs((grb.quicksum(I[i-len(self.items),j]*x[j] forjinrange(len(self.items))) <= M * (1-delta[i]) foriinrange(len(self.items), 2*len(self.items))), name="big-M-complementary-A_2")

    #additional complementary constraints for more complex case

    model.addConstrs( (grb.quicksum(additional_constraint_lhs[j][i]*x[i] foriinrange(len(self.items))) - additional_constraint_rhs[j] <= M * (1- delta[j+ 2*len(self.items)]) forjinrange(num_additional_var)), name='big-M-complementary-additional_constraints')

    model.write('modelHarder.lp')

    model.optimize()

    model.write('modelHarder.sol')


    For some context, we have $\bm x$ to be in a simple [0,1] box set, and defined it as A = [-I, I] (instead of explicitly defining the lb and ub of the variable x). 

    0
  • Marika Karbstein
    Gurobi Staff Gurobi Staff

    Thanks for the additional information.
    Please note that the Matrix Python API is especially for models already given in matrix notation. It is not efficient to use mVars mixed with term-based notation.

    For example, the constraint

    model.addConstrs((grb.quicksum(self.A[i][j]*x[j] for j in range(n)) - self.b[i] <= M*(1-delta[i]) for i in range(m)), name = 'big-M-complementary-others')

    should be written as

    model.addConstr((self.A @ x) - self.b <= M*(1-delta), name = 'big-M-complementary-others')

    Another example is

    model.addConstrs((y[i]<= M *(delta[i]) for i in range(m)), name='big-M-complementary_y')

    which should be written as

    model.addConstr((y <= M *(delta)), name='big-M-complementary_y')

    Can you try to adapt all constraints in this way and check again?

    Additionally, please note that the scipy.sparse library is imported when adding constraints with MVar for the first time (which is done when adding your first L1-norm constraint). The time for importing this library is not trivial. If you import it in the beginning with 

    import scipy.sparse

    then you can more accurately measure the time required to create these constraints.

    1

サインインしてコメントを残してください。

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

新規投稿