Linear Programming: Minimize deviation and evenly maximize decisive variable

Question

I came across linear programming while trying to find a solution to a problem. I didn't use LP before so pardon if it is naive question. I hope this forum can help.

There are n tasks (x1, x2 .., xn) with current assigned values (r1, r2 .. rn) and new target values (t1, t2 ... tn). Each of the tasks has certain known constraint on upper and lower bound values (lbi <= xi <= ubi). There are also constraint across the task values. (See example for more details)

Objective is to minimize individual task deviation.

I tried with minimizing sum of absolute value deviation ($min \sum_i \left|x_i - t_i\right|$) but with that some tasks are more close to target value than others.

---

Edit1: Here is a simple example.

This is the input:

task	current (r)	target (t)	LB (lb)	UB (ub)
X1	500	1500	500	1500
X2	500	1500	500	1500
X3	5000	4000	4000	8000
X4	5000	4000	4000	8000

Update Eg constraint across task total values: $x_1 + x_2 \le 2000$

My initial approach: Here is the primary objective I initially created:

\begin{align} min \sum_i \left|x_i - t_i\right| \end{align}

Subject to: \begin{align} \text{lb}_i \le x_i \le \text{ub}_i \\ \sum_i x_i - \sum_i t_i = 0 \\ \ x_1 + x_2 \le 2000 \end{align}

This gave me results:

task	current (r)	target (t)	LB (lb)	UB (ub)	result (x)
X1	500	1500	500	1500	1500
X2	500	1500	500	1500	500
X3	5000	4000	4000	8000	4000
X4	5000	4000	4000	8000	5000

I would want to optimize so that X1, X2, X3, X4 increase/decrease evenly close to the target. Result for X1, X2 should be 1000 and X3, X4 should be 4500 respectively.

Hope it helps.

Edit2: Model file for glpsol for above problem and the solution:

Note that Z is (same as what @RobPratt suggested): \begin{align} z_i + x_i &\ge t_i \\ z_i - x_i &\ge -t_i \end{align}

Minimize
 obj: TaskZ1 + TaskZ2 + TaskZ3 + TaskZ4
Subject to
 c0: TaskX1 + TaskX2 <= 2000
 c1: TaskZ1 + TaskX1 >= 1500
 c2: TaskZ1 - TaskX1 >= -1500
 c3: TaskZ2 + TaskX2 >= 1500
 c4: TaskZ2 - TaskX2 >= -1500
 c5: TaskZ3 + TaskX3 >= 4000
 c6: TaskZ3 - TaskX3 >= -4000
 c7: TaskZ4 + TaskX4 >= 4000
 c8: TaskZ4 - TaskX4 >= -4000
 c9: TaskX1 + TaskX2 + TaskX3 + TaskX4 >= 11000
Bounds
 0 <= TaskZ1 <= 1000
 0 <= TaskZ2 <= 1000
 0 <= TaskZ3 <= 1000
 0 <= TaskZ4 <= 1000
 500 <= TaskX1 <= 1500
 500 <= TaskX2 <= 1500
 4000 <= TaskX3 <= 8000
 4000 <= TaskX4 <= 8000
General
 TaskZ1 TaskZ2 TaskZ3 TaskZ4 TaskX1 TaskX2 TaskX3 TaskX4
End

Solution:

 Objective: 2000.0
TaskZ1 = 0.0
TaskZ2 = 1000.0
TaskZ3 = 1000.0
TaskZ4 = 0.0
TaskX1 = 1500.0
TaskX2 = 500.0
TaskX3 = 5000.0
TaskX4 = 4000.0

There are many solution to the above problem.

But the desired outcome: Get task value to evenly change to reduce variability: (objective still 2000)

TaskX1 = 1000.0
TaskX2 = 1000.0
TaskX3 = 4500.0
TaskX4 = 4500.0

How to achieve this?

Edit3: This question was marked closed due to initial limited info. I have been updating the question with more concrete examples and findings (thanks to @RobPratt). I have updated the description again to make it more valuable for folks that might be in similar situation.

Bdw, @RobPratt's last update to his response did the trick! There is subtle difference between $min \sum_i \left|z_i\right|$ and $min |z|$. Minimizing $|z|$ did the trick for me.

Answer 1

An alternative linearizable objective is to minimize the maximum absolute difference. Your original objective function is the $L_1$ norm, and this alternative is the $L_\infty$ norm. You can also combine the two by first minimizing one of them (primary objective), then imposing a constraint (objective cut) that the primary objective value must be no more than this minimum, then minimizing the other (secondary) objective.

---

I guess there are actually four main linearizable objective functions to consider: \begin{align} \sum_i \left|x_i - r_i\right| \tag1\label1 \\ \sum_i \left|x_i - t_i\right| \tag2\label2 \\ \max_i \left|x_i - r_i\right| \tag3\label3 \\ \max_i \left|x_i - t_i\right| \tag4\label4 \\ \end{align} You can minimize one of them or some combination. From your problem description, it sounds like you might have been minimizing the sum of \eqref{1} and \eqref{2} rather than $\sum_i |r_i - t_i|$, which is a constant. If $\text{lb}_i \le t_i \le \text{ub}_i$ for all $i$, then you can make both \eqref{2} and \eqref{4} zero by taking $x_i=t_i$.

To linearize \eqref{2}, introduce new decision variable $z_i$ and minimize $\sum_i z_i$ subject to additional constraints \begin{align} z_i&\ge x_i-t_i \\ z_i&\ge t_i-x_i \end{align}

To linearize \eqref{4}, introduce a new decision variable $z$ and minimize $z$ subject to additional constraints \begin{align} z&\ge x_i-t_i \\ z&\ge t_i-x_i \end{align}

Answer 2

I was able to achieve the desired outcome using two LP. Pending test for all corner cases. Also, not sure if this is optimal solution but better than before.

1. First LP, Minimize the absolute sum. Same objective as posted in the question.

\begin{align} min \sum_i \left|x_i - t_i\right| \end{align}

Subject to: \begin{align} \text{lb}_i \le x_i \le \text{ub}_i \\ \sum_i x_i - \sum_i t_i = 0 \\ \ x_1 + x_2 \le 2000 \end{align}

2. Calculate two standard deviation $sd_i$ from the first LP results $x_i$.

   • one for the tasks whose current value is less than target.
   • second for the tasks whose current value is greater than target.

3. Second LP, Add new constraint to have absolute value within calculated sd to reduce variability.

\begin{align} min \sum_i \left|x_i - t_i\right| \end{align}

Subject to: \begin{align} \text{lb}_i \le x_i \le \text{ub}_i \\ \sum_i x_i - \sum_i t_i = 0 \\ \ x_1 + x_2 \le 2000 \\ \left|x_i - t_i\right| \le sd_i \\ \end{align}

This is the outcome I got:

TaskX1 = 1000.0
TaskX2 = 1000.0
TaskX3 = 4500.0
TaskX4 = 4500.0