# Cutting Planes for Mathematical Programming:
Separation from Convex Hulls

Renaud Chicoisne

► To cite this version:

Renaud Chicoisne. Cutting Planes for Mathematical Programming: Separation from Convex Hulls.
2020. hal-02982831v2

HAL Id: hal-02982831

https://hal.science/hal-02982831v2

Preprint submitted on 17 Nov 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Cutting Planes for Mathematical Programming:
Separation from Convex Hulls

Renaud Chicoisne[0000-0002-5001-4350]

ULB, Brussels, Belgium and INOCS, INRIA Lille Nord-Europe, France
renaud.chicoisne@gmail.com

**Abstract.** Cutting planes methods are of crucial importance to solve huge or nonconvex optimization problems. Minimizing a linear functional over general sets $\mathcal{F}$ may not be possible directly, however, optimizing on a wisely chosen relaxation $\mathcal{R} \supseteq \mathcal{F}$ can be computationally tractable. Using the equivalence between optimization and separation, a popular approach consists in optimizing over a lightweight relaxation $\mathcal{R}^0$ and separate the resulting incumbent from other cherry-picked relaxations $\mathcal{R}$ via cutting planes. Doing so, we implicitly optimize over $\mathcal{R}^0$ intersected with $\mathcal{C}\mathcal{C}\mathcal{R}$, the closed convex hull of $\mathcal{R}$.

For any type of relaxation $\mathcal{R}$, we present a framework to efficiently separate an incumbent from $\mathcal{C}\mathcal{C}\mathcal{R}$, granted that optimizing a linear functional over $\mathcal{R}$ can be done efficiently. In particular, our approach can generate in an efficient way 1) Balas' disjunctive cuts without having to solve a problem being multiple times the size of the original (for mixed integer linear conic problems) nor using perspective functions (for nonlinear problems), 2) Boyd's Fenchel cuts (for mixed integer linear problems) without enumerating all combinations of a small number of the integer constrained variables and 3) The hull generated by a Dantzig-Wolfe (DW) scheme via cutting planes only.

In its classical use, DW is usable only when $\mathcal{F}$ exhibits a block-separable sub-structure. However, when facing a mixed integer problem with convex generalized nonlinear inequalities, given a partition of the variables, we show a generic way to construct a relaxation that is block-separable with respect to that partition.

**Keywords:** Mixed Integer Programming · Large Scale Optimization · Nonlinear Conic Optimization · Cutting Planes · Disjunctive cuts · Convexification · Decomposition Methods.

# 1 Introduction

## 1.1 Problem definition

Consider an optimization problem of the form:

$$ (P) \quad \min_{x} \{c^{\top} x : x \in \mathcal{F}\} := \min_{x} c^{\top} x \quad (1a) $$

$$ \text{s.t.} \quad x \in \mathcal{X} \quad (1b) $$

$$ x(\mathcal{Z}) \in \mathbb{Z}^{|\mathcal{Z}|}, \quad (1c) $$
where $\mathcal{X} \subseteq \mathbb{R}^n$, $\mathcal{Z} \subseteq [n]$, and $x(\mathcal{Z})$ is $x$ restricted to its components in $\mathcal{Z}$. This kind of problem can be difficult in general and a classical way to solve it relies on solving tractable relaxations of it, $\min_{x \in \mathbb{R}^0} c^\top x$, with $\mathcal{F} \subseteq \mathbb{R}^0$. A straightforward relaxation can be obtained by e.g. relaxing the integrality constraints (1c). There is no guarantee in general however, that the relaxation provides solutions $\bar{x}$ belonging to $\mathcal{F}$. Two popular devices are then used to exclude an infeasible incumbent $\bar{x}$ from the search: Split the feasibility set with a disjunction that excludes $\bar{x}$ using e.g. a Branch and Bound [43] and/or find a hyperplane $\eta \le \mu^\top x$ such that $\eta > \mu^\top \bar{x}$ and $\eta \le \mu^\top x$ for any $x \in \mathcal{F}$ i.e. that is satisfied by every feasible solution of $P$ but cuts away $\bar{x}$. Such an inequality that is satisfied by every point of $\mathcal{F}$ is said to be valid for $\mathcal{F}$.

In this paper, we focus on efficient ways to use the second method. In particular, given a relaxation $\mathcal{R} \supseteq \mathcal{F}$, we study the separation problem of 1) determining if $\bar{x} \in \text{cc} \mathcal{R}$ and 2) in the negative, find a valid inequality for $\text{cc} \mathcal{R}$ that is violated by $\bar{x}$. In particular, 1) we develop a generic framework allowing to efficiently separate from $\text{cc} \mathcal{R}$ granted that $\inf_{x \in \mathcal{R}} \mu^\top x$ is efficiently solvable for any $\mu$, that 2) allows to generate in a different way several existing classes of cuts that correspond to special cases of $\mathcal{R}$.

## 1.2 Literature review

Given a cone $\mathcal{C}$ and some function $f$, we say that $P$ is 1) Mixed Integer (MI) Non Linear Conic (NLCP) representable if $\mathcal{Z} \ne \emptyset$ and

$$ \mathcal{X} := \{x \in \mathbb{R}^n : -f(x) \in \mathcal{C}\}, $$

2) Non Linear (NLP) representable if $\mathcal{C} = \mathbb{R}_+^m$, 3) Linear Conic (LCP) representable if $f$ is a linear operator and 4) Mixed Integer Linear (LP) representable if $\mathcal{C} = \mathbb{R}_+^m$ and $f$ is a linear operator.

The literature on cutting planes for MILPs is extensive: Mixed Integer Round- ing cuts (MIR) [34] and Chvátal-Gomory (CG) cuts [20, 25] make use of the simplex tableau of an optimal solution of the LP relaxation to exclude frac- tional incumbents $\bar{x}$. Zero-half cuts [16] are special MIR cuts whose separation is efficient. When $\mathcal{X}$ exhibits a special structure, powerful inequalities can be generated such as e.g. Cover Inequalities [3], Flow Cover Inequalities [35]; or using conflict graphs, clique cuts and Generalized Upper Bound cuts [2].

The hierarchies of relaxations of Sherali-Adams [39], Lovász-Schrijver [31], Balas-Ceria-Cornuéjols [5] or Lasserre [28] allow to lift $\mathcal{F}$ in extended spaces of higher dimensions - while possibly changing its nature, e.g. turning the contin- uous relaxation of the extended formulation into a Semidefinite Programming problem (SDP). While they grow exponentially in size, the resulting relaxations can be as strong as $\text{cc} \mathcal{F}$ when projected onto the original variables.

Several of these techniques have been extended beyond the MILP world, e.g. MIR cuts for MILCPs [17] and when $\mathcal{C}$ is defined by Second Order Cones [1]. For MINLPs, Reformulation Linearization Techniques (RLT) are specialized Lift- and-project methods that use the Sherali-Adams hierarchies to solve polynomial
optimization problems [40] or nonconvex quadratic optimization problems [41]. We now present an approach that is usable in all the aforementioned cases, from which we build the main engine of the present work.

