Constant term in objective for quadratic program w

问题:

I'm using CPLEX 12.5.0.0 via the C# API.

Until now, I've never had a situation with an objective with a constant term - only constraints. With constraints, I have always been able to re-arrange the equation so the constant is always on one side, meaning each ILinearNumExpr has no constant term on its own.

Now I have a quadratic programming problem, with an objective of the following type:

MAX Z = 
  c[1,2] * a[1] * a[2] - c[1,2] * (1 - a[1] * a[2]) +
  c[1,3] * a[1] * a[3] - c[1,2] * (1 - a[1] * a[3]) +
  c[2,3] * a[2] * a[3] - c[2,2] * (1 - a[2] * a[3])

c[,] is a constant, symmetric cost matrix. a[i] are binary variables.

So looking at the left halves of the 3 lines above, having both a[i] and a[j] together will contribute c[i,j] to the objective value. This is what is currently implemented, tested, and working.

I want to modify the objective so that, if a[i] and a[j] are not both equal to 1, rather than not contributing c[i,j] to the objective value, it will subtract it.

Now, I've looked up the CPLEX documentation (the authors of which are apparently allergic to providing clear explanations or examples), and there appears to be an ILinearNumExpr.Constant property that allows me to set a constant for a given expression.

When I tried to modify my code with IQuadNumExpr, I noticed it doesn't have that .Constant property.

Is there any way to add constant terms to a quadratic objective function in CPLEX?

回答1:

To answer your specific question, to add a constant to a quadratic objective function, you can use the .Sum method of the cplex object. For example

cplex.AddMaximize(cplex.sum(quadExpr, cplex.Constant(10));

makes the objective function quadExpr + 10.

Now, two comments on the rest of your post.

First, any linear transformation on the objective function will have no effect on your solution. So, if you are maximizing either

quadExpr

or

m * quadExpr + c

are equivalent for any (nonzero) constant m and constant c.

Next, Since the variables in your quadratic expression are binary, then you can almost always do better by formulating a mixed-integer linear model. To do this, you create an additional set of linear variables, say b[i][j] that will be 1 only if both x[i] and a[j] are both 1. You can enforce the property of b[][] by adding the constraints

b[i][j] <= x[i]
b[i][j] <= x[j]

If you are maximizing, and c[i][j] >= 0, then you don't need to explicitly enforce the converse, but if that's not the case, you can add

x[i] + x[j] <= 1 + b[i][j]