Introduction

The Column-and-Constraint Generation (CCG) algorithm is a classical method for solving two-stage robust optimization problems. It was originally introduced by [14].

In idol, the implementation of CCG alows to solve a class of problems which is slightly more general than classical two-stage robust optimization problems. This class of problems is defined in the following section.

Problem Definition and Notation

The CCG algorithm can solve optimization problems of the form

(1)\[\begin{split}\begin{align} \min_x \quad & f(x) \\ \text{s.t.} \quad & x\in X, \\ & \forall \xi\in\Xi, \ \exists y\in Y(x,\xi), \ G(x,y,\xi) \le 0. \end{align}\end{split}\]

in which \(f:\mathbb R^{n_x}\rightarrow\mathbb R\) is a given function, \(X\subseteq\mathbb R^{n_x}\) is a given set, called the first-stage feasible set, \(\Xi\subseteq\mathbb R^{n_\xi}\) is a given set, called the uncertainty set, typically compact, \(Y(x,\xi) \subseteq \mathbb R^{n_y}\) is a set, defined for all \(x\in X\) and \(\xi\in\Xi\), called the second-stage feasible set, and \(G:\mathbb R^{n_x+n_y+n_\xi}\rightarrow\mathbb R^\ell\) is a given vector of functions, defining the so-called coupling constraints between the uncertainty, the first- and the second-stage decisions.

Regarding Coupling Constraints

It is clear that coupling constraints are redundant since they can be incorporated into the definition of the second-stage feasible set. However, we will see that explicitly defining coupling constraints may lead to different implementations of the CCG algorithm. We will dive into this aspect after introducing the concept of separators.

Hint

Consider the Min-Max-Min problem

\[\min_{x\in X} \ \max_{\xi\in\Xi} \ \min_{y\in Y(x,\xi)} \ \psi(x,y,\xi).\]

Clearly, this is a special case of (1) since it can be written as

\[\begin{split}\begin{align} \min_{x_0,x} \quad & x_0 \\ \text{s.t.} \quad & (x_0,x) \in\mathbb R\times X, \\ & \forall \xi\in\Xi, \ \exists y\in Y(x,\xi), \ \psi(x,y,\xi) \le x_0. \end{align}\end{split}\]

Here, there is only one coupling constraint, which is \(\psi(x,y,\xi) \le x_0\).

The Algorithm

Basic Idea

The idea of the CCG algorithm is to consider a finite subset of points in \(\Xi\), say \(\{ \xi^1, \dotsc, \xi^k \}\), and to solve the following problem instead of (1):

(2)\[\begin{split}\begin{align} \min_{x_0,x,y^1,\dotsc,y^K} \quad & f(x) \\ \text{s.t.} \quad & x\in X, \\ & G(x,y^t,\xi^t) \le 0 \qquad k=1,\dotsc,K, \\ & y^t\in Y(x,\xi^t) \qquad k=1,\dotsc,K. \end{align}\end{split}\]

Here, a new variable \(y^t\) has been introduced for each \(t=1,...,k\), enforcing that, indeed, there exists \(y^t\in Y(x,\xi^t)\) such that \(G(x,y^t,\xi^t) \le 0\).

Note that Problem (2) is a relaxation of Problem (1) since any feasible point of (1) is also feasible for (2) (for some \(y^1,\dotsc,y^K\)).

Now, given a solution \(\hat x\in X\) to the relaxed problem (2), one needs to check whether \(\hat x\) is feasible for Problem (1). Thus, one seeks a scenario \(\xi^*\in\Xi\) such that, either \(Y(\hat x, \xi^*)\) is empty, or \(G(\hat x,y,\xi^*) > 0\) for all \(y\in Y(\hat x, \xi^*)\). If no such scenario exists, then \(\hat x\) is feasible for (1). Otherwise, the new scenario \(\xi^*\) is added to the set of considered scenarios and the process is repeated.

Identifying a missing scenario is called separation, and can be done by solving the following problem:

(3)\[ \max_{\xi\in \Xi} \ \max_{\ell=1,...,L} \left\{ \ \min_{ y\in Y(\hat x,\xi) } \ G_\ell(\hat x,y,\xi) \right\}.\]

If the optimal value of the separation problem is non-positive, then \(\hat x\) is feasible for (1). Otherwise, the solution to the separation problem gives a new scenario \(\xi^*\) to be added to the set of scenarios.

Note that we use the convention \(\max \emptyset = -\infty\) and \(\min \emptyset = +\infty\).

Separators

Clearly, the separation problem (3) can be solved in many different ways. In idol, it is therefore possible to give a user-defined functor, called a separator, which solves the separation problem. Note that the most common ways to solve the separation problem are already implemented in idol. Yet, if you wish to implement your own separator, you should refer to this tutorial.

Shortly put, the separator solves problems of the form

(4)\[ \max_{\xi\in \Xi} \ \min_{ y\in Y(\hat x,\xi) } \ G_\ell(\hat x,y,\xi),\]

for a given \(G_\ell\) (\(\ell\in\{1,...,L\}\)).

Note that it is ensured that the separator always solves a problem which is feasible. Indeed, in case Problem (3) is not known to satisfy the complete recourse assumption (i.e., it is not known whether \(\forall x\in X, \forall\xi\in\Xi, \exists y\in Y(x,\xi)\) holds), the CCG algorithm will first solve a feasibility version of the separation problem to check whether \(\hat x\) is such that for all \(\xi\in\Xi\) there exists \(y\in Y(\hat x,\xi)\). Fortunately, it is also possible to specify that the complete recourse assumption holds, in which case the feasibility version of the separation problem is not solved.

Let \(\xi^{\ell}\) denote the solution to the separation problem (4) for a given \(\ell\in\{1,...,L\}\). Then, a scenario \(\xi^{\ell^*}\) is added to Problem (2) if and only if

\[\ell^* \in \underset{\ell=1,...,L}{\text{argmax}} \ \min_{ y\in Y(\hat x,\xi^\ell) } \ G_\ell(\hat x,y,\xi^\ell) > \varepsilon_\text{feas}.\]

See the dedicated page for more details.

On the Impact of Coupling Constraints

We now discuss the impact of the definition of the coupling constraints \(G\) on the implementation of the CCG algorithm. Clearly, one obtains an equivalent problem to (1) by defining the second-stage feasible set as

\[\tilde Y(x,\xi) = \{ y\in Y(x,\xi) \ | \ G(x,y,\xi) \le 0 \},\]

and by considering the problem

\[\begin{split}\begin{align} \min_x \quad & f(x) \\ \text{s.t.} \quad & x\in X, \\ & \forall \xi\in\Xi, \ \exists y\in \tilde Y(\hat x,\xi). \end{align}\end{split}\]

In this case, the separation problem becomes

\[\max_{\xi\in\Xi} \ \min_{ y\in \tilde Y(\hat x,\xi) } \ 0,\]

which is a feasibility problem.

Though the two approaches are equivalent, in the sense that they will both lead to a solution to (1), they may lead to different computational performances. An interested reader may refer to, e.g., [2] for more details.