3
$\begingroup$

I have the following question:

I have a non-convex QCP model. In the parameter description for method it says that "Only barrier is available for continuous QCP models". However, the dual simplex algorithm (i.e. method 1) is used automatically. Does my model become MIQCP by setting NonConvex = 2 or how can I understand this?

$\endgroup$
2
$\begingroup$

I'm not familiar with what GUROBI does exactly, but continuous non-convex QCPs are solved using continuous branch-and-bound. This involves generating a linear relaxation of the problem which is solved at every node of the BnB tree, along with local optimisation of QCPs to get primal solutions (until we hit the global optimum).

The linear relaxations would typically be solved using Dual Simplex.

An interesting special case is if your QCP has complementarity constraints, which solvers typically (but not always) transform to MI linear constraints. Depending on the outcome, the problem can be fully linearised, in which case it's solved as an MILP, or partially linearised, in which case it's solved as an MIQCP.

From GUROBI's manual however, it's quite clear:

In the current release, the default Automatic (-1) setting will typically choose non-deterministic concurrent (Method=3) for an LP, barrier (Method=2) for a QP or QCP, and dual (Method=1) for the MIP root node. Only the simplex and barrier algorithms are available for continuous QP models. Only primal and dual simplex are available for solving the root of an MIQP model. Only barrier is available for continuous QCP models.

They specifically say that only barrier is available for continuous QCP, and that Automatic mode will select barrier (Method=2) for those problems.

Even though it doesn't say so, I would expect it to use Dual Simplex if the QCP problem has e.g. complementarity constraints and is transformed to an MILP.

Generally speaking, if you see that Dual Simplex was used in the output, it most likely means that it reformulated your problem to an MILP by exploiting special structure.

$\endgroup$
4
  • $\begingroup$ Thank you for the detailed answer. Here is also the link to the method selection. But if I have understood correctly, it has its justification that the dual simplex is used, since it is a non-convex QCP model or? gurobi.com/documentation/9.1/refman/method.html $\endgroup$ May 4 at 12:32
  • $\begingroup$ @Handballer73 I updated the answer, hopefully it helps you out :) $\endgroup$ May 4 at 16:32
  • $\begingroup$ thank you very much, that really helped me a lot $\endgroup$ May 5 at 7:06
  • $\begingroup$ @Handballer73 Glad to hear! $\endgroup$ May 5 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.