Disjunctive cuts (DC) date back to the 70's with the pioneering work of Balas [4] to solve MILPs. It was shown that many classical cutting planes classes such as CG or MIR cuts were particular cases of DCs [6]. To illustrate its functioning, consider that we are provided a relaxation $\mathcal{R} \supseteq \mathcal{F}$ defined as the disjunction $\mathcal{R} := \bigcup_{h \in \mathcal{H}} \mathcal{R}_h$, with $\mathcal{R}_h := \{x : A^h x \ge b^h\}$ for each $h \in \mathcal{H}$. A valid cut for $\mathcal{R}$ that $\bar{x}$ does not satisfy is generated and appended to $\mathcal{R}^0$ to strengthen the relaxation. To do so, they make use of the following membership problem (MP), that is either infeasible - if $\bar{x} \notin \mathcal{C} \mathcal{C}$ - or has objective value zero:

$$ \inf_{\theta, x} 0 \qquad (2a) $$

$$ \text{s.t.} \quad \bar{x} = \sum_{h \in \mathcal{H}} x^h \qquad (2b) $$

$$ 1 = \sum_{h \in \mathcal{H}} \theta_h, \quad \theta \ge 0 \qquad (2c) $$

$$ A^h x^h \ge \theta_h b^h, \quad \forall h \in \mathcal{H}. \qquad (2d) $$

If MP is feasible, no separation is possible as $\bar{x} \in \mathcal{C} \mathcal{C}$, otherwise consider its LP dual - called the *Cut Generating Problem* (CGP):

$$ \sup_{\mu, \eta, \pi} \eta - \bar{x}^{\top} \mu \qquad (3a) $$

$$ \text{s.t.} \quad \mu = (A^h)^{\top} \pi^h, \quad \eta \le (b^h)^{\top} \pi^h, \quad \pi^h \ge 0, \quad \forall h \in \mathcal{H} \qquad (3b) $$

It is not difficult to see that whenever MP is infeasible, there is an extreme ray $(\tilde{\mu}, \tilde{\eta}, \tilde{\pi})$ of the polyhedron defined by (3b) such that $\tilde{\eta} - \bar{x}^{\top} \tilde{\mu} > 0$. In consequence $\tilde{\eta} \le \bar{x}^{\top} \tilde{\mu}$ is a valid inequality for $\mathcal{C} \mathcal{C}$ that $\bar{x}$ does not satisfy. In practice, it is beneficial to consider normalized versions of MP (CGP) to turn it feasible (bounded): Given a norm $|| \cdot ||$, let us consider the *Normalized MP* (NMP)

$$ \inf_{\theta, x} \left\{ \left\| \bar{x} - \sum_{h \in \mathcal{H}} x^h \right\| : (2c), (2d) \right\}, $$

and the *Normalized CGP* (NCGP), which is none other than its conic dual:

$$ \sup_{\mu, \eta, \pi} \{ \eta - \bar{x}^{\top} \mu : (3b), ||\mu||_* \le 1 \}. $$

Depending on the normalization used, NCGP can behave differently both in terms of solution time and quality of the cut generated [8, 14, 15, 19, 22, 38]. It is important to notice that if the number of constraints defining each $\mathcal{R}_h$ is similar to that of $\mathcal{F}$, MP (NMP) and CGP (NCGP) are roughly $|\mathcal{H}|$ times larger than P. In [8] they generate split cuts - where $|\mathcal{H}| = 2$ - for MILPs by using a special
normalization that reduces the size of NCGP to roughly the same size as that of the original LP relaxation. In [7, 29], DCs are extended to MILCP-representable sets $\mathcal{R}_h$. For convex MINLP-representable sets $\mathcal{R}_h$, perspective functions are used to cast MP as a convex NLP [42]. However, using perspectives can be problematic because of the eventual presence of nondifferentiabilities [26].

Even if they are not tagged as DCs for MILPs, methodologies to generate DCs with discrete sets $\mathcal{R}$ are presented in [9–12, 18, 36, 44], The idea is based on the enumeration of small subsets of integer constrained variables and solve either the LP relaxation (wrt to the non-enumerated variables) or a tailored relaxation that can be weak but is extremely fast to solve. In particular, [36] shows a way to solve NCGP for disjunctions defined with linear inequalities without using the copies. Using strong LP duality, NCGP is shown to be solvable with cutting planes and a succession of MILPs over $\mathcal{R}$. It is important to remark that most works about DCs use NMP - that provides a representation of cc $\mathcal{R}$ - as the base ingredient. After taking the conic dual, are they able to certify that $\bar{x} \notin$ cc $\mathcal{R}$. Because there is no generic way to have explicit strong duals in the nonlinear world, NCGP is solved implicitly, further motivating our dual-free approach.

## 1.3 Contributions and outline

We introduce the notation in Section 2. Our contributions are as follows: In Section 3, we first provide a generalization to generic relaxations $\mathcal{R}$ an idea of [36] for MILPs, and exhibit directly NCGP without needing NMP nor additional copies. Second, we propose an efficient separation routine provided that $\inf_{x \in \mathcal{R}} \mu^\top x$ is efficiently solvable for any cost vector $\mu$.

We extend these efficient separation schemes to well-known existing families of cuts in Section 4 by using specific sets $\mathcal{R}$.

In Section 5 we propose a new methodology inspired from Column Generation [32] that partially convexifies $\mathcal{F}$ when $\mathcal{X}$ exhibits a separable structure, allowing *de facto* to use DW implicitly by generating cuts only. We finally extend to MINLCPS an idea of Boyd [9] and the so-called *Fenchel cuts* for MILPs, where generic separable relaxations can be constructed when $\mathcal{F}$ is MILP-representable and *no structure is present*. We conclude by some remarks and describe future research directions in Section 6.

## 2 Background

Given a norm $|| \cdot ||$, we call $|| \cdot ||_*$ the norm dual to $|| \cdot ||$ defined as $||w||_* := \sup_{v \in \mathcal{V}} \{v^\top w : ||v|| \le 1\}$. The indicator function $\mathbb{1}[\mathcal{V}]$ of a set $\mathcal{V}$ is defined as: $\mathbb{1}[\mathcal{V}](v) := 0$ if $v \in \mathcal{V}$ and $+\infty$ otherwise. We call respectively $\text{cl} \mathcal{V}$, $\text{cc} \mathcal{V}$ and $\text{int} \mathcal{V}$ the closure, the closed convex hull and the interior of $\mathcal{V}$. $\text{recc} \mathcal{V} := \{w : v + tw \in \mathcal{V}, \forall v \in \mathcal{V}, t \ge 0\}$ is called the recession cone of $\mathcal{V}$, $\Pi[\mathcal{V}](w) := \arg \min_{v \in \mathcal{V}} ||v - w||$ is the projection of $w$ onto $\mathcal{V}$ and the distance between $w$ and $\mathcal{V}$ is $\mathcal{D}[\mathcal{V}](w) := \min_{v \in \mathcal{V}} ||v - w||$. We define the $K$-dimensional simplex as
$\Delta_K := \{t \in \mathbb{R}_+^K : \sum_{k=1}^K t_k = 1\}$. For any $v \in \mathbb{R}$ let us define $[v]_+ := \max(0, v)$ and $[v]_- := \max(0, -v)$.

The convex conjugate of a real valued function $\varphi$ is $\varphi^*(w) := \sup_v \{v^\top w - \varphi(v)\}$, and its convex biconjugate - also called Fenchel transform - is $\varphi^{**} = (\varphi^*)^*$. 

