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

Answered

y xm

• April 02, 2024 10:26
• Edited

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

• 

  Matthias Miltenberger

  Gurobi Staff

  • April 02, 2024 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

  • April 02, 2024 13:19

  

  

  Thanks!  I found the error in my problem.

  0

Please sign in to leave a comment.