2

I need to program a model in python to solve it with gurobi. The model contains a square root: Σ(hza*√(SI+T-R)) (this is the objective function)

Because Gurobi doesn't support square roots I transformed the objective function as followed: Σ(hza*Z) (objective function)

SI+T-R<=Z*Z (extra constrain)

Z>=0 (extra constrain)

But now Gurobi still gives an error :GurobiError: Q matrix is not positive semi-definite (PSD)

How do I get Gurobi to solve this model? The code: (start with line 143 till line 199)

#create objective
for j in intermediateStage:
    for d in demandStage:
            m.setObjective(quicksum(h[d]*Z*VarDemand[d]*Z2[d] for d in demandStage)+quicksum(h[j]*Z*Z1[j]*Var[j] for j in intermediateStage),GRB.MINIMIZE)

#addconstraints
for j in intermediateStage:
    m.addConstr(R[j]-SI[j]<=T[j])

for d in demandStage:
    m.addConstr(R[d]-SI[d]<=T[d])

for k in supplyStage:
    m.addConstr(R[k]-SI[k]<=T[k])

for j in intermediateStage:
    m.addQConstr(SI[j]+T[j]-R[j]<=Z1[j]*Z1[j])

for d in demandStage:
    m.addQConstr(SI[d]+T[d]-R[d]<=Z2[d]*Z2[d])

for k in supplyStage:
    for j in intermediateStage:
        m.addConstr(R[k]-SI[j]<=0)

for j in intermediateStage:
    for d in demandStage:
        m.addConstr(R[j]-SI[d]<=0)

for d in demandStage:
    m.addConstr(R[d]<=E[d])

for k in supplyStage:
    m.addConstr(SI[k]==0)

for k in supplyStage:
            m.addConstr(SI[k]>=0)
for k in supplyStage:
            m.addConstr(R[k]>=0)

for d in demandStage:
    m.addConstr(SI[d]>=0)
for d in demandStage:
    m.addConstr(R[d]>=0)
for d in demandStage:
    m.addConstr(Z2[d]>=0)

for j in intermediateStage:
    m.addConstr(SI[j]>=0)
for j in intermediateStage:
    m.addConstr(R[j]>=0)
for j in intermediateStage:
    m.addConstr(Z1[j]>=0)

m.optimize()
print SI[j]
print R[j]

Traceback (most recent call last): File "C:\gurobi600\win32\examples\python\safetyStock.py", line 230, in safetystock(demand,intermediate,alfa) File "C:\gurobi600\win32\examples\python\safetyStock.py", line 192, in safetystock m.optimize() File "model.pxi", line 536, in gurobipy.Model.optimize (../../src/python/gurobipy.c:37543) GurobiError: Q matrix is not positive semi-definite (PSD)

S.Six
  • 31
  • 2
  • 5
  • Who can help me? is not a great question. You might want to reword it better. – Caltor Aug 10 '15 at 09:42
  • better? I just need help to remove the error so that Gurobi can solve the model, but I don't really know how to do that... – S.Six Aug 10 '15 at 12:32
  • Great stuff. I've upvoted to try and help you get an answer. Unfortunately I know nothing about Gurobi but hopefully somebody will be able to help you out. – Caltor Aug 10 '15 at 13:53
  • You are getting this error because you have non-linear terms in your constraints, such as `SI+T-R<=Z*Z `, that render your constraint matrix non-PSD. Your objective function is also non-linear, although it can be linearised (see [here](http://stackoverflow.com/questions/30774270/how-to-convert-quadratic-to-linear-program/30812966#30812966)). – Ioannis Aug 10 '15 at 20:46
  • According to the website of Gurobi, Gurobi does support Quadratic Programming and Quadratically constrained programming... Our am I mistaken? – S.Six Aug 11 '15 at 08:00
  • The objective function is lineair. h, z and a are coefficient so there is only one variable in the objective function... – S.Six Aug 11 '15 at 08:16
  • Yes, it supports QCQP, but they have to be in [this](http://www.gurobi.com/documentation/5.0/refman/node537) form. I think gurobi tries to convert your quadratic equations to that form, fails and then gives this error. I am not an expert in transformations of quadratic expressions. [This](http://www.gurobi.com/resources/seminars-and-videos/gurobi-quadratic-constraints-webinar) video might help you though. – Ioannis Aug 11 '15 at 11:03
  • To clarify the previous comment by loannis, it appears that the only languages with constraints on the form of a quadratic constraint are C, MATLAB, and R, where the right hand side of the constraint must be a constant. In other languages (C++, Python, Java, .NET), there is no such restriction on the form of a quadratic constraint. See the [Quadratic Constraints](http://www.gurobi.com/documentation/7.5/refman/constraints.html#subsubsection:QuadraticConstraints) page. –  Apr 16 '18 at 00:56

1 Answers1

2

An expression of the form Z2[d]*Z2[d] is convex, but you have it on the right side of a <= constraint. That's equivalent to a <= equation with a concave left-hand side expression, which isn't supported by Gurobi. The fundamental issue is that you trying to minimize a concave expression (the square root) which represents an economy of scale. While you can use algebra make the square root go away, you can't make the inherent non-convexity of the problem go away. You can use binary variables or the built-in piecewise linear features to approximate the square root.

David Nehme
  • 21,379
  • 8
  • 78
  • 117