*Remark 1.* Given a set $\mathcal{V}$, we have [37]: $(\mathbb{I}[\mathcal{V}])^{**} = \mathbb{I}[\mathrm{cc} \, \mathcal{V}] = (\mathbb{I}[\mathrm{cc} \, \mathcal{V}])^{**}$.

A set $\mathcal{K}$ is a cone if for every $v \in \mathcal{K}$ and $t \ge 0$, we have $tv \in \mathcal{K}$. For any convex cone $\mathcal{K}$ we denote $v \preceq_{\mathcal{K}} w$ iff $w - v \in \mathcal{K}$. We call $\mathcal{K}^*$ the cone dual to a cone $\mathcal{K}$ the set defined as $\mathcal{K}^* := \{\pi : \langle \pi, v \rangle \ge 0, \forall v \in \mathcal{K}\}$. The conjugate $V^*$ of a linear operator $V$ is such that $\langle V \cdot, \cdot \rangle = \langle \cdot, V^* \cdot \rangle$. Given a convex cone $\mathcal{K}$ and a function $\varphi$, $\varphi$ is $\mathcal{K}$-convex [13] iff $\varphi(tv + (1-t)w) \preceq_{\mathcal{K}} t\varphi(v) + (1-t)\varphi(w), \forall v, w, \forall t \in [0, 1]$. Alternatively, if $\varphi$ is differentiable, $\varphi$ is $\mathcal{K}$-convex iff $\varphi(v) \succeq_{\mathcal{K}} \varphi(w) + D\varphi(w)(v-w), \forall v, w \in \mathrm{dom} f$, where $D\varphi(w)$ is the Jacobian of $\varphi$ at $w$. When convenient, we use the equivalent notation $D\varphi(w)v = \sum_j D^j\varphi(w)v_j$.

# 3 Membership conditions and efficient separation

In this document, our goal is to separate an incumbent $\bar{x} \in \mathcal{R}^0$ from the closed convex hull of some nonempty - and bounded when convenient - relaxation $\mathcal{R} \supseteq \mathcal{F}$. In other words, the basic question we aim to answer is twofold: 1) Does $\bar{x}$ belong to $\mathrm{cc} \, \mathcal{R}$? 2) In the negative, how can we find a valid inequality for $\mathrm{cc} \, \mathcal{R}$ that separates $\bar{x}$? The first part is naturally answerable by either checking if $\mathbb{I}[\mathrm{cc} \, \mathcal{R}](\bar{x}) \le 0$ or $\mathrm{D}[\mathrm{cc} \, \mathcal{R}](\bar{x}) \le 0$ - if we can compute these quantities. We answer both questions in what follows.

## 3.1 Membership conditions

We begin by showing that optimizing a linear functional over a set or over its closed convex hull yields the same optimal value.

**Proposition 1.** For any set $\mathcal{V}$, we have $\bar{\omega} = \omega$ where

$$ \bar{\omega} := \inf_v \{ \alpha^\top v : v \in \mathrm{cc} \, \mathcal{V} \} \quad \text{and} \quad \omega := \inf_v \{ \alpha^\top v : v \in \mathcal{V} \}. $$

*Proof.* Because $\mathcal{V} \subseteq \mathrm{cc} \, \mathcal{V}$, we have $\bar{\omega} \le \omega$. Second, for any $v \in \mathcal{V}$, we have

$$ \omega \le \alpha^\top v. \quad (4) $$

Consider some $\theta \in \Delta_K$ in the $K$-simplex, and $K$ sequences $v^{kp} \in \mathcal{V}^N$ such that $v^{kp} \to v^k \in \mathrm{cl} \, \mathcal{V}$. The sum over $k \in [K]$ of each $\theta_k \times (4)$ at $v = v^{kp}$ becomes: $\sum_{k=1}^K \theta_k \omega = \omega \le \alpha^\top \sum_{k=1}^K \theta_k v^{kp} \to \alpha^\top \sum_{k=1}^K \theta_k v^k$. We then have $\omega \le \alpha^\top v$ for any $v \in \mathrm{cc} \, \mathcal{V}$. We finish by taking the infimum over $\mathrm{cc} \, \mathcal{V}$.

Finding a tuple $(\tilde{\mu}, \tilde{\eta})$ such that $\tilde{\eta} \le \tilde{\mu}^\top x$ is 1) violated by $\bar{x}$ and 2) valid for $\mathcal{R}$ boils down to 1) maximize an eventual violation $\eta - \mu^\top \bar{x}$ such that 2) for every $x \in \mathcal{R}$, $\eta \le \mu^\top x$. This is done by checking if $\sup_{\mu, \eta} \{\eta - \mu^\top \bar{x} : \eta \le \inf_{x \in \mathcal{R}} \mu^\top x\} = \sup_{\mu} \inf_{x \in \mathcal{R}} \mu^\top(x - \bar{x})$ has a positive optimal value. We now show that the last problem is our CGP, and forcing $\mu$ to satisfy $||\mu||_* \le 1$ provides us our NCGP:
**Proposition 2.** $\mathbb{I}[cc\,\mathcal{R}](\bar{x}) := \sup_{\mu} \inf_{x \in \mathcal{R}} (x - \bar{x})^{\top}\mu$. If $\mathcal{R}$ is bounded, then

$$ \mathcal{D}[cc\,\mathcal{R}](\bar{x}) := \sup_{||\mu||_* \le 1} \inf_{x \in \mathcal{R}} (x - \bar{x})^{\top}\mu. $$

*Proof.* From Remark 1, we know that $\mathbb{I}[cc\,\mathcal{R}](\bar{x}) = (\mathbb{I}[\mathcal{R}])^{**}(\bar{x}) = \sup_{\mu}\{\mu^{\top}\bar{x} - \sup_{x}\{x^{\top}\mu - \mathbb{I}[\mathcal{R}](x)\}\}$. Using the change of variables $\mu \leftarrow -\mu$, we obtain the first result. By definition

$$ \mathcal{D}[cc\,\mathcal{R}](\bar{x}) = \inf_{x \in cc\,\mathcal{R}} ||x - \bar{x}|| = \inf_{x \in cc\,\mathcal{R}, \delta, \delta_0} \{\delta_0 : ||\delta|| \le \delta_0, \delta = x - \bar{x}\}. $$

The problem in $(\delta, \delta_0)$ is a strictly feasible LCP, making strong duality hold:

$$ \begin{aligned} \mathcal{D}[cc\,\mathcal{R}](\bar{x}) &= \inf_{x \in cc\,\mathcal{R}} \sup_{\mu, \alpha, \alpha_0} \{\mu^{\top}(x - \bar{x}) : ||\alpha||_* \le \alpha_0, \mu + \alpha = 0, \alpha_0 = 1\} \\ &= \inf_{x \in cc\,\mathcal{R}} \sup_{\mu} \{\mu^{\top}(x - \bar{x}) : ||\mu||_* \le 1\}. \end{aligned} $$

$(x, \mu) \mapsto \mu^{\top}(x - \bar{x})$ is bilinear, $cc\,\mathcal{R}$ and $\{\mu : ||\mu||_* \le 1\}$ are compact so we can swap the inf and sup [27]: $\mathcal{D}[cc\,\mathcal{R}](\bar{x}) = \sup_{||\mu||_* \le 1} \inf_{x \in cc\,\mathcal{R}} \mu^{\top}(x - \bar{x})$. From Proposition 1, we can replace $x \in cc\,\mathcal{R}$ by $x \in \mathcal{R}$, obtaining the result.

