3
$\begingroup$

I'm trying to figure out the general solution to a min-max problem. The general form of the problem is as follows:

  x1 +   x2 + ... +   xn  = T
a1x2 + a2x2 + ... + anxn  = At * T
  x1                     >= 0
  x1                     <= T1
         x2              >= 0
         x2              <= T2
            ...
                      xn >= 0
                      xn <= Tn

Where T and At are target values supplied by the user.

a1..an are known multipliers for the variables x1..xn respectively.

T1..Tn are known maximum values for each variable x1..xn respectively.

This is essentialy a Multi-Objective Linear Programming problem. My objective is to get a value as close as possible to the target values T and At. The problem is, most linear programming problems try to maximize or minimize the result (in this case, it would be T and At), however my objective is to provide values for x1..xn that are as close to the particular values as possible.

My background in math isn't as strong as it probably should be, but I've been doing some research in order to solve this problem.

Would the best approach be to move the T and At * T values to the left hand side as constants, and try to minimize the function (ie. as close to zero as possible)? If that's the case, how would I approach this for a solution? Most of the examples for this kind of problem that I've seen do not have constants within the objective function. Are they just ignored in terms of the solution matrix? That means it's not that useful. Perhaps, ignore the constants, and compare the proposed solutions to those constant, and recalculate if they are outside of a basic tolerance, by adding additional constraints?

--- EDIT --- based on @calculus suggestions, I have come up with the following.

I'm trying to use a simplex algorithm to solve this problem. The algorithm takes an MxN matrix of constraint coefficients ([A]), an M-length vector of constraint upper limits ([b]) and an N-Length vector of objective coefficients.

Can anyone confirm that the objects I'm using are correct:

c = [0, 0, ... 0, 1, 1, 1, 1]  

where the first part corresponds to the coefficients for x1..xn, and the last 4 1's correspond to the coefficients for y3+, y3-, y4+ and y4-.

b = [T1, T2, ..., Tn, T, AtT] 

where these are the upper limits for each individual x1..xn, and the solutions for the sum(xn), and sum(anxn) equations respectively.

A = 1, 0, ... 0,  0,  0,  0,  0
    0, 1, ... 0,  0,  0,  0,  0
          ...
    0, 0, ... 1,  0,  0,  0,  0
    1, 1, ... 1, -1,  1,  0,  0
   a1, a2,...an,  0,  0, -1,  1

where the first batch of rows correspond to the xn <= Tn rows, then 2nd last line corresponds to x1 + .. xn - y3+, + y3- = T and the last line corresponds to a1x1 + ... anxn - y4+ + y4- = AtT

Does this make sense?

--- Edit 2 ---

I used a known problem with a solution to test this out.

T = 1000, At = 1.5, a1 = 5, a2 = 1, T1 = 500, T2 = 1000.

This can be solved arithmetically:

x + y = 1000,       (x1+..+xn = T)
5x + y = 1500       (a1x1+...+anxn = AtT)

results in x = 125, y = 875

so I created the matricies necessary:

b = [500, 1000, 1000, 1500]
c = [0, 0, 1, 1, 1, 1]
A = |1, 0,  0, 0,  0, 0|
    |0, 1,  0, 0,  0, 0|
    |1, 1, -1, 1,  0, 0|
    |5, 1,  0, 0, -1, 1|

but the solver I'm using says the program is unbounded.

$\endgroup$
1
$\begingroup$

Let

$x_1 + x_2 + ... + x_n=y_1$

and $a_1x_2 + a_2x_2 + ... + a_nx_n = y_2$ the two addtional constraints.

The provisional objective function would be $|y_1-T|+|y_2-At\cdot t|$ to calculate the sum of the two differences. It doesn´t play a role wether the differences are positive or negative or not.

To get rid off the absolute values, you have to define:

  1. $y_3=y_1-T$ and $y_4=y_2-At\cdot t$

The objective function is now $|y_3|+|y_4|$

  1. $|y_3|=y_3^++y_3^-$ and $|y_4|=y_4^++y_4^-$

And finally the objective function is

$\texttt{min} \ \ y_3^++y_3^-+y_4^++y_4^-$

Transforming $y_3$ and $y_4$

$y_3=y_3^+-y_3^-$ and $y_4=y_4^+-y_4^-$

The two additional constraints are

$x_1 + x_2 + ... + x_n=y_3^+-y_3^-+T$

$a_1x_2 + a_2x_2 + ... + a_nx_n = y_4^+-y_4^-+At\cdot t$

The variables are $x_i, y_3^+,y_3^-, y_4^+,y_4^- \geq 0$

