Linear and Quadratic terms in CPLEX Objective Function

Question

I would like to minimize an objective function which is rather simple, but I am somehow having problems making the correct calls to from the Python API to CPLEX

I looked at how to use set_quadratic and set_quadratic_coefficients here but that didn't result in a solution to my problem.

My objective function has a set of linear variables and a set of quadratic variables

varCoefs = [1]*(numB + numQ)
varLower = [0]*(numB + numQ)
varNames = [(x,"b%s"%x) for x in range( numB )]
varNames += [(len(varNames) + x,"q%s"%x) for x in range( numQ )]

varCoefs += [10]*len(deltas)
varLower += [1]*len(deltas)
varNames += [(len(varNames) + x,"delta%s"%x) for x in range( len(deltas) )]

varCoefs += [0]*len(target.v)
varLower += [0]*len(target.v)

sContent = [(len(varNames) + x,"s%s"%x) for x in range( len(target.v) )]
varNames += sContent

varCoefs += [-1]
varLower += [0]
varNames += [(len(varNames),'mu')]


problem.variables.add(obj = varCoefs, lb = varLower)
problem.variables.set_names(varNames)

# problem.objective.set_quadratic_coefficients([[['s%s' % x], [1]] for x in range( len(target.v) )])

problem.objective.set_quadratic(
    [cplex.SparsePair(ind=[sContent[x][0]], val=[1]) for x in range( len(target.v) )]
    )

Everything works up to the last call add the quadratic terms. At which point CPLEX throws the following error CPLEX Error 1226: Array entry 13919 not ascending. twice, ignoring the command, and the Python code continues.

I looked up the error, but that didn't seem to help me either.

I did try re-writing the above to add the variables by name and lower bound first... and then call set_linear and set_quadratic afterward, but that doesn't help either.

What am I missing here?

Answer 1

If you're calling set_quadratic with a quadratic objective function that is separable, it corresponds to CPXXcopyqpsep. If you're calling set_quadratic with a quadratic objective function that is inseparable, it corresponds to CPXXcopyquad. I agree that the error you're getting is not particularly useful, but it makes a bit more sense if you know where it's coming from in the Callable C Library.

With that said, here's a complete example, using your snippet, with some dummy inputs:

import cplex

class MockTarget(object):
    pass

# Dummy data for testing

numB = 3
numQ = 3
deltas = [0.1, 0.1, 0.1]
problem = cplex.Cplex()

target = MockTarget()
target.v = [1, 2, 3]

# Build the problem

varCoefs = [1]*(numB + numQ)
varLower = [0]*(numB + numQ)
varNames = [(x,"b%s"%x) for x in range( numB )]
varNames += [(len(varNames) + x,"q%s"%x) for x in range( numQ )]

varCoefs += [10]*len(deltas)
varLower += [1]*len(deltas)
varNames += [(len(varNames) + x,"delta%s"%x) for x in range( len(deltas) )]

varCoefs += [0]*len(target.v)
varLower += [0]*len(target.v)

sContent = [(len(varNames) + x,"s%s"%x) for x in range( len(target.v) )]
varNames += sContent

varCoefs += [-1]
varLower += [0]
varNames += [(len(varNames),'mu')]


problem.variables.add(obj = varCoefs, lb = varLower)
problem.variables.set_names(varNames)

# Print without quadratic terms so you can see the progression.
problem.write('test1.lp')

# Separable Q

qsepvec = []
for tpl in varNames:
    if tpl in sContent:
        qsepvec.append(1.0)
    else:
        qsepvec.append(0.0)
print qsepvec

problem.objective.set_quadratic(qsepvec)

problem.write('test2.lp')

# Inseparable Q (overwrites previous Q)

qmat = []
for tpl in varNames:
    if tpl in sContent:
        sp = cplex.SparsePair(ind=[tpl[0]], val=[1.0])
        qmat.append(sp)
    else:
        sp = cplex.SparsePair(ind=[], val=[])
        qmat.append(sp)
print qmat

problem.objective.set_quadratic(qmat)

problem.write('test3.lp')

I've written that out in long form rather than using list comprehensions to make it a bit more clear. The contents of the the LP files are below:

test1.lp:

\ENCODING=ISO-8859-1
\Problem name: 

Minimize
 obj: b0 + b1 + b2 + q0 + q1 + q2 + 10 delta0 + 10 delta1 + 10 delta2 + 0 s0
      + 0 s1 + 0 s2 - mu
Bounds
      delta0 >= 1
      delta1 >= 1
      delta2 >= 1
End

test2.lp

\ENCODING=ISO-8859-1
\Problem name: 

Minimize
 obj: b0 + b1 + b2 + q0 + q1 + q2 + 10 delta0 + 10 delta1 + 10 delta2 + 0 s0
      + 0 s1 + 0 s2 - mu + [ s0 ^2 + s1 ^2 + s2 ^2 ] / 2
Bounds
      delta0 >= 1
      delta1 >= 1
      delta2 >= 1
End

test3.lp

\ENCODING=ISO-8859-1
\Problem name: 

Minimize
 obj: b0 + b1 + b2 + q0 + q1 + q2 + 10 delta0 + 10 delta1 + 10 delta2 + 0 s0
      + 0 s1 + 0 s2 - mu + [ s0 ^2 + s1 ^2 + s2 ^2 ] / 2
Bounds
      delta0 >= 1
      delta1 >= 1
      delta2 >= 1
End

You can see that test2.lp and test3.lp are the same (the later overwrites the former, but does the same thing). Hopefully that makes it a bit easier to understand. In general, using this technique of printing out LP's for very simple problems, is one of the more useful debugging techniques.

You should also check out the python examples that are shipped with CPLEX. For example, qpex1.py, miqpex1.py, indefqpex1.py.

Answer 2

I solved the problem by adding the quadratic terms first, setting their coefficients, and then adding the linear terms in a separate call see below.

problem.objective.set_sense(problem.objective.sense.minimize)

varLower = [0]*len(target.v)
varNames = ["s%s"%x for x in range( len(target.v) )]

problem.variables.add(names=varNames, lb=varLower)

problem.objective.set_quadratic(
    [[[x],[1]] for x in range( len(target.v) )]
    )

varCoefs = [-1]
varLower = [0]
varNames = ['mu']


varCoefs += [1]*(numB + numQ)
varLower += [0]*(numB + numQ)
varNames += ["b%s"%x for x in range( numB )]
varNames += ["q%s"%x for x in range( numQ )]

varCoefs += [10]*len(deltas)
varLower += [1]*len(deltas)
varNames += ["delta%s"%x for x in range( len(deltas) )]

problem.variables.add(names=varNames, lb=varLower, obj=varCoefs)

However, I would still like to know why it works this way, and not the other way.