## 3.2 Cut retrieval

Following the literature, we now work only with $\mathcal{D}[cc\,\mathcal{R}](\bar{x})$: as opposed to $\mathbb{I}[cc\,\mathcal{R}](\bar{x})$ it is bounded, which can avoid numerical problems in practice:

$$ \begin{aligned} (NCGP[\mathcal{R}](\bar{x}))\quad \mathcal{D}[cc\,\mathcal{R}](\bar{x}) &:= \sup_{\mu, \eta} \eta - \mu^{\top}\bar{x} \\ \text{s.t.} \quad &\eta \le \inf_{x \in \mathcal{R}} x^{\top}\mu \\ &||\mu||_* \le 1. \end{aligned} $$

**Proposition 3.** For any feasible solution $(\tilde{\mu}, \tilde{\eta})$ of $NCGP[\mathcal{R}](\bar{x})$, $\tilde{\eta} \le \tilde{\mu}^{\top}\bar{x}$ is a valid inequality for $cc\,\mathcal{R}$. Further, $\bar{x} \notin cc\,\mathcal{R}$ iff there is some feasible solution $(\tilde{\mu}, \tilde{\eta})$ of $NCGP[\mathcal{R}](\bar{x})$ such that $\tilde{\eta} > \tilde{\mu}^{\top}\bar{x}$

*Proof.* From Proposition 1, any $(\tilde{\mu}, \tilde{\eta})$ feasible for $NCGP[\mathcal{R}](\bar{x})$ satisfies $\tilde{\eta} \le \inf_{x \in \mathcal{R}} \tilde{\mu}^{\top}x = \inf_{x \in cc\,\mathcal{R}} \tilde{\mu}^{\top}x$, meaning that $\tilde{\eta} \le \tilde{\mu}^{\top}\bar{x}$ is valid for $cc\,\mathcal{R}$. Second, we know that $\bar{x} \notin cc\,\mathcal{R}$ iff $\mathcal{D}[cc\,\mathcal{R}](\bar{x}) > 0$, i.e. there is some $(\tilde{\mu}, \tilde{\eta})$ feasible for $NCGP[\mathcal{R}](\bar{x})$ with positive objective value, proving the result.

We now present an efficient way to solve $NCGP[\mathcal{R}](\bar{x})$.
### 3.3 Efficient cut generation

We define the core problem as follows:

$$ (CP[\mathcal{R}](\mu)) \quad \kappa[\mathcal{R}](\mu) := \inf_{x \in \mathcal{R}} \mu^\top x. $$

We now show how to take advantage of the structure of NCGP[$\mathcal{R}$]($\bar{x}$).

**Proposition 4.** For any $\tilde{\mu}$ such that $||\tilde{\mu}||_* \le 1$ and $\tilde{\mathcal{R}} \subseteq \mathcal{R}$, we have

$$ \kappa[\mathcal{R}](\tilde{\mu}) - \tilde{\mu}^{\top}\bar{x} \le \mathcal{D}[\mathrm{cc}\,\mathcal{R}](\bar{x}) \le \mathcal{D}[\mathrm{cc}\,\tilde{\mathcal{R}}](\bar{x}). $$

*Proof.* The first inequality comes from $\mathcal{D}[\mathrm{cc}\,\mathcal{R}](\bar{x}) = \sup_{||\mu||_* \le 1}\{\kappa[\mathcal{R}](\mu) - \mu^\top\bar{x}\}$. $\tilde{\mathcal{R}} \subseteq \mathcal{R}$ implies that for any $\mu$, $\kappa[\mathcal{R}](\mu) \le \kappa[\tilde{\mathcal{R}}](\mu)$, proving the second.

This suggests the following Column Generation approach: we first select a finite subset $\tilde{\mathcal{R}}$ of $\mathcal{R}$, then solve NCGP[$\tilde{\mathcal{R}}$]($\bar{x}$) that becomes the following LC problem

$$ \begin{array}{ll} \mathcal{D}[\mathrm{cc}\,\tilde{\mathcal{R}}](\bar{x}) := & \sup_{\mu, \eta} \eta - \mu^\top \bar{x} \\ \text{s.t.} & \eta \le x^\top \mu \\ & ||\mu||_* \le 1, \end{array} \quad , \forall x \in \tilde{\mathcal{R}} $$

with optimal solution $(\tilde{\mu}, \tilde{\eta})$, and dynamically append to $\tilde{\mathcal{R}}$ any optimal solution of the core problem $CP[\tilde{\mathcal{R}}](\tilde{\mu})$ if $\tilde{\eta} > \kappa[\tilde{\mathcal{R}}](\tilde{\mu})$. We stop whenever $\kappa[\tilde{\mathcal{R}}](\tilde{\mu}) - \tilde{\mu}^\top \bar{x} > 0$, in which case $\bar{x} \notin \mathrm{cc}\,\mathcal{R}$ and we have a cut available, or $\mathcal{D}[\mathrm{cc}\,\tilde{\mathcal{R}}](\bar{x}) \le 0$, in which case $\bar{x} \in \mathrm{cc}\,\mathcal{R}$. We summarize the procedure in Algorithm 1.

<table><caption>**Algorithm 1:** Cut generating procedure</caption><thead><tr><th></th><th>Data: A point x&#773;, a relaxation R &sup; F and a norm ||&middot;||.<br>Result: A certificate (&mu;&#771;, &eta;&#771;) if x&#773; &notin; cc R</th></tr></thead><tbody><tr><td>1</td><td>Set R&#771; = &empty;</td></tr><tr><td>2</td><td>repeat</td></tr><tr><td>3</td><td>Solve NCGP[R&#771;](x&#773;). Let (&mu;&#771;, &eta;&#771;) be an optimal solution;</td></tr><tr><td>4</td><td>if D[cc(R&#771;)](x&#773;) &le; 0 then</td></tr><tr><td>5</td><td>return x&#773; &isin; cc R;</td></tr><tr><td>6</td><td>Solve the core problem CP[R&#771;](&mu;&#771;). Let x&#773; be an optimal solution;</td></tr><tr><td>7</td><td>if &kappa;[R&#771;](&mu;&#771;) &gt; &mu;&#771;<sup>&top;</sup> x&#773; then</td></tr><tr><td>8</td><td>return (&mu;&#771;, &kappa;[R&#771;](&mu;&#771;));</td></tr><tr><td>9</td><td>if &kappa;[R&#771;](&mu;&#771;) &ge; &eta;&#771; then</td></tr><tr><td>10</td><td>return (&mu;&#771;, &eta;&#771;);</td></tr><tr><td>11</td><td>R&#771; &lleftarrow; R&#771; &cup; {x&#773;};</td></tr></tbody></table>
**Proposition 5.** When Algorithm 1 terminates, either $x \in \text{cc } \mathcal{R}$ or it returns a "certificate" $(\tilde{\mu}, \tilde{\eta})$ defining a hyperplane separating $\bar{x}$ from $\text{cc } \mathcal{R}$.

*Proof.* Recall that from Proposition 4, we have

