1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

$$ 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.

$\endgroup$
  • $\begingroup$ @Kuifke What happens if condition does not hold is also important to me. $\endgroup$ – 1.. Apr 6 '19 at 11:53
  • $\begingroup$ If the condition does not hold, then $\delta = 0$, and the first equation becomes $Ay \le b+M$ which always holds. $\endgroup$ – Kuifje Apr 6 '19 at 11:54
  • $\begingroup$ Then $y$ may not satisfy the condition. $\endgroup$ – 1.. Apr 6 '19 at 11:55
  • $\begingroup$ But you wrote that "if the condition does not hold I should not care." $\endgroup$ – Kuifje Apr 6 '19 at 11:56
  • $\begingroup$ That means such a $y$ should be definable in the program. $\endgroup$ – 1.. Apr 6 '19 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.