3

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.

Rodrigo de Azevedo
  • 1,097
  • 9
  • 17
john m
  • 37
  • 1
  • 4

1 Answers1

3

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

Martin
  • 328
  • 1
  • 6
  • Martin, thank you very much for your response. It is very useful. The variables are not continuous, all of them are integers, instead. So in this case, can I use [link] (http://www.leandro-coelho.com/linearization-product-variables/) the link to make them linear? However, as far as I understand, I can still need an NLP solver, if I receive the error before? So steps, trying to linearize the formulation, if I still get the error than go with the NLP solvers, is it right? – john m Mar 12 '14 at 11:26
  • When your variables are integer, the problem can be expressed as a mixed integer linear problem, i.e. all constrains are linear - you "circumvent" quadratic expressions by integrality conditions. So it can be solved by standard cplex (you don't need the quadratic solver) by simplex and branch & bound. You should not get an error message when all products are linearized, however it might be that solution speed is unsatisfying, depending on your problems size. – Martin Mar 12 '14 at 12:58
  • Martin, linearization of product link gives hints about binary variables, however the variables in my model is general integer (can be 3, 4, etc.). Is there a way to linearize these conditions as well? – john m Mar 12 '14 at 21:40
  • 1
    It is important that each of your integer variables is bounded by a number n (I think otherwise it doesn't work). Then, you can replay each integer variable I by a series of binary variables x_i, i.e. I = 1x_1+2x_2+ 3x_3 ... + nx_n. Each products of integers is then a product of binaries. They you can linearize each product of the corresponding binary variables. The "blowup" makes it ineffective/efficient for larger problems... – Martin Mar 13 '14 at 15:41