Hi,
I have the following LP:
min c'x
s.t. Ax=b
x=>0
where
c=[0 0 0 0 0 0 0 0]'
and
A=[0 1 1 0 0 0 1 1;
0 1 0 1 0 1 0 1;
0 1 0 1 1 0 1 0;
1 1 1 1 1 1 1 1]
and b=[b1;b2;b3;1] with b1,b2,b3 are all in [0,1].
My question is about feasibility of this problem. How can I understand
that there exists feasible solutions?

The problem is feasible iff b can be written as a positive linear
combination of the columns in A.
Specifically for this problem, last constraint (last row in A) simply
states that sum(x)=1. Therefore, the problem is feasible iff b* =
[b1,b2,b3]' lies inside the polytope whose vertices are the columns of
A* = [ 0 1 1 0 0 0 1 1;
0 1 0 1 0 1 0 1;
0 1 0 1 1 0 1 0 ]
In other words, if b* can be expressed as a convex combination of the
columns in A*. Now, by simple inspection of A*, it is clear that the
set spanned by all convex combinations of its columns is precisely the
polytope of the allowed region for b*. Hence, the problem is feasible
and, furthermore, stating that the problem is feasible is the same as
stating that b1,b2,b3 are all in [0,1]

Joao wrote:
The problem is feasible iff b can be written as a positive linear
combination of the columns in A.
Specifically for this problem, last constraint (last row in A) simply
states that sum(x)=1. Therefore, the problem is feasible iff b* =
[b1,b2,b3]' lies inside the polytope whose vertices are the columns of
A* = [ 0 1 1 0 0 0 1 1;
0 1 0 1 0 1 0 1;
0 1 0 1 1 0 1 0 ]
In other words, if b* can be expressed as a convex combination of the
columns in A*. Now, by simple inspection of A*, it is clear

Why is it clear? Certainly, if b1+b2+b3 <=1, what you say is true (and
is clear) since by looking at columns 3, 5, and 6 we can conclude that
x3=b1, x5=b3, x6=b2 and x1=1-b1-b2-b3 is a feasible solution. However,
if b1+b2+b3 1, what you say is not clear at all, although it may
still be true. Also: how do you know that all the columns of A* are
vertices? Might not some of the columns be contained in the convex hull
of some others?

R.G. Vickson
Adjunct Professor, University of Waterloo

that the
set spanned by all convex combinations of its columns is precisely the
polytope of the allowed region for b*. Hence, the problem is feasible
and, furthermore, stating that the problem is feasible is the same as
stating that b1,b2,b3 are all in [0,1]

Let A* = [a1 a2 a3 a4 a5 a6 a7 a8] where a_i is the i_th column of a.
>From the problem, it follows that, b* = sum(a_i*x_i) with x_i>=0, i =
1,2,,8 and sum(x_i) = 1. This is precisely the statement that b* is
a convex combination of the columns in A*. Now, if b* can NLY be a
convex combination of the columns of A*, the problem will necessarily
be feasible. b1, b2 and b3 are all in [0,1]. That means that the space
of all values that the vector b* can assume is a cube with vertices
given by the columns in A*, which is the same space that is formed by
all possible convex combinations of these vertices.

I'm not sure what is the source of the misinterpretation, but let me
finish by giving some examples: if b1 = 1, b2 = 1 and b3 = 1, b1 + b2 +
b3 = 3 >1 and x = [0 1 0 0 0 0 0 0]' is a feasible solution. , if b1
= 0.5 , b2 = 0.5 and b3 = 0.5, b1 + b2 + b3 = 1.5 >1 and x = [0.5 0.5 0
0 0 0 0 0]' or x = [0 0 0.5 0.5 0 0 0 0]' , etc are feasible
solutions. Provided that b's are in [0,1] no example can be constructed
that would result in an infeasible problem.

Joao wrote:
Let A* = [a1 a2 a3 a4 a5 a6 a7 a8] where a_i is the i_th column of a.
>From the problem, it follows that, b* = sum(a_i*x_i) with x_i>=0, i =
1,2,,8 and sum(x_i) = 1. This is precisely the statement that b* is
a convex combination of the columns in A*.

Yes, I understand the statement, But the question is: is the statement
true?

Now, if b* can NLY be a
convex combination of the columns of A*, the problem will necessarily
be feasible. b1, b2 and b3 are all in [0,1]. That means that the space
of all values that the vector b* can assume is a cube with vertices
given by the columns in A*, which is the same space that is formed by
all possible convex combinations of these vertices.

I agree, but A* is a submatrix of the whole matrix A in the original
question. That is why I asked whether sum b_i <= 1. If this holds,
the fourth row of A (which is omitted in A*) does not invalidate the
solution. I was worried about whether this remains true also if sum b_i
1.

I'm not sure what is the source of the misinterpretation, but let me
finish by giving some examples: if b1 = 1, b2 = 1 and b3 = 1, b1 + b2 +
b3 = 3 >1 and x = [0 1 0 0 0 0 0 0]' is a feasible solution. , if b1
= 0.5 , b2 = 0.5 and b3 = 0.5, b1 + b2 + b3 = 1.5 >1 and x = [0.5 0.5 0
0 0 0 0 0]' or x = [0 0 0.5 0.5 0 0 0 0]' , etc are feasible
solutions. Provided that b's are in [0,1] no example can be constructed

This sounds like a theorem. What is the proof?

RGV

that would result in an infeasible problem.

The counter examples demonstrate that sum(b_i)<= 1 is not a necessary
condition. The 4th row of A only states that sum(x_i) = 1 (this
condition, together with the non-negativity constraint on x and the
equation A*x=b* implies that b* is a convex combination of the columns
in A*). The proof to the only theorem used, that any point in a bounded
polyhedral set can be described by a convex combination of the extreme
points (vertices) of this polytope, is a common result in linear
programming and can be found in Bazaraa, M.S., Jarvis, J.J. and
Sherali, H.D., Linera Programming and Network Flows, 2nd edition,
Theorem 2.1, p. 69.

Joao wrote:
The counter examples demonstrate that sum(b_i)<= 1 is not a necessary
condition. The 4th row of A only states that sum(x_i) = 1 (this
condition, together with the non-negativity constraint on x and the
equation A*x=b* implies that b* is a convex combination of the columns
in A*). The proof to the only theorem used, that any point in a bounded
polyhedral set can be described by a convex combination of the extreme
points (vertices) of this polytope, is a common result in linear
programming and can be found in Bazaraa, M.S., Jarvis, J.J. and
Sherali, H.D., Linera Programming and Network Flows, 2nd edition,
Theorem 2.1, p. 69.

course. This just proves that I should not interact with a newsgroup
when I am suffering from the Norwalk Virus, as it tends to make me
stupid. The 8 columns of A* are just the 8 vertices of [0,1]^3, so of
course we're done.

RGV