Maximizing linear objective subject to quadratic c

Question

I have a programming formulation from a paper and want to give it a tool for solving specific problems. The authors stated it as an linear programming (LP) instance, however I am not sure. Formulation is somewhat like as follows:

max x1+x2+x3...

s.t.

x1.x3+x4.x5 <= 10

x2.x5+x3.x7+x1.x9 <=10

...

I tried to program it through cplexqcp function (due to quadratic constraints, however constraints do not include any x_i^2 variable). However I receive CPLEX Error 5002: Q in %s is not positive semi-definite error. Is this an instance of non-linear programming with non-convex constraints? Can I solve it with CPLEX or use an NLP tool for it? I am newbie to LP/NLP staff (do not take any course regarding them), so really welcome help explaining details of the answers of my questions.

Thanks so much.

Answer 1

The problem you posted needs some information on the domain of the variables x1, x2 and x3.

If they are continuous, there is no way to express your problem as linear program (LP), since the surface of x1*x2 is just non-linear.

If at least one of the product variables are binary (integer), the product can be linearized (so if you have a mixed integer program) like described in here - since the "borders" of above product are linear.

Cplex can basically solve some classes of quadratic problems. Judging by your error message, your problem does not belong in there. So for solving this problem, you will probably need to stick to a general purpose NLP solver. A sample list of solvers can be found here, all of which can be triggered by the software AMPL, or can be used standalone. I am no expert here, so I can not give advice which solver should be preferred for your problem.

Regards, Martin