Solution for a MIP problem with QP non-convex constraints is not right.

回答済み

y xm

2024年04月02日 10:26 編集済み

• 
• 
• 

Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (win64 - Windows 11.0 (22631.2))

The raw problem is "max min avg_r", and it is transformed into "max min_avg_r".

The code is as follows.

def max_min_avg_res(res_M, s_MN, alloc_a_MN, fix_a_N, fix_a_M):
    M, N = s_MN.shape
    model = gp.Model("qcp")

    var_a_MN = model.addMVar(shape=(M, N), vtype=GRB.BINARY, name='a_MN')
    var_min_avg_res = model.addVar(vtype=GRB.CONTINUOUS, lb=0.0, ub=np.max(res_M), name='min_avg_res')

    model.setObjective(var_min_avg_res, GRB.MAXIMIZE)

    for n in range(N):
        if fix_a_N[n] == FIXED_DEV:
            model.addConstrs((var_a_MN[m, n] == alloc_a_MN[m, n] for m in range(M)), name=f'a_MN==alloc_a_MN-N{n}')
        else:
            model.addConstr(var_a_MN[:, n].sum() == 1, name=f"sum_a_N{n}==1")

    for m in range(M):
        if fix_a_M[m] != FIXED_EDGE:
            # z_N = min_avg_res * a_MN[m,n]
            # var_z_N = model.addVars(N, vtype=GRB.CONTINUOUS, lb=0.0, ub=res_M[m], name=f"z_N-M{m}")
            model.addConstr(res_M[m] - (var_a_MN[m, :].sum() - np.sum(alloc_a_MN[m,:])) * var_min_avg_res >= 0.0, name=f"res{m}")
            
    ###################
    # model.printStats()
    model.optimize()
    model.write("./model.lp")

    a_MN = np.zeros((M, N))
    if model.Status == GRB.OPTIMAL:
        for m in range(M):
            for n in range(N):
                a_MN[m, n] = model.getVarByName(f"a_MN[{m},{n}]").X
    else:
        a_MN = None
        print("No optimal solution.")
    return a_MN

def test():
    remained_res_m = np.array([5.0, 6.0])
    Smn = np.array([[0, 1, 1], [1, 0, 1]])
    Amn_alloc = np.array([[0, 1, 0], [1, 0, 0]])
    fix_a_N = np.array([1, 1, 0])
    fix_a_M = np.array([1, 0])

    a_MN = max_min_avg_res(remained_res_m, Smn, Amn_alloc, fix_a_N, fix_a_M)
    print(a_MN)

The output of model.lp is as follows.

\ Model qcp
\ LP format - for model browsing. Use MPS format to capture full model detail.
Maximize
  min_avg_res
Subject To
 a_MN==alloc_a_MN-N0[0]: a_MN[0,0] = 0
 a_MN==alloc_a_MN-N0[1]: a_MN[1,0] = 1
 a_MN==alloc_a_MN-N1[0]: a_MN[0,1] = 1
 a_MN==alloc_a_MN-N1[1]: a_MN[1,1] = 0
 sum_a_N2==1: a_MN[0,2] + a_MN[1,2] = 1
 res1: [ - a_MN[1,0] * min_avg_res - a_MN[1,1] * min_avg_res
   - a_MN[1,2] * min_avg_res ] >= -6
Bounds
 min_avg_res <= 6
Binaries
 a_MN[0,0] a_MN[0,1] a_MN[0,2] a_MN[1,0] a_MN[1,1] a_MN[1,2]
End

The values of a_MN is:

[[-0.  1.  1.]
 [ 1.  0.  0.]]

It should be 

[[-0.  1.  0.]
 [ 1.  0.  1.]]

 

I'll be grateful for any help.

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:27

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

  Matthias Miltenberger

  • Gurobi Staff

  2024年04月02日 10:43

  Your question is unclear. The optimal solution to the small LP file is (values of a_MN):

  [[-0.  1.  1.]
   [ 1.  0.  0.]]

  You want to maximize \(\texttt{min_avg_res}\), so it will be set to 6, satisfying all constraints. \(\texttt{sum_a_N2}\) forces \(\texttt{a_MN[0,2]}\) to 0 because constraint \(\texttt{res1}\) forces \(\texttt{a_MN[1,2]}\) to 0.

  0
• 

  y xm

  2024年04月02日 13:19

  • 
  • 
  • 

  Thanks!  I found the error in my problem.

  0

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