$$ \kappa[\mathcal{R}](\tilde{\mu}) - \tilde{\mu}^{\top}\bar{x} \le \mathcal{D}[\text{cc } \mathcal{R}](\bar{x}) \le \mathcal{D}[\text{cc } \tilde{\mathcal{R}}](\bar{x}). \quad (5) $$

1. If we terminate at Line 4, (5) implies that $\mathcal{D}[\text{cc } \mathcal{R}](\bar{x}) = 0$, i.e. $\bar{x} \in \text{cc } \mathcal{R}$.

2. By definition, $(\tilde{\mu}, \kappa[\mathcal{R}](\tilde{\mu}))$ is always feasible for NCGP[$\mathcal{R}$]($\bar{x}$). From Proposition 3, we know that $\tilde{\mu}^{\top}x \ge \kappa[\mathcal{R}](\tilde{\mu})$ is valid for $\text{cc } \mathcal{R}$. If we stop at Line 7, $\bar{x}$ does not satisfy the inequality, (5) implies that $\mathcal{D}[\text{cc } \mathcal{R}](\bar{x}) > 0$: $\bar{x} \notin \text{cc } \mathcal{R}$.

3. Because $\mathcal{D}[\text{cc } \tilde{\mathcal{R}}](\bar{x}) = \tilde{\eta} - \tilde{\mu}^{\top}\bar{x}$, (5) implies $\kappa[\mathcal{R}](\tilde{\mu}) \le \tilde{\eta}$. If we stop at Line 9, $\kappa[\mathcal{R}](\tilde{\mu}) = \tilde{\eta}$ and $(\tilde{\mu}, \tilde{\eta})$ is feasible for NCGP[$\mathcal{R}$]($\bar{x}$) with objective value

$$ \tilde{\eta} - \tilde{\mu}^{\top}\bar{x} = \kappa[\mathcal{R}](\tilde{\mu}) - \tilde{\mu}^{\top}\bar{x} \le \mathcal{D}[\text{cc } \mathcal{R}](\bar{x}) \le \mathcal{D}[\text{cc } \tilde{\mathcal{R}}](\bar{x}) = \tilde{\eta} - \tilde{\mu}^{\top}\bar{x}. $$

At this point, we already stated that $\mathcal{D}[\text{cc } \tilde{\mathcal{R}}](\bar{x}) > 0$, obtaining $\tilde{\mu}^{\top}\bar{x} > \tilde{\eta}$.

**Remark 2.** Line 7 of Algorithm 1 is an early stopping criterion and can be dropped at will as the certificate returned already cuts $\bar{x}$ and is valid for $\text{cc } \mathcal{R}$, but may not be the deepest cut available. In other words, a suboptimal solution does not necessarily provide a cut that exposes $\text{cc } \mathcal{R}$, i.e. intersecting with it.

**Remark 3.** The relaxation $\mathcal{R}$ can assume any form as long as $\text{CP}[\mathcal{R}](\mu)$ is efficiently solvable for any $\mu$, condition on which our framework heavily relies on.

**Remark 4.** If $\mathcal{R}$ is not bounded, $\text{CP}[\mathcal{R}](\tilde{\mu})$ can be unbounded from below. If a certificate of unboundedness is available - i.e. some $\tilde{x} \in \text{recc } \text{cc } \mathcal{R}$ such that $\tilde{\mu}^{\top}\tilde{x} < 0$ - we must add the cut $0 \le \mu^{\top}\tilde{x}$ instead of incrementing $\tilde{\mathcal{R}} \leftarrow \tilde{\mathcal{R}} \cup \{\tilde{x}\}$.

# 4 Special cases

Using specific relaxations $\mathcal{R}$, we can generate several existing types of cuts. We point out the advantages of our method when $\mathcal{R}$ has an exploitable structure.

## 4.1 Lift-and-project

Some problems $P$ admit strong extended formulations $\mathcal{R}$ such as SDP relaxations [24, 30] or hierarchies. If $\mathcal{R}$ has nonempty interior and is representable with LC inequalities, i.e. $\mathcal{R} := \{x : \exists y : Vx + Wy - d \in \mathcal{K}\}$, it is not difficult to see that the core problem is equivalent to $\kappa[\mathcal{R}](\mu) = \sup_{\pi}\{\langle d, \pi \rangle : \pi \in \mathcal{K}^*, V^*\pi = \mu, W^*\pi = 0\}$, making NCGP[$\mathcal{R}$]($\bar{x}$) equivalent to the following problem

$$ \begin{array}{ll} \mathcal{D}[\text{cc } \mathcal{R}](\bar{x}) = \sup_{\mu, \eta, \pi} & \eta - \mu^{\top}\bar{x} \\ \text{s.t.} & \eta \le \langle d, \pi \rangle, \quad ||\mu||_* \le 1, \pi \in \mathcal{K}^*, V^*\pi = \mu, W^*\pi = 0. \end{array} $$

In this case, our framework is equivalent to a Benders Decomposition [23] that considers $\pi$ as the second stage variables. For relaxations that are not LCPs, our framework allows to generate cutting planes without needing strong duals.
## 4.2 Disjunctions

If $\mathcal{R} := \bigcup_{h \in \mathcal{H}} \mathcal{R}_h$, optimizing over $\mathcal{R}$ is separable on each $\mathcal{R}_h$. In fact, we have

$$ \kappa[\mathcal{R}](\tilde{\mu}) = \inf_{h \in \mathcal{H}} \kappa[\mathcal{R}_h](\tilde{\mu}). $$

Defining $\tilde{x}^h$ as an optimal solution of $CP[\mathcal{R}_h](\tilde{\mu})$ and $h^* \in \arg\inf_{h \in \mathcal{H}} \kappa[\mathcal{R}_h](\tilde{\mu})$, we have that $\tilde{x}^{h^*}$ is an optimal solution for $CP[\mathcal{R}](\tilde{\mu})$.

