Simultaneous Convexification of Bilinear Functions over Polytopes with Application to Network Interdiction
提出一种构造性方法，用于得到双线性函数图集的凸包线性描述，可应用于网络阻断问题的对偶公式强化，并给出初步数值结果。
We study the simultaneous convexification of graphs of bilinear functions $g^k({x};{y}) = {y}^{\intercal} A^k {x}$ over ${x} \in \ensuremath{\Xi} = \{ {x} \in [0,1]^n \, | \, E{x} \geq {f} \}$ and ${y} \in \Delta_m = \{ {y} \in {R}_+^{m} \, | \, {1^{\intercal}y} \leq 1 \}$. We propose a constructive procedure to obtain a linear description of the convex hull of the resulting set. This procedure can be applied to derive convex and concave envelopes of certain bilinear functions, to study unary expansions of integer variables in mixed integer bilinear sets, and to obtain convex hulls of sets with complementarity constraints. Exploiting the structure of $\Xi$, the procedure naturally yields stronger linearizations for bilinear terms in a variety of practical settings. In particular, we demonstrate the effectiveness of the approach by strengthening the traditional dual formulation of network interdiction problems and report encouraging preliminary numerical results.