sepa_flower.h File Reference

Detailed Description

flower-inequality separator

Author

Matthias Walter

Separator for flower inequalities that are valid for the mulitlinear polytope \( P(G) \) of a hypergraph \( G = (V,E) \), defined as the convex hull of all vectors \( z \in \{0,1\}^{V + E} \) that satisfy \( z_e = \prod_{v \in e} z_v \) for all \( e \in E \). In other words, the variable associated with each (hyper-)edge is equal to the product of the variables associated with the vertices.

The hypergraph \( G \) is computed in the first separation round in which this separator is called. The edges correspond to all AND constraints (see cons_and.h), where \( z_e \) is the resultant \( r \) of \( r = x_1 \land x_2 \land \dotsb \land x_n \) and its incident vertices correspond to the \( x_i \). Moreover, also (nonlinear) product expressions (see expr_product.h) are scanned. For these, the involved variables are not necessarily binary, i.e., we have \( \ell_i \leq x_i \leq u_i \), and there might be an additional constant scaling factor \( c \). Such expressions \( r = c \prod\limits_{i=1}^n x_i \) are only taken into account if \( \ell_i \geq 0 \) for all \( i \) since in this case the cut can be applied to the space \( (r',x') \) with \( r' = \frac{ r }{ c \cdot u_1 \cdot u_2 \cdot \dotsc \cdot u_n } \) and \( x'_i = \frac{ x_i }{ u_i } \) for all \( i \).

Flower inequalities

The implemented cuts are k-flower inequalities for \( k=1,2 \). Such a cut is determined by a base edge \( e \) and \( k \) adjacent edges \( f_1, f_2, \dotsc, f_k \) that satisfy \( f_i \cap e \neq \emptyset \) but are disjoint in \( e \), i.e., \( f_i \cap f_j \cap e = \emptyset \) for all \( i \neq j \) holds. The set \( R \) of remaining nodes is defined as \( R := e \setminus \bigcup_{i=1}^k f_i \). The inequality reads

\[ z_e + \sum\limits_{i=1}^k (1-z_{f_i}) + \sum\limits_{v \in R} (1-z_v) \geq 1. \]

Validity follows from the fact that the left-hand side is a sum of nonnegative binary terms, and can thus only be violated if (in particular) \( z_{f_i} = 1 \) for \( i=1,2,\dotsc,k \) and \( z_v = 1 \) for all \( v \in R \) holds. This, however, implies \( z_v = 1 \) for all \( v \in e \) and thus \( z_e = 1 \).

Separation can either be done in time \( \mathcal{O}( |E|^{k+1} ) \) by enumeration or as follows: Replacing an adjacent edge \( f_i \) by another edge \( f_i' \) with the same overlap with the base edge, i.e., \( f'_i \cap e = f_i \cap e \) improves the violation if \( 1-z_{f'_i} < 1 - z_{f_i} \). Consequently, we compute the set of all overlap sets \( \{ e \cap f \mid e,f \in E \} \) (see hypergraph.h) and compute \( \min \{ 1-z_e \mid e \in E : U \subseteq e \} \) for all such \( U \). If the number of overlap sets incident to an edge is constant (say, if \( |e| \) is constant), then the running time reduces to \( \mathcal{O} ( |E| ) \).

Definition in file sepa_flower.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeSepaFlower (SCIP *scip)