**Remark 5.** Whenever $\tilde{\eta} > \kappa[\mathcal{R}_h](\tilde{\mu})$ for some $h \in \mathcal{H}$ we can stop solving the remaining subproblems $CP[\mathcal{R}_{h'}](\tilde{\mu})$, $h' \neq h$, and directly append $\tilde{x}^h$ to $\tilde{\mathcal{R}}$.

**Cross cuts** Given a subset $\mathcal{N} \subseteq [n]$ such that $\bar{x}(\mathcal{N}) \notin \mathbb{Z}^{|\mathcal{N}|}$ and $|\mathcal{N}|$ integers $(t_j)_{j \in \mathcal{N}}$, we define a $|\mathcal{N}|$-cross as $\mathcal{T} := \bigcup_{j \in \mathcal{N}} \{x : t_j \le x_j \le t_j + 1\}$. Cross cuts are generated by taking $\mathcal{R} := \mathcal{R}^0|\mathcal{T}$ and Defining the $|\mathcal{H}| := 2^{|\mathcal{N}|}$ 2-partitions of $\mathcal{N}$ as $\{N_h^+, N_h^-\}_{h \in \mathcal{H}}$ and the following sets

$$ \mathcal{T}_j^+ := \{x : x_j \ge t_j + 1\}, \quad \mathcal{T}_j^- := \{x : x_j \le t_j\}, \quad \mathcal{R}^0 := \{x \in \mathcal{X} : l \le x \le u\}, $$

we obtain that $\mathcal{R} = \bigcup_{h \in \mathcal{H}} \mathcal{R}_h$ where:

$$ \begin{align*} \mathcal{R}_h &:= \mathcal{R}^0 \cap \bigcap_{j \in N_h^+} \mathcal{T}_j^+ \cap \bigcap_{j \in N_h^-} \mathcal{T}_j^- &&, \forall h \in \mathcal{H} \\ &:= \{x \in \mathcal{R}^0 : (x_j \ge t_j + 1, \forall j \in N_h^+) \wedge (x_j \le t_j, \forall j \in N_h^-)\} &&, \forall h \in \mathcal{H} \end{align*} $$

**Remark 6.** If we can efficiently optimize over $\mathcal{R}^0$ and $2^{|\mathcal{N}|}$ is reasonably small, calculating $\kappa[\mathcal{R}](\mu)$ reduces to solve $2^{|\mathcal{N}|}$ optimization problems over $\mathcal{R}^0$ with the additional requirement that $|\mathcal{N}|$ variables must satisfy an extra lower or upper bound. Further, the classical framework solves a CGP having a number of variables and constraints that is roughly $2^{|\mathcal{N}|}$ times that of $\mathcal{R}^0$.

## 4.3 Local and Fenchel cuts

In a MILP context - i.e. $\mathcal{X} := \{x : Ax \ge b\}$ - we can generate the Local cuts of [18] by using a relaxation $\mathcal{R}$ that is a relaxation $\{x : \tilde{A}x \ge \tilde{b}\}$ of $\mathcal{X}$ where the integrality requirements are dropped safe for a small ($|\mathcal{N}| \le 5$) subset $\mathcal{N} \subseteq \mathcal{Z}$, i.e. $\mathcal{R} := \{x : \tilde{A}x \ge \tilde{b}, x(\mathcal{N}) \in \mathbb{Z}^{|\mathcal{N}|}\}$. Using LP duality and column generation, their procedure is equivalent to ours. However, we show in the next Section that our framework extends the idea to general mixed integer optimization problems and can specialize into an implicit DW scheme that locally convexifies $\mathcal{F}$.

Local cuts are a generalization of Boyd's *Fenchel cuts* [9–12, 44] where single row relaxations of $\mathcal{X}$ are considered and either all possible integer combinations of $x(\mathcal{N})$ are enumerated or a tailored integer knapsack problem is solved via dynamic programming. In the next Section, we extend their idea to MINLCPs - i.e. when $\mathcal{X} := \{x : -f(x) \in \mathcal{C}\}$. We now show that local cuts hold several advantages against cross cuts.
**Proposition 6.** Consider $\mathcal{N} \subseteq \mathcal{Z}$, some tractable relaxation $\mathcal{R}^0$ of $\mathcal{F}$, an $|\mathcal{N}|$-cross $\mathcal{T}$ and the following relaxations of $\mathcal{F}$

$$ \mathcal{R}^1 = \mathcal{R}^0|\text{int } \mathcal{T} \quad \text{and} \quad \mathcal{R}^2 := \mathcal{R}^0 \cap \{x : x(\mathcal{N}) \in \mathbb{Z}^{|\mathcal{N}|}\}. $$

Then $cc \mathcal{R}^2$ is a relaxation of $\mathcal{F}$ that is no weaker than $cc \mathcal{R}^1$.

*Proof.* It is enough to show that $\mathcal{R}^2 \subseteq \mathcal{R}^1$, i.e. that any $x^2 \in \mathcal{R}^2$ satisfies $x^2 \in \mathcal{R}^0$ - which is immediate - and $x^2 \notin \text{int } \mathcal{T}$. The second point is also straightforward as by construction $\text{int } \mathcal{T} \cap \{x : x(\mathcal{N}) \in \mathbb{Z}^{|\mathcal{N}|}\} = \emptyset$.

*Remark 7.* Notice that

1. $CP[\mathcal{R}^2](\mu)$ is an optimization problem with $|\mathcal{N}|$ integer variables

2. $CP[\mathcal{R}^1](\mu)$ requires solving $2^{|\mathcal{N}|}$ continuous optimization problems.

3. Separating for $\mathcal{R}^1$ with the classical method requires solving a problem that is roughly $2^{|\mathcal{N}|}$ larger than $\mathcal{R}^0$.

4. $cc \mathcal{R}^2$ is often strictly stronger than $cc \mathcal{R}^1$.

# 5 Block-separable structures and Column Generation

Suppose that some block-separable structure is present in $P$, i.e. we have $\mathcal{F} := \{x \in \mathcal{F}^0 : x(\mathcal{N}_h) \in \mathcal{F}_h, \forall h \in \mathcal{H}\}$, where the $\mathcal{N}_h \subseteq [n]$ are pairwise disjoint and each $\mathcal{F}_h$ is a general set. Notice that without $x \in \mathcal{F}^0$, $P$ is separable in $|\mathcal{H}|$ independent problems in $x(\mathcal{N}_h)$ only. $\mathcal{R} := \bigcap_{h \in \mathcal{H}} \mathcal{R}_h$ is a block-separable relaxation of $\mathcal{F}$, where for each $h \in \mathcal{H}$, $\mathcal{R}_h := \{x : x(\mathcal{N}_h) \in \mathcal{F}_h\}$. In DW, one successively constructs $cc \mathcal{R}$ via inner approximations of $cc \mathcal{R}$; We now show that we can build $cc \mathcal{R}$ via outer approximations.

## 5.1 Column generation via cutting planes

Similar to the *pricing problem* in DW, solving the core problem reduces to optimize on each $\mathcal{R}_h$ i.e. solve $|\mathcal{H}|$ optimization problems with $|\mathcal{N}_h|$ variables each:

$$ \kappa[\mathcal{R}](\mu) = \sum_{h \in \mathcal{H}} \kappa[\mathcal{R}_h](\mu). $$

Equally importantly, the cuts generated separate $\bar{x}$ from $cc \mathcal{R} = \bigcap_{h \in \mathcal{H}} cc \mathcal{R}_h = \{x : x(\mathcal{N}_h) \in cc \mathcal{F}_h, \forall h \in \mathcal{H}\}$. We can also separate each $\bar{x}(\mathcal{N}_h)$ from $cc \mathcal{F}_h$ - which yields the same hull - but generates the following disaggregated cuts:

$$ \tilde{\eta}_h \le x(\mathcal{N}_h)^{\top} \tilde{\mu}^h, \text{ where } (\tilde{\mu}^h, \tilde{\eta}_h) \text{ is optimal for NCGP}[\mathcal{R}_h](\bar{x}(\mathcal{N}_h)). $$

In fact, similar to DW with a separable structure, one can choose to consider the “easy” subproblem either as a single block or a family of $|\mathcal{H}|$.

For such an approach to work, a block separable sub-structure is needed. When such a sub-structure does not appear naturally, it is sometimes possible
to extract one: In Boyd's work for MILPs, they first define a single row relaxation {$x: \tilde{a}^\top x \le \tilde{b}$} of $\mathcal{X}$. For some bounds $l \le x \le u$ and noticing that for each $j \in [n]$

$$l_j[\tilde{a}_j]_+ - u_j[\tilde{a}_j]_- \le x_j \tilde{a}_j, \qquad (6)$$

they work on the following relaxation of $\mathcal{F}$ that depends on $x(\mathcal{N})$ only: $\mathcal{R} := \{x: x(\mathcal{N} \cap \mathcal{Z}) \in \mathbb{Z}^{|\mathcal{N} \cap \mathcal{Z}|}: \tilde{a}(\mathcal{N})^\top x(\mathcal{N}) + \sum_{j \notin \mathcal{N}} (l_j[\tilde{a}_j]_+ - u_j[\tilde{a}_j]_-) \le \tilde{b}\}$. We now extend this idea to construct separable relaxations for MINLCPs.

## 5.2 Projection and conic dominance

We begin with an adaptation of a theorem from Moreau [33] that allows to decompose a point in terms of its projections onto the cones $\mathcal{K}$ and $-\mathcal{K}^*$:

**Proposition 7.** Consider a closed convex cone $\mathcal{K}$. For any $v$, 1) there exists a decomposition $v = \hat{v} + v^*$ such that $\hat{v} \in \mathcal{K}$ and $v^* \in -\mathcal{K}^*$ and 2) the only decomposition satisfying $\langle \hat{v}, v^* \rangle = 0$ is $v = \Pi[\mathcal{K}](v) + \Pi[-\mathcal{K}^*](v)$.

