Can't get dual values for my non-convex QP

Question

How can I get CPLEX to solve for the dual values in a quadratic program? It is currently giving me error that my program is mixed integer when in fact it is not. I came up with a simple example as follows: max z = x^2 + 2x + y s.t 0 <= x <= 10; 0 <= y <= 10

Below is my codes in cplex c++:

IloEnv env;

IloNumVar x(env, 0, IloInfinity);
IloNumVar y(env, 0, IloInfinity);

IloExpr obj(env);
obj = x*x + 2*x + y;

IloModel model(env);
model.add(IloMaximize(env,obj));

IloRange r1(env, 0, x, 10);
IloRange r2(env, 0, y, 10);

model.add(r1);
model.add(r2);

IloCplex cplex(model);
cplex.setOut(env.getNullStream());
cplex.setWarning(env.getNullStream());
cplex.setParam(IloCplex::Param::SolutionTarget,IloCplex::SolutionOptimalGlobal);

try{
    cplex.solve();
    env.out() << "x: " << cplex.getValue(x) << endl;
    env.out() << "y: " << cplex.getValue(y) << endl;
    env.out() << "Dual r1: " << cplex.getDual(r1) << endl;
    env.out() << "Dual r2: " << cplex.getDual(r2) << endl;  

    } catch (IloException& e) {
    std::cerr << "IloException: " << e << endl;
} catch (std::exception& e) {
    std::cerr << "Standard exception: " << e.what() << endl;
} catch (...) {
    std::cerr << "Some other exception!" << endl;
}

While cplex is able to solve for the optimal solution, it is unable to generate the dual values. Error message is "Cplex Error 1017: Not available for mixed integer programs.

Answer 1

You didn't specify which version of CPLEX you were using. Let me try with the latest one, 12.9. Here's your problem:

$ cat foo.lp
Maximize
 obj1: 2 x + y + [ 2 x ^2 ] / 2
Subject To
 c1: x <= 10
 c2: y <= 10
End

And here's the CPLEX log when setting the OptimalityTarget parameter to 3, as you did, to get a globally optimal solution:

$ cplex -c "read foo.lp" "set optimalitytarget 3" "optimize"

Welcome to IBM(R) ILOG(R) CPLEX(R) Interactive Optimizer 12.9.0.0
  with Simplex, Mixed Integer & Barrier Optimizers
5725-A06 5725-A29 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5655-Y21
Copyright IBM Corp. 1988, 2019.  All Rights Reserved.

Type 'help' for a list of available commands.
Type 'help' followed by a command name for more
information on commands.

CPLEX> Problem 'foo.lp' read.
Read time = 0.00 sec. (0.00 ticks)
CPLEX> New value for type of solution CPLEX will attempt to compute: 3
CPLEX> CPXPARAM_OptimalityTarget                        3
Warning: global optimality target changes problem type to MIQP.
Found incumbent of value 0.000000 after 0.00 sec. (0.00 ticks)
Tried aggregator 1 time.
MIQP Presolve eliminated 2 rows and 2 columns.
All rows and columns eliminated.
Presolve time = 0.00 sec. (0.00 ticks)

Root node processing (before b&c):
  Real time             =    0.00 sec. (0.00 ticks)
Parallel b&c, 4 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.00 sec. (0.00 ticks)

Solution pool: 2 solutions saved.

MIP - Integer optimal solution:  Objective =  1.3000000000e+02
Solution time =    0.00 sec.  Iterations = 0  Nodes = 0
Deterministic time = 0.00 ticks  (2.00 ticks/sec)

CPLEX>

You can notice the following warning (you could not see it, because you disabled the warning stream):

Warning: global optimality target changes problem type to MIQP.

In order to solve a non-convex QP to global optimality, CPLEX has to consider the problem as a Mixed-Integer QP. And dual values are not available for Mixed-Integer problems.

To get dual values for your solution, you can turn the problem to a fixed MIQP: the problem is relaxed to a QP with the variable bounds fixed to the incumbent solution. Then ask for local optimality (otherwise the problem will again be turned into an MIQP), and re-solve. Here's how it looks like in the Interactive:

$ cplex129 -c "read foo.lp" "set optimalitytarget 3" "optimize" \
              "change problem fixed_miqp" "set optimalitytarget 2" \
              "optimize" "display solution dual *"

[...]

CPLEX> MIQP problem relaxed to QP with fixed integer variables using
incumbent solution.
CPLEX> New value for type of solution CPLEX will attempt to compute: 2
CPLEX> CPXPARAM_OptimalityTarget                        2
Note: Q in objective is not positive semi-definite.
Tried aggregator 1 time.
QP Presolve eliminated 2 rows and 2 columns.
All rows and columns eliminated.
Presolve time = 0.00 sec. (0.00 ticks)
Barrier time = 0.00 sec. (0.00 ticks)

Total time on 4 threads = 0.00 sec. (0.00 ticks)

Barrier - Optimal:  Objective =  1.3000000000e+02
Solution time =    0.00 sec.  Iterations = 0
Deterministic time = 0.00 ticks  (0.68 ticks/sec)

CPLEX> Constraint Name             Dual Price
c1                           22.000000
c2                            1.000000
CPLEX>