Function SCIPcomputeFacetVertexPolyhedralNonlinear 

pub unsafe extern "C" fn SCIPcomputeFacetVertexPolyhedralNonlinear(
    scip: *mut SCIP,
    conshdlr: *mut SCIP_CONSHDLR,
    overestimate: c_uint,
    function: Option<unsafe extern "C" fn(args: *mut f64, nargs: c_int, funcdata: *mut c_void) -> f64>,
    fundata: *mut c_void,
    xstar: *mut f64,
    box_: *mut f64,
    nallvars: c_int,
    targetvalue: f64,
    success: *mut c_uint,
    facetcoefs: *mut f64,
    facetconstant: *mut f64,
) -> SCIP_RETCODE

computes a facet of the convex or concave envelope of a vertex polyhedral function

If \f$ f(x) \f$ is vertex-polyhedral, then \f$ g \f$ is a convex underestimator if and only if \f$ g(v^i) \leq f(v^i), \forall i \f$, where \f$ { v^i }_{i = 1}^{2^n} \subseteq \mathbb R^n \f$ are the vertices of the domain of \f$ x \f$, \f$ [\ell,u] \f$. Hence, we can compute a linear underestimator by solving the following LP (we don’t necessarily get a facet of the convex envelope, see below):

\f{align*}{ \max , & \alpha^T x^* + \beta \ s.t. ; & \alpha^T v^i + \beta \le f(v^i), , \forall i = 1, \ldots, 2^n \f}

In principle, one would need to update the LP whenever the domain changes. However, \f$ [\ell,u] = T([0, 1]^n) \f$, where \f$ T \f$ is an affine linear invertible transformation given by \f$ T(y)_i = (u_i - \ell_i) y_i + \ell_i \f$. Working with the change of variables \f$ x = T(y) \f$ allows us to keep the constraints of the LP, even if the domain changes. Indeed, after the change of variables, the problem is: find an affine underestimator \f$ g \f$ such that \f$ g(T(y)) \le f(T(y)) \f$, for all \f$ y \in [0, 1]^n \f$. Now \f$ f(T(y)) \f$ is componentwise affine, but still satisfies that \f$ g \f$ is a valid underestimator if and only if \f$ g(T(u)) \leq f(T(u)), \forall u \in {0, 1}^n \f$. So we now look for \f$ \bar g(y) := g(T(y)) = g(((u_i - \ell_i) y_i + \ell_i)_i) = \bar \alpha^T y + \bar \beta \f$, where \f$ \bar \alpha_i = (u_i - \ell_i) \alpha_i \f$ and \f$ \bar \beta = \sum_i \alpha_i \ell_i + \beta \f$. So we find \f$ \bar g \f$ by solving the LP:

\f{align*}{ \max , & \bar \alpha^T T^{-1}(x^*) + \bar \beta \ s.t. ; & \bar \alpha^T u + \bar \beta \le f(T(u)), , \forall u \in {0, 1}^n \f}

and recover \f$ g \f$ by calculating \f$ \bar \alpha_i = (u_i - \ell_i) \alpha_i, \bar \beta = \sum_i \alpha_i \ell_i + \beta \f$. Notice that \f$ f(T(u^i)) = f(v^i) \f$ so the right hand side doesn’t change after the change of variables.

Furthermore, the LP has more constraints than variables, so we solve its dual: \f{align*}{ \min , & \sum_i \lambda_i f(v^i) \ s.t. ; & \sum_i \lambda_i u^i = T^{-1}(x^*) \ & \sum_i \lambda_i = 1 \ & \forall i, , \lambda_i \geq 0 \f}

In case we look for an overestimate, we do exactly the same, but have to maximize in the dual LP instead of minimize.

Technical and implementation details

-# \f$ U \f$ has exponentially many variables, so we only apply this separator for \f$n\f$ ≤ \ref SCIP_MAXVERTEXPOLYDIM. -# If the bounds are not finite, there is no underestimator. Also, \f$ T^{-1}(x^) \f$ must be in the domain, otherwise the dual is infeasible. -# After a facet is computed, we check whether it is a valid facet (i.e. we check \f$ \alpha^T v + \beta \le f(v) \f$ for every vertex \f$ v \f$). If we find a violation of at most ADJUSTFACETFACTOR * SCIPgetLPFeastol(), then we weaken \f$ \beta \f$ by this amount, otherwise, we discard the cut. -# If a variable is fixed within tolerances, we replace it with its value and compute the facet of the remaining expression. Note that since we are checking the cut for validity, this will never produce wrong result. -# If \f$ x^ \f$ is in the boundary of the domain, then the LP has infinitely many solutions, some of which might have very bad numerical properties. For this reason, we perturb \f$ x^* \f$ to be in the interior of the region. Furthermore, for some interior points, there might also be infinitely many solutions (e.g. for \f$ x y \f$ in \f$ [0,1]^2 \f$ any point \f$ (x^, y^) \f$ such that \f$ y^* = 1 - x^* \f$ has infinitely many solutions). For this reason, we perturb any given \f$ x^* \f$. The idea is to try to get a facet of the convex/concave envelope. This only happens when the solution has \f$ n + 1 \f$ non zero \f$ \lambda \f$’s (i.e. the primal has a unique solution). -# We need to compute \f$ f(v^i) \f$ for every vertex of \f$ [\ell,u] \f$. A vertex is encoded by a number between 0 and \f$ 2^n - 1 \f$, via its binary representation (0 bit is lower bound, 1 bit is upper bound), so we can compute all these values by iterating between 0 and \f$ 2^n - 1 \f$. -# To check that the computed cut is valid we do the following: we use a gray code to loop over the vertices of the box domain w.r.t. unfixed variables in order to evaluate the underestimator. To ensure the validity of the underestimator, we check whether \f$ \alpha v^i + \beta \le f(v^i) \f$ for every vertex \f$ v^i \f$ and adjust \f$ \beta \f$ if the maximal violation is small.

@todo the solution is a facet if all variables of the primal have positive reduced costs (i.e. the solution is unique). In the dual, this means that there are \f$ n + 1 \f$ variables with positive value. Can we use this or some other information to handle any of both cases (point in the boundary or point in the intersection of polytopes defining different pieces of the convex envelope)? In the case where the point is in the boundary, can we use that information to maybe solve another to find a facet? How do the polytopes defining the pieces where the convex envelope is linear looks like, i.e, given a point in the interior of a facet of the domain, does the midpoint of the segment joining \f$ x^* \f$ with the center of the domain, always belongs to the interior of one of those polytopes?