We now use the last result to derive the following (conic) bound:

**Proposition 8.** Consider a closed convex cone $\mathcal{K}$ such that $\mathcal{K}^* \subseteq \mathcal{K}$. For any $v$ and some real number $t \in [l, u]$, we have

$$l \cdot \Pi[\mathcal{K}](v) + u \cdot (v - \Pi[\mathcal{K}](v)) \preceq_{\mathcal{K}} t \cdot v$$

*Proof.* From Proposition 7, for any $\pi \in \mathcal{K}^*$, we have: $\langle \pi, t \cdot v \rangle = t\langle \pi, \Pi[\mathcal{K}](v) \rangle + t\langle \pi, \Pi[-\mathcal{K}^*](v) \rangle$. Given that $\Pi[\mathcal{K}](v) \in \mathcal{K}$ and $-\Pi[-\mathcal{K}^*](v) \in \mathcal{K}^* \subseteq \mathcal{K}$, we have $\langle \pi, \Pi[\mathcal{K}](v) \rangle \ge 0$ and $\langle \pi, \Pi[-\mathcal{K}^*](v) \rangle \le 0$. Because $t \in [l, u]$, this implies that for any $\pi \in \mathcal{K}^*$: $\langle \pi, t \cdot v \rangle \ge l\langle \pi, \Pi[\mathcal{K}](v) \rangle + u\langle \pi, \Pi[-\mathcal{K}^*](v) \rangle$. Because $v = \Pi[\mathcal{K}](v) + \Pi[-\mathcal{K}^*](v)$, we obtain the result.

If $\mathcal{K} = \mathbb{R}_+$, we retrieve Boyd's basic ingredient (6) to his single row relaxation. Going beyond single-row relaxations, we now provide block-separable relaxations for convex MINLCPs.

*Remark 8.* Many of the usual cones are self dual - i.e. $\mathcal{K}^* = \mathcal{K}$ - and proving membership or projecting on $\mathcal{K}$ is not necessarily a hard task:

1. Nonnegative orthant $\mathbb{R}_+^m$. For $v \in \mathbb{R}^m$: $\Pi[\mathcal{K}](v) = ([v_i]_+)^{i \in [m]}$.

2. SOC $\mathcal{L}_2^{m+1} := \{(v, v_0) : ||v||_2 \le v_0\}$. For any nonzero $(v, v_0) \notin \mathcal{L}_2^{m+1}$ [21]: $\Pi[\mathcal{K}](v, v_0) = (v_0 + ||v||_2)(2||v||_2)^{-1} \cdot (v, ||v||_2)$.

3. Symmetric SDP matrices $\mathbb{S}_+^m$. Any matrix $V \in \mathbb{S}^m$ with eigenvalues $(\lambda_i)_{i \in [m]}$ is diagonalizable in an orthonormal basis $L: \Pi[\mathcal{K}](V) = L\mathrm{diag}([\lambda_i]_+)^{i \in [m]} L$.

## 5.3 Generic separable relaxation

Consider that we have $\mathcal{X} := \{x: l \le x \le u, -f(x) \in \mathcal{C}\}$, where $\mathcal{C}$ is a convex proper cone such that $\mathcal{C}^* \subseteq \mathcal{C}$ and $f$ is $\mathcal{C}$-convex.
**Proposition 9.** Given $\mathcal{N} \subseteq [n]$, $\mathcal{R} := \{x : x(\mathcal{N} \cap \mathcal{Z}) \in \mathbb{Z}^{|\mathcal{N} \cap \mathcal{Z}|} : \bar{A}x(\mathcal{N}) \preceq_c \bar{b}\}$, is a relaxation of $\mathcal{F}$, where

$$ \bar{Ax}(\mathcal{N}) := \sum_{j \in \mathcal{N}} D^j f(\bar{x}) x_j, \\ \bar{b} := Df(\bar{x}) \bar{x} - f(\bar{x}) + \sum_{j \notin \mathcal{N}} ((u_j - l_j) \Pi[\mathcal{C}] (D^j f(\bar{x})) - u_j D^j f(\bar{x})). $$

*Proof.* Because $f$ is $\mathcal{C}$-convex, for every $x \in \text{dom}(f)$ we have

$$ \begin{aligned} f(x) \succeq_c f(\bar{x}) + Df(\bar{x})(x - \bar{x}) &= f(\bar{x}) - Df(\bar{x})\bar{x} + \sum_{j \in [n]} D^j f(\bar{x}) x_j \\ &= f(\bar{x}) - Df(\bar{x})\bar{x} + \sum_{j \in \mathcal{N}} D^j f(\bar{x}) x_j + \sum_{j \notin \mathcal{N}} D^j f(\bar{x}) x_j. \end{aligned} $$

Applying Proposition 8 to each $D^j f(\bar{x}) x_j$, $j \notin \mathcal{N}$ we obtain:

$$ \begin{aligned} f(x) \succeq_c f(\bar{x}) - Df(\bar{x})\bar{x} + \sum_{j \in \mathcal{N}} D^j f(\bar{x}) x_j &+ \sum_{j \notin \mathcal{N}} (l_j \Pi[\mathcal{C}] (D^j f(\bar{x}) x_j) + u_j (D^j f(\bar{x}) x_j - l_j \Pi[\mathcal{C}] (D^j f(\bar{x}) x_j))). \end{aligned} $$

Replacing into $-f(x) \in \mathcal{C}$ we obtain the result.

Given disjoint sets $\mathcal{N}_h \subseteq [n]$, consider $\mathcal{R} := \bigcap_{h \in \mathcal{H}} \mathcal{R}_h$ where for each $h \in \mathcal{H}$

$$ \mathcal{R}_h := \{ x : x(\mathcal{Z}) \in \mathbb{Z}^{|\mathcal{Z}|} : l \le x \le u, \bar{A}^h x(\mathcal{N}_h) - \bar{b}^h \in \mathcal{C} \}. $$

