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

Question

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 \geq 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.

Answer 1

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
# add 4 nonnegativity constraints
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

Answer 2

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.