Skip to main content
5 of 5
`\label`+`\eqref` while this is on the front page
LSpice
  • 12.9k
  • 4
  • 45
  • 69

I will give you the main idea in the following steps:

  1. You must put initially the empty set directly without counting (I'm assuming that the set contains only positive numbers).
  2. You construct the following mathematical program: $$ x_i = \begin{cases} 1 , & \ \text{if the element } i \text{ of the set } A \text{ is chosen;}\\ 0 , & \ \text{otherwise.} \end{cases}$$

$$\left\{\begin{aligned} & {\min \sum_{i=1}^{n} A_i x_i} \\ & \text{s.t.} \\ & \sum_{i=1}^{n} x_i \geq 1 \end{aligned}\right.\tag{$P$}\label{467374_P}$$ where $n=|A|$.

  1. You solve the problem \eqref{467374_P}, and let $B$ the set of the outer base variables of the optimal solution.

  2. Generate the constraint that excludes the current optimal solution from your domain: $$ \sum_{i\in B} x_i \geq 1.$$

  3. Add the new constraint to \eqref{467374_P}.

  4. Repeat the steps 3, 4 and 5 until \eqref{467374_P} becomes empty. Terminate.

Each solution you get is the minimal possible in the current domain, so you'll get your subsets in the wanted order.

By doing that, I'm assuming that we have only positive numbers, if you have negative numbers (and eventually the number zero) you must omit the step one and the constraint $\sum_{i=1}^{n} x_i \geq 1$ from \eqref{467374_P}.