Given the objective function $\sum_{i=0}^{i=n} t_i$ (which I want to minimize), constraints $At = u, t \geq 0$ where $A \in m \times n$, and $ n>m$, I'm trying to determine all of the possible optimal bases of $t$.
This paper outlines this process pretty well: the main idea is to use the simplex algorithm, but instead of choosing leaving variables based on ratios from $A$ and $u$, every possible leaving variable is chosen, which results in branching after each iteration. (the point of the paper is to do all this without prior knowledge of $u$)
The physical interpretation of this problem (18 thrusters controlling a spacecraft in 6 DoF) is to find all sets of 6 thrusters that (together) could achieve any control input $u \in \mathbb{R}^6$ (i.e. a 3D force + 3D torque) while minimizing the sum of on-times of the thrusters.
The paper presents a table of 120 optimal thruster combinations for their specific $A$ matrix. (the columns of $A$ represents the force and torque produced by each thruster)
I've written code that works perfectly with relatively small dimension $n = 4$ and $m = 2$, but with $n = 18$ and $m = 6$, but I'm trying to reproduce their optimal thruster table, but running into issues where the program finds a huge number of (supposedly) optimal sets, and eventually runs out of memory from branching too many times.
I've added checks to make sure no optimal sets are being repeatedly found, but the program still appears to be finding lots and lots of unique optimal sets. Basically everything appears to be in working order except the total number of sets I'm finding is way higher than what the paper suggests.
Anyone have any thoughts on what could be going wrong?