From Proposition 9, $\mathcal{R}$ is a relaxation of $\mathcal{F}$ that is separable in each cluster $\mathcal{N}_h$.

**Remark 9.** The relaxation obtained after linearizing $f$ and fixing some variables to their bounds is weaker than the continuous relaxation of $P$; However, keeping the integrality as a hard constraint can compensate that weakness.

**Remark 10.** If the sets $\mathcal{N}_h$ are not pairwise disjoint, we cannot split the core problem. However, we can still separate in parallel each $\bar{x}(\mathcal{N}_h)$ from $\mathcal{C} \in \mathcal{R}_h$.

# 6 Conclusions and future directions

We present a framework to separate from convex hulls of general relaxations $\mathcal{R}$. We allow the use of existing classes of cuts for more general problems and compare our method with the classical methodologies. We show how to generate partial convex hulls just as DW and in the MINLCP case, we give guidelines to construct separable relaxations making our framework decomposable. In a current work, we study 1) a modified algorithm that solves the NCGP and the core problems only approximately and 2) the generation of facet-defining cuts with different normalizations, including the stand-alones used in [14, 19]. Extensive computational experiments on benchmark instances are required in order to assess the quality of the methodology - in terms of both cut strength and computational efficacy.
References

1. Atamtürk, A., Narayanan, V.: Conic mixed-integer rounding cuts. Mathematical programming **122**(1), 1–20 (2010)

2. Atamtürk, A., Nemhauser, G.L., Savelsbergh, M.W.: Conflict graphs in solving integer programming problems. European Journal of Operational Research **121**(1), 40–55 (2000)

3. Balas, E.: Facets of the knapsack polytope. Mathematical programming **8**(1), 146–164 (1975)

4. Balas, E.: Disjunctive programming. In: Annals of discrete mathematics, vol. 5, pp. 3–51. Elsevier (1979)

5. Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical programming **58**(1-3), 295–324 (1993)

6. Balas, E., Perregaard, M.: A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming. Mathematical Programming **94**(2-3), 221–245 (2003)

7. Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM (2001)

8. Bonami, P.: On optimizing over lift-and-project closures. Mathematical Programming Computation **4**(2), 151–179 (2012)

9. Boyd, E.A.: Generating fenchel cutting planes for knapsack polyhedra. SIAM Journal on Optimization **3**(4), 734–750 (1993)

10. Boyd, E.A.: Fenchel cutting planes for integer programs. Operations Research **42**(1), 53–64 (1994)

11. Boyd, E.A.: Solving 0/1 integer programs with enumeration cutting planes. Annals of Operations Research **50**(1), 61–72 (1994)

12. Boyd, E.A.: On the convergence of fenchel cutting planes in mixed-integer programming. SIAM Journal on Optimization **5**(2), 421–435 (1995)

13. Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge university press (2004)

14. Buchheim, C., Liers, F., Oswald, M.: Local cuts revisited. Operations Research Letters **36**(4), 430–433 (2008)

15. Cadoux, F., Lemaréchal, C.: Reflections on generating (disjunctive) cuts. EURO Journal on Computational Optimization **1**(1-2), 51–69 (2013)

16. Caprara, A., Fischetti, M.: {0, 1/2}-chvátal-gomory cuts. Mathematical Programming **74**(3), 221–235 (1996)

17. Çezik, M.T., Iyengar, G.: Cuts for mixed 0-1 conic programming. Mathematical Programming **104**(1), 179–202 (2005)

18. Chvátal, V., Cook, W., Espinoza, D.: Local cuts for mixed-integer programming. Mathematical Programming Computation **5**(2), 171–200 (2013)

19. Conforti, M., Wolsey, L.A.: Facet separation with one linear program. Mathematical Programming **178**(1-2), 361–380 (2019)

20. Espinoza, D.G.: Computing with multi-row gomory cuts. Operations Research Letters **38**(2), 115–120 (2010)

21. Ferreira, O.P., Németh, S.Z.: How to project onto extended second order cones. Journal of Global Optimization **70**(4), 707–718 (2018)

22. Fischetti, M., Lodi, A., Tramontani, A.: On the separation of disjunctive cuts. Mathematical Programming **128**(1-2), 205–230 (2011)

23. Geoffrion, A.: Generalized benders decomposition. Journal of optimization theory and applications **10**(4), 237–260 (1972)
24. Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM) 42(6), 1115–1145 (1995)

25. Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs and an algorithm for the mixed integer problem. In: 50 Years of Integer Programming 1958-2008, pp. 77–103. Springer (2010)

26. Kılınç, M.R., Linderoth, J., Luedtke, J.: Lift-and-project cuts for convex mixed integer nonlinear programs. Mathematical Programming Computation 9(4), 499–526 (2017)

27. Komiya, H.: Elementary proof for sion's minimax theorem. Kodai mathematical journal 11(1), 5–7 (1988)

28. Lasserre, J.B.: An explicit exact sdp relaxation for nonlinear 0-1 programs. In: International Conference on Integer Programming and Combinatorial Optimization. pp. 293–303. Springer (2001)

29. Lodi, A., Tanneau, M., Vielma, J.P.: Disjunctive cuts for mixed-integer conic optimization. arXiv preprint arXiv:1912.03166 (2019)

30. Lovász, L.: On the Shannon capacity of a graph. IEEE Transactions on Information theory 25(1), 1–7 (1979)

31. Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0–1 optimization. SIAM journal on optimization 1(2), 166–190 (1991)

32. Lübbecke, M.E., Desrosiers, J.: Selected topics in column generation. Operations research 53(6), 1007–1023 (2005)

33. Moreau, J.J.: Décomposition orthogonale d'un espace hilbertien selon deux cônes mutuellement polaires (1962)

34. Nemhauser, G.L., Wolsey, L.A.: A recursive procedure to generate all cuts for 0–1 mixed integer programs. Mathematical Programming 46(1-3), 379–390 (1990)

35. Padberg, M.W., Van Roy, T.J., Wolsey, L.A.: Valid linear inequalities for fixed charge problems. Operations Research 33(4), 842–861 (1985)

36. Perregaard, M., Balas, E.: Generating cuts from multiple-term disjunctions. In: International Conference on Integer Programming and Combinatorial Optimization. pp. 348–360. Springer (2001)

37. Rockafellar, R.T.: Convex analysis. No. 28, Princeton university press (1970)

38. Serra, T.: Reformulating the disjunctive cut generating linear program. Annals of Operations Research pp. 1–22 (2020)

39. Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3(3), 411–430 (1990)

40. Sherali, H.D., Adams, W.P.: A reformulation-linearization technique for solving discrete and continuous nonconvex problems, vol. 31. Springer Science & Business Media (2013)

41. Sherali, H.D., Tuncbilek, C.H.: A reformulation-convexification approach for solving nonconvex quadratic programming problems. Journal of Global Optimization 7(1), 1–31 (1995)

42. Stubbs, R.A., Mehrotra, S.: A branch-and-cut method for 0-1 mixed convex programming. Mathematical programming 86(3), 515–532 (1999)

43. Wolsey, L.A., Nemhauser, G.L.: Integer and combinatorial optimization, vol. 55. John Wiley & Sons (1999)

44. Yan, X.Q., Boyd, E.A.: Cutting planes for mixed-integer knapsack polyhedra. Mathematical programming 81(2), 257–262 (1998)