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$

2 Answers 2

Reset to default
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$
17
  • $\begingroup$ @Kuifke What happens if condition does not hold is also important to me. $\endgroup$ Commented Apr 6, 2019 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$ Commented Apr 6, 2019 at 11:54
  • $\begingroup$ Then $y$ may not satisfy the condition. $\endgroup$ Commented Apr 6, 2019 at 11:55
  • $\begingroup$ But you wrote that "if the condition does not hold I should not care." $\endgroup$ Commented Apr 6, 2019 at 11:56
  • $\begingroup$ That means such a $y$ should be definable in the program. $\endgroup$ Commented Apr 6, 2019 at 11:57

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.