Cartesian factorization of a finite set of n-tuples
If I understand the question correctly, the problem is easy (once we understand the problem).

As I understand it, you are given a finite set X⊆A1×…×An and want to find the “best” set I⊆{1,…,n} of indices that is feasible, where we say that a set I is feasible when X can be written as the direct product of the sets Ai for i∈I and some set of (n−|I|)-tuples (where indices are permuted appropriately).

You consider two formulations of the meaning of “best”: (1) the product ∏i∈I |Ai| is maximized, (2) the size |I| is maximized.  However, it does not matter which criterion you use because both can be maximized at the same time.

For each i=1,…,n, test whether the singleton set {i} is feasible (this can be done efficiently).  Let J be the set of indices i such that {i} is feasible.  It is easy to see that J is also feasible, and moreover J is the maximum with respect to inclusion among the feasible sets of indices.  Therefore, the index set J maximizes both criteria (1) and (2) stated above.