Solving Constraint Integer Programs

sepa_convexproj.h File Reference

Detailed Description

convexproj separator

Felipe Serrano

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 separators 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

\[ \min || x - x_0 ||^2 \\ \]

\[ s.t. \; g_j(x) \le 0 \, \forall j=1,\ldots,m \\ \]

By default, 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 by 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 \]

Definition in file sepa_convexproj.h.

#include "scip/def.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"

Go to the source code of this file.


SCIP_EXPORT SCIP_RETCODE SCIPincludeSepaConvexproj (SCIP *scip)