If then convex condition in mixed integer linear programming with binary variables

Question

I have a convex polynomial $f(x_1,\dots,x_t)$ where $x_1,\dots,x_t\in\mathbb R$ and constant $a$.

If condition $$f(x_1,\dots,x_t)\leq a$$ holds I have to make variables $y_1,\dots,y_n\in\mathbb R$ ($n\geq t$ and some of $y_i$s are same as $x_i$s) satisfy some linear condition $Ay\leq b$ where $A\in\mathbb R^{m\times n}$ and $b\in\mathbb R^{m}$ are fixed and known where $y^T=(y_1,\dots,y_n)$ is variable vector.

If condition $$f(x_1,\dots,x_t)> a$$ holds I just have to make variables $y_1,\dots,y_n\in\mathbb R$ to satisfy nothing however it should be defined.

Is this possible to this with feasibility Mixed integer programming with no objective function possibly by introducing integer variables and only additional linear conditions?

Answer 1

$$ Ay \le b + M(1-\delta) \\ f(x_1,...,x_n) \le a + M(1-\delta) \\ \delta \in \{0,1\} $$ And penalize the $\delta$ variable in your cost function so that it is set to $0$ only if there is no other option.

Answer 2

I can think of two alternatives, neither of which is perfect. Both involve a binary variable $\delta$, a large scalar $M$ and a vector of large scalars $\vec{M}$. Both use the inequality $Ay\le b + \vec{M}(1-\delta)$.

The first approach adds the inequality $f(x)\ge a - M\delta$. The weakness of this version is that if $f(x)=a$, $\delta$ can be either 1 (logically correct) or 0. So the if-then requirement fails to be enforced if $f(x)=a$.

The second approach instead uses $f(x)\ge a + \epsilon - M\delta$ for some small $\epsilon > 0$. The good news is that $f(x)=a$ will result in $Ay\le b$. The bad news is that $f(x)\in (a, a+\epsilon)$ enforces $Ay\le b$, which was not wanted.

Note that @Kuifje's approach, penalizing $\delta$, can achieve exactly what was asked for, provided that a penalty coefficient can be found that is large enough to enforce the requirement (which is testable: see if the final solution violates it) but not large enough to produce a suboptimal solution (harder to test).