$\endgroup$
  • $\begingroup$ I reviewed your suggestions and have added an edit to my original question above outlining the structure that would need to be used to solve this problem using a simplex algorithm. Does it look correct? $\endgroup$ – Code Monkey Apr 28 '15 at 14:39
  • $\begingroup$ @CodeMonkey First I have to say, that had to edit my answer. It is $|y_3|=y_3^++y_3^-$ and $|y_4|=y_4^++y_4^-$ and $y_3=y_3^+-y_3^-$ and $y_4=y_4^+-y_4^-$. I mixed up the signs. "+ .. xn - y3+, -y3- - y4+ - y4- = T" Why do you substract $y_3$ and $y_4$ ? It is $+ .. x_n - y_3^+ + y_3^- = T$, with the edited definition. And what about the constraints $\ldots \leq T_1$ and $\ldots \leq T_2$. Beside this, it looks ok. $\endgroup$ – callculus Apr 28 '15 at 15:58
  • $\begingroup$ I made a mistake in that, which I have updated. It was supposed to be "x1+..xn - y3+ + y3- = T" and "a1x1+..anxn - y4+ + y4- = AtT". I also updated the corresponding matrix to match that structure. I have tested this against a simplex solver, and I keep getting "program is unbound". I used a simple (and known) example which I will attach to the original question. $\endgroup$ – Code Monkey Apr 28 '15 at 16:07
  • $\begingroup$ The reason I was getting "program is unbounded", was because the solver I was using assumed max instead of min. I reversed the sign for all the values in the c vector, and I no longer get the unbound error, but the solver results in a trivial solution where x1..xn is 0 for all cases. $\endgroup$ – Code Monkey Apr 28 '15 at 16:24
  • $\begingroup$ I did a step through of the logic for the algorithm and the reason that I'm getting a trivial solution, is because the "c" values that the algorithm uses for an optimal solution all must be <= 0. The initial state of the tableau puts all theses values as either 0 or -1 using the data I proposed above. I'm somewhat at a loss for figuring out the solution here. I think because the "y" values are actually dependent on the original X values, I may need to expand the original objective function to use just the original x values, instead of replacing them. $\endgroup$ – Code Monkey Apr 28 '15 at 18:21
1
$\begingroup$

Thanks to the help from @calculus, I was able to come up with a solution that appears to work:

Instead of trying to take the absolute value of the difference between target and sum of all variables, I decided to just sum all my objective functions together into one, and maximize that.

All values have to be positive and all the objective functions are additions with positive coefficients, so taking an absolute value of the difference won't really mean much, especially if there is a constraint that indicates that the individual sums must be less than a specified target value.

The final generalized problem is:

  • assume one objective function in the form of $Z = x_1 + .. + x_n$
  • assume an arbitrary number of additional objective functions from [0..i] all in the form of $Z_i = [ a_1 x_1 + ... + a_n x_n ]_i$
  • with conditions:
    • $(x_i \geq 0)]^1_n$
    • $(x_i \leq T_i)]_n^1$
    • $(x_1+...+x_n) \leq T$ (first objective)
    • $(a_1i x_1i + ... + a_ni x_ni) \leq A_ni * T]_i^1 $ (additional objectives if any)
  • Where
    • $A_ni$ is a known target multiplier for each of the additional objective functions
    • $T$ is a known target sum.
    • { $a_ni$ } are known multipliers for every variable $x_n$ for each additional objective function.
    • $T_i$ is a known upper bound to for each variable $x_i$ used commonly throughout.

The structure of the solution is:

  • Create a single objective function that is a sum of all the functions:
    • $(1 + a_11 + a_12 + ... a_1i)x1 + ... + (1 + a_n1 + a_n2 + ... + a_ni)x_n$
  • Solve maximum using a simplex tableau:
    • $ A = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & & \ddots & \\ 0 & 0 & \cdots & 1 \\ 1 & 1 & \cdots & 1 \\ a_11 & a_21 & \cdots & a_n1 \\ \vdots & & \ddots & \\ a_1i & a_2i & \cdots & a_ni \end{bmatrix}$
    • $ b = \begin{bmatrix} T_1 & T_2 & \cdots & T_n & T & A_1 & \cdots & A_i \end{bmatrix}$
    • $ c = \begin{bmatrix} (1 + a_11 + a_12 + ... a_1i) & \cdots & (1 + a_n1 + a_n2 + ... + a_ni) \end{bmatrix}$

The solution is collection of values of x[0..n-1] from the simplex result, providing the amount from each source required to total the target value T, constrained by the multipliers A[0..i]

$\endgroup$
0
$\begingroup$

Minimise $d$

where

$d>T-x_1-x_2-x_3-...-x_n$

$d>x_1+x_2+x_3+...x_n-T$

$d>At \times T-a_1x+1-a_2x_2-a_3x_3-...-a_nx_n$

$d>a_1x+1+a_2x_2+a_3x_3+...+a_nx_n- At \times T$

This way $d$ is a measure of how far you are away from your desired target (notice that it needs to be both ways) and you are trying to minimise that measure.

$\endgroup$
  • $\begingroup$ Thanks for the help. This gave me some ideas that lead ultimately to the solution I provided above. $\endgroup$ – Code Monkey Apr 29 '15 at 12:46

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.