adding a quadratic constraint for the sum of an inverse variable
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
-
Official comment
-
Gurobi Staff
This post is more than three 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 why not try our AI Gurobot?. -
-
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 -
-
-
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 -
-
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 -
Post is closed for comments.
Comments
4 comments