1
$\begingroup$

In a linear program need to constrain the percent change between two decision variables, $a,b$ where the percent change formula, relative to $b$ is $\frac{a-b}{b}$.

I'm not sure that any arbitrary value will be feasible given other constraints, which are omitted for brevity. So my intention is to solve sequentially. In the first model, I will find the minimum percent change possible, and in a second model, I will constrain to achieve this minimum percent change. Assume that all omitted constraints in the first model will also be applied in the second model.

Let's start with some arbitrarily small percent change, for example $0.001$.

thus my naive constraint is $\frac{a-b}{b} \le 0.001$. This isn't linear, which is problematic but we can linearize it as $a-b \le 0.001b$.

Now, I don't know that $0.001$ is achievable, so let's add in some surplus variables and rerun this logic:

  1. $\frac{a-b}{b} \le 0.001$
  2. $\frac{a-b}{b} = 0.001 + u -l $
  3. $a-b = b(0.001 +u -l)$
  4. $a-b = 0.001b + bu - bl$
  5. $a-b - 0.001b = bu -bl$
  6. $a - 1.001b = bu - bl$

Now from this form I can modify solve this model whether or not $a>b$

$min(u+l)$

$u, l \ge 0$

$a-1.001b = bu - bl$

$1.001b-a = bu - bl$

And finally, the minimum achievable percent change achievable is as follows

  • If $a>b$ then best percent change is $0.001 + u$
  • Elif $a<b$ then best percent change is $0.001 - l$
  • Elif $a=b$, then best percent change is $0.001$.

In the edge case that $l=0.001$ then best percent change is $0.0$.

Now in my second model, I can use the derived best percent changes. Suppose that $u=0.002$, the best achievable is $0.003$. We can now constrain $a-b = 0.003b$

Am I thinking about this correctly?

Edit: I just realized that $bu, bl$ are nonlinear terms, so my linearization strategy is not effective. What alternatives are available?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Your $u$ and $l$ variables are essentially relative tolerances. If you can tolerate absolute tolerances, you can use linear constraints (e.g., $a-b \le 0.001 b + u$).

Another possibility is to use binary variables (escalating your LP to a MILP) and do a piecewise linear tolerance. Choose $K$ possible values $0 = \alpha_1 < \dots < \alpha_K$ for your relative tolerance $u$ and write $$u=\sum_{k=1}^K \alpha_k x_k$$ where $x_1,\dots,x_K\in \lbrace 0,1 \rbrace.$ Add the constraint $$\sum_{k=1}^K x_k = 1.$$ Your constraint, after multiplying both sides by $b,$ becomes $$a-b \le 0.001 b + \alpha_1 x_1 b + \dots + \alpha_K x_K b.$$ The products $x_k b$ can be linearized (it's a FAQ on this site) assuming that you can provide a priori bounds for $b.$

Improve this answer
$\endgroup$
3
  • $\begingroup$ Absolute tolerances are appropriate for my use and I also would to prefer to use pure LP because the scale of my problem will have thousands of decision variables. I'm sure there are IP tricks to wrangle such problems (eg column generation) but that's a bit beyond me - at least for the moment. $\endgroup$ Commented Oct 21 at 21:10
  • $\begingroup$ But @prubin can you tell me a bit more about the $a-b \le 0.001b +u$ approach? $\endgroup$ Commented Oct 21 at 21:13
  • $\begingroup$ What is it you want to know? You have already observed how to linearize the original constraint. The nonnegative variable $u$ captures the violation of that constraint. You can penalize it in the objective function, and you can also slap an upper bound on it (to prevent an intolerably large violation). $\endgroup$ Commented Oct 22 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.