adding a quadratic constraint for the sum of an inverse variable

Imke Lorenz

• July 08, 2019 12:09

Hello,

I am trying to maximize the following non-linear objective: quicksum(1/x[k] for k in K) where x[k] are the different least weighted paths from a source to a target, which equals the product of the weights of each path (R[i,j]) (Matrix of constants) and the paths selected t[i,j] (Matrix of binary variables) to reach the target.

I thought I could reformulate the inverse as invX[k] = 1/x[k] which should be a second order cone problem and invX is an array of continuous variables. Therefore I want to add the constraint for each k: m.addQConstr(invX[k]*x[k] == 1) and rewrite the ojective function as maximize quicksum(invX[k] for k in K), K is an array of the length of the number of least weighted paths to be considered.

I implemented the following:

m.addQConstr(invX[k]*quicksum(R[i,j]*t[i,j,k] for i in node_list for j in node_list) >= 1)

The error message I get is "Q matrix is not positive semi-definite (PSD)". However, I thought for this problem a rotated second order cone is the case, which is the third case stated here: https://www.gurobi.com/documentation/8.1/refman/py_model_addqconstr.html.

How do I incorporate this objective as a constraint correctly?

Thanks in advance

0

• 

  Imke Lorenz

  • July 08, 2019 13:47

  

  

  

  I found part of the solution to this problem: I defined another variable TR[k] and m.addConstr(TR[k] == quicksum(R[i,j]*t[i,j,k] for i in node_list for j in node_list)) and rewrote the quadratic constraint as m.addQConstr(invX[k]*TR[i,j,k] >= 1), which works now. The other part missing is m.addQConstr(invX[k]*TR[i,j,k] <= 1), which is not applicable. Are there any ideas how to incorporate this constraint maybe also in combination with rewriting the current objective function: m.setObjective(quicksum(invX[k] for k in K), GRB.MAXIMIZE).

  I already tried m.addQConstr(invX[k]*TR[i,j,k]*-1 >= -1) but this is not solvable.

  Thanks in advance

  0
• 

  Tobias Achterberg

  Gurobi Staff

  • July 30, 2019 11:55

  Hi Imke,

  the issue is that your objective function needs to be convex when it is formulated as minimization problem. So, your objective function would read

  min quicksum(-1/x[k] for k in K)

  But this objective function is not convex. So, Gurobi 8.1 is not able to solve it. You have already seen it yourself: if you translate this into a constraint, then a convex constraint will point into the wrong direction.

  With Gurobi 9.0 it will be possible to solve non-convex quadratic problems. But it is not clear to me how difficult your model would be.

  Best regards,

  Tobias

   

  0
• 

  Surya Narayanan Hari

  • October 24, 2020 16:47

  

  

  

  I tried doing 1 / p_inv[i] but division is not supported between an int and an MVar. I am using version 9.0.2. Can you suggest if it is not supported for MVars yet?

  0

Please sign in to leave a comment.