# How to minimize a linear function subject to $11$ inequality constraints?

I'm not sure if this question qualifies for this place, but I have a linear equation in the form:

$$\begin{array}{ll} \ Ax \geq b\end{array}$$

In VBA in excel.

with A = 11 rows, 4 columns, with random fractions between 0 and 1.

x = a 4 row, 1 column matrix and each $$\begin{array}{ll}\ x_i >=0 \end{array}$$ B is a 11 rows, 1 column matrix containing only 1's.

It appearently is a [linear program] (LP) and I will look into this.

$$\begin{array}{ll} \text{minimize} & x_1 + x_2 + x_3 + x_4\\ \text{subject to} & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.5 x_4 \geq 1\\ & 0.1 x_1 + 0.4 x_2 + 0.3 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.3 x_3 + 0.4 x_4 \geq 1\\ & 0.4 x_1 + 0.9 x_2 + 0.1 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.6 x_3 + 0.1 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.4 x_2 + 0.9 x_3 + 0.2 x_4 \geq 1\\ & 0.6 x_1 + 0.4 x_2 + 0.1 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.7 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.5 x_3 + 0.6 x_4 \geq 1\end{array}$$ I was wondering what the minimisation procedure whilst satisfying the equation, for the sum of all the x_1 to x_4 was.

I thought of taking the minimized summation of all the fractions in 1 row of matrix A and solving for that = 1, so that one would know all others are at least higher, but I was not sure, whether that is garanteed to provide the minimized sum of x's.

Also, that approach would yield infinitely many solutions with 1 row and 4 variables.

• In case of linear (in-)equalities I apply the simplex algorithm. – callculus Oct 25 '16 at 23:57
• What is the domain of $x_1,x_2,x_3$ and $x_4$ ? Is it $x_i \geq 0 \ \forall \ i\in \{1,2,3,4\}$ ? – callculus Oct 26 '16 at 0:18
• Yes thank you, I forgot to add the constraints of the x_i's, Each x_i needs to be positive or 0. I am not sure what the upside down A means, but I think the above is what you ask, and that this answers your question. I shall also learn about the simplex algorithm, thank you. – Maximilian brutus III Oct 26 '16 at 0:33
• Your guess is right. The meaning of $\forall i \ \in \ \{1,2,3,4\}$ is "for all i with the value of $1,2,3$ or $4$". – callculus Oct 26 '16 at 0:38
• Thank you, I think I'm falling in love with this forum <3 – Maximilian brutus III Oct 26 '16 at 0:39

You have the following linear program (LP)

$$\begin{array}{ll} \text{minimize} & x_1 + x_2 + x_3 + x_4\\ \text{subject to} & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.5 x_4 \geq 1\\ & 0.1 x_1 + 0.4 x_2 + 0.3 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.3 x_3 + 0.4 x_4 \geq 1\\ & 0.4 x_1 + 0.9 x_2 + 0.1 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.6 x_3 + 0.1 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.4 x_2 + 0.9 x_3 + 0.2 x_4 \geq 1\\ & 0.6 x_1 + 0.4 x_2 + 0.1 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.7 x_2 + 0.9 x_3 + 0.9 x_4 \geq 1\\ & 0.2 x_1 + 0.3 x_2 + 0.5 x_3 + 0.6 x_4 \geq 1\\ & x_1, x_2, x_3, x_4 \geq 0\end{array}$$

Using PuLP,

from pulp import *

# decision variables
x_1 = LpVariable("x_1")
x_2 = LpVariable("x_2")
x_3 = LpVariable("x_3")
x_4 = LpVariable("x_4")

# define linear problem (LP)
prob = LpProblem("problem", LpMinimize)
prob += x_1 + x_2 + x_3 + x_4   # objective function
prob += x_1 >= 0
prob += x_2 >= 0
prob += x_3 >= 0
prob += x_4 >= 0
# add 11 inequality constraints to the LP
prob += 0.2*x_1 + 0.3*x_2 + 0.9*x_3 + 0.5*x_4 >= 1
prob += 0.1*x_1 + 0.4*x_2 + 0.3*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.3*x_3 + 0.4*x_4 >= 1
prob += 0.4*x_1 + 0.9*x_2 + 0.1*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.9*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.6*x_3 + 0.1*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.9*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.4*x_2 + 0.9*x_3 + 0.2*x_4 >= 1
prob += 0.6*x_1 + 0.4*x_2 + 0.1*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.7*x_2 + 0.9*x_3 + 0.9*x_4 >= 1
prob += 0.2*x_1 + 0.3*x_2 + 0.5*x_3 + 0.6*x_4 >= 1

# solve ILP
prob.solve()

# print results
print LpStatus[prob.status]
print value(x_1)
print value(x_2)
print value(x_3)
print value(x_4)


we get

Optimal
0.0
0.0
1.4285714
1.4285714

• Thank you, I was unfamiliar with the syntax, but I incorporated it reasonably I think. And I will look into the wiki documentation in quest for my answer. – Maximilian brutus III Oct 26 '16 at 0:04
• @MaximilianbrutusIII I updated my answer. – Rodrigo de Azevedo Oct 26 '16 at 0:13
• Thank you, the curse of knowledge; I forgot to mention each x_i needs to be positive or 0. I added it into the question. At least I shall play with the above program in Python to learn about the algorithm so I can understand it, predict what will happen when I alter parameters, and eventually replicate it in my VBA code. – Maximilian brutus III Oct 26 '16 at 0:29
• @MaximilianbrutusIII Excel's Solver can solve linear programs, I believe. – Rodrigo de Azevedo Oct 26 '16 at 0:35
• I think indeed it can, but I thought humans would be better at explaining an algorithm than empirical results from a computer program. I would like to understand the logic and reasoning, then I have a higher flexibility in application and future problems. But looking into the simplex algorithm I think I will. Once again thank you for the concise example. – Maximilian brutus III Oct 26 '16 at 0:44

Each row, considered as equality, represents a 4-D plane, normal to the coefficient vector ($\mathbf a$), and the plane is "distant" $1$ from the origin (where "distance" is the dot product of the position vector of the points on the plane with $\mathbf a$ ) .
Each inequality represents then the half-space limited by the plane and containing points at "distance" larger than $1$ from the origin.
Since the coefficients are all positive, then an unlimited region of points whose projection on the various $\mathbf a$ is greater than $1$ surely exists.
On the average, the solution point closest to the origin will lay onto the $(1,1,1,1)$ direction.
So in your case the only simplification that I see feasible is to start and search for a point that lays on the direction of the resultant of the coefficients, and check the inequalities starting from those whose coefficient vector is more far from the average.