Suggestion : Handle unbounded high-point relaxation

[hlefebvr]

Hello,

I am suggesting an enhancement to MibS and will try to motivate this with an example.

Enhancement Handle MILP-MILP Bilevel problems with unbounded high-point relaxation.

Motivation The main motivation comes from the two-stage robust optimization literature and, in particular, the adversarial problem therein, which is a bilevel problem.

Two-stage robust optimization is concerned with general problems of the form

$$ \begin{align} \min_x \ & c^\top x \\ \text{s.t.} \ & x\in X, \\ & \forall \xi\in\Xi, \exists y\in Y(x,\xi). \end{align} $$

Here, $X$ is called the first-stage feasible space, $\Xi$ is the uncertainty set and $Y(x,\xi)$ is the second-stage feasible space.

One traditional method to solve such problems is through column-and-constraint generation. This method considers a finite subset $\lbrace \xi^1, \dotsc, \xi^K \rbrace \subset \Xi$ and solves the relaxation

$$ \begin{align} \min_x \ & c^\top x \\ \text{s.t.} \ & x\in X, \\ & y^k\in Y(x,\xi^k) \qquad k=1,\dotsc,K. \end{align} $$

Then, one needs to check if a (projected) solution to this relaxation, say $\hat x$, is feasible for the original problem. Hence, one needs to search for a $\xi\in \Xi$ such that $Y(x,\xi) = \emptyset$. This can be done by solving a bilevel problem which maximizes newly introduced "artificial" variables in the second stage, i.e., one solves

$$ \begin{align} \max_{\xi\in\Xi} \ & s \\ \text{s.t.} \ & \xi\in\Xi, \\ & y\in\text{arg min}_y { s : y\in Y(x,\xi) + s }. \end{align} $$

Unfortunately, this problem has an unbounded high-point relaxation which makes it unsolvable by MibS.

Hence, in order to be able to use MibS in, e.g., column-and-constraint algorithms as a sub-routine for two-stage robust problem, it would be very nice if MibS could solve such problems.

I am open to discussion on how this can be achieved (included, if needed, contribution to the MibS code).

Thank you,

Henri.

[tkralphs]

Hey @hlefebvr sorry for not keeping as close an eye on these issues as I ideally should. I just saw this one and it's something that I would be very willing to talk about, though probably wouldn't have much bandwidth to implement myself. If you're still interested, then perhaps we could discuss how this might be done.