Linear map of unit cube

Question

Let c be a vector of n constants and X = Table[Symbol["x" <> ToString[i]], {i, n}] be a vector of n variables.

Assuming that 0 <= X <= 1, I would like to compute the linear map c.X. This can be expressed with Reduce:

formula = Exists[Evaluate[X], y == c.X && Fold[#1 && 0 <= #2 <= 1 &, True, X]];
Reduce[formula, {y}, Reals]

With increasing n, the performance of this solution drops rapidly. Is there a better way to compute the solution y?

Answer 1

This is a typical linear programming problem. For a given vector c you can quickly find the minimum and maximum values of y that allow a solution X.

Example for n=10:

n = 10;
c = RandomVariate[NormalDistribution[], n]    (* random, to have an example *)
(*    {0.105518, -0.439788, -0.33041, -1.93738, -0.810956, 1.43839, -0.529671, 0.668688, 0.879621, 0.458327}    *)
X = Array[x, n]
(*    {x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10]}    *)
Minimize[{c.X, And @@ Thread[0 <= X <= 1]}, X]
(*    {-4.0482, {x[1] -> 0., x[2] -> 1., x[3] -> 1., x[4] -> 1., x[5] -> 1.,
                x[6] -> 0., x[7] -> 1., x[8] -> 0., x[9] -> 0., x[10] -> 0.}}    *)
Maximize[{c.X, And @@ Thread[0 <= X <= 1]}, X]
(*    {3.55054, {x[1] -> 1., x[2] -> 0., x[3] -> 0., x[4] -> 0., x[5] -> 0.,
                 x[6] -> 1., x[7] -> 0., x[8] -> 1., x[9] -> 1., x[10] -> 1.}}    *)

So for this particular choice of the vector c there exists solutions X if $-4.0482 \le y \le 3.55054$. The convexity of the problem assures that all values of $y$ in this range give rise to solutions X.

The above code is fast and executes in about one second for $n=10^4$. For ultimate speed, call the LinearProgramming function directly: you get the same results, but much faster:

X1 = LinearProgramming[c,
                       -IdentityMatrix[n, SparseArray], 
                       ConstantArray[-1, n]];
X1.c
(*    -4.0482    *)
X2 = LinearProgramming[-c,
                       -IdentityMatrix[n, SparseArray], 
                       ConstantArray[-1, n]];
X2.c
(*    3.55054    *)