SCIP
Solving Constraint Integer Programs
sepa_convexproj.h File Reference
Detailed Description
convexproj separator
This separator receives a point \( x_0 \) to separate, projects it onto a convex relaxation of the current problem and then generates gradient cuts at the projection.
In more detail, the separator builds and stores a convex relaxation of the problem
\[ C = \{ x \colon g_j(x) \le 0 \, \forall j=1,\ldots,m \} \]
where each \( g_j \) is a convex function and computes the projection by solving
\begin{align} \min \; & || x - x_0 ||^2 \\ s.t. \; & g_j(x) \le 0 & \forall j=1,\ldots,m. \end{align}
By default, if enabled, the separator runs only if the convex relaxation has at least one nonlinear convex function.
The separator generates cuts for constraints which were violated by the solution we want to separate and active at the projection. If the projection problem is not solved to optimality, it still tries to add a cut at the best solution found. In case that the projection problem is solved to optimality, it is guaranteed that a cut separates the point. To see this, remember that \( z \) is the projection if and only if
\[ \langle x - z, z - x_0 \rangle \ge 0 \, \forall x \in C \\ \]
This inequality is violated for \( x = x_0 \). On the other hand, one of the optimality conditions of the projection problem at the optimum looks like
\[ 2 (z - x_0) + \sum_j \lambda_j \nabla g_j(z) = 0. \]
Now suppose that the no gradient cut at \( z \) separates \( x_0 \), i.e.,
\[ g_j(z) + \langle \nabla g_j(z), x_0 - z \rangle \le 0. \]
Multiplying each inequality with \( \lambda_j \ge 0 \) and summing up, we get the following contradiction:
\[ \langle -2(z - x_0), x_0 - z \rangle \le 0. \]
This separator is currently disabled by default. It requires additional tuning to be enabled by default. However, it may be useful to enable it on instances with convex nonlinear constraints if SCIP spends many iterations in the separation loop without doing sufficient progress.
Definition in file sepa_convexproj.h.
Go to the source code of this file.
Functions | |
| SCIP_RETCODE | SCIPincludeSepaConvexproj (SCIP *scip) |