The family of integer programs this problem may belong to

Question

I have an integer program that I need to solve and I do not know if it belongs to any specific class of integer programs.

The binary $\{0,1\}$-valued vectors $\pmb{x}^i_{1:T} = (x^i_1, x_2^i, \ldots, x_T^i), i = 1, \ldots, r$ form the variables in the problem where $r$ is a non-negative integer that enumerates these vectors and needs to be maximized. The quantities $y_1, \ldots, y_T$ and $E$ are non-negative integers that are known.

The problem I need to solve is

$$ \max \;\; r \\ \text{subject to} \; \; \sum\limits_{i=1}^r x_t^i \le y_t \; , \; \text{for all} \; \; t = 1, \ldots, T \\ \sum\limits_{t=1}^T x^i_t = E \; , \; \text{for all} \; \; i = 1, \ldots, r \\ x^i_t \in \{0,1\} \; , \; \text{for all} \; \; i = 1, \ldots, r \;, \; t = 1, \ldots, T \\ r \in \mathbb{Z}_{\ge 0} $$ I have formulated this problem as an intermediate step in a larger research problem. I wonder if anyone that recognizes the broader class of integer programs that this problem may belong to, share their insights here. It would also be immensely helpful to guide me to relevant resources on the related families of integer programs so I can read more about it.

Thanks so much!

Answer 1

You can use a technique known as column generation. The idea is to solve the linear programming (LP) relaxation of your problem with the current set of variables (the "restricted master" problem). Then use the optimal master dual variables as input to a "column-generating" integer linear programming (ILP) subproblem that tries to find a new solution $x$ with negative reduced cost. If there is none, you have implicitly solved the unrestricted master LP. Otherwise, augment the master with the new column, and repeat as needed. Once you solve the master LP to optimality, you can then solve the restricted master as an ILP to get an integer feasible solution. If the optimal objective value agrees with the LP objective value, you are done. Otherwise, you need to branch, and the full method is called branch-and-price.

An alternative approach if you know an upper bound $\bar{r}$ on the optimal $r$ is to take $r=\bar{r}$ and introduce additional binary variables $z_i$ for $i\in\{1,\dots,r\}$, change the objective to maximize $\sum_{i=1}^r z_i$, and change the equality constraints to $$E z_i \le \sum_{t=1}^T x_t^i \le E z_i + T(1-z_i),$$ so that $z_i = 1$ implies $\sum_{t=1}^T x_t^i=E$. To reduce symmetry, you can also introduce linear constraints $z_i \le z_{i-1}$.

Answer 2

There are $N={T \choose E}$ possible vectors in $\{0, 1\} ^{T}$ whose components sum to $E$. Let us enumerate them as $\left\{a^{1},\dots,a^{N}\right\}$. We can rewrite your problem as the following integer linear program:

\begin{align*} \max & \sum_{i=1}^{N}z_{i}\\ \textrm{s.t.} & \sum_{i=1}^{N}a_{t}^{i}z_{i}\le y_{t}\,\forall t\in\left\{ 1,\dots,T\right\} \\ & z\in\left\{ 0,1\right\} ^{N}. \end{align*}

Option 1: If $N$ is small enough (relative to the capabilities of your hardware and software), you can just solve this model.

Option 2: If $N$ is too big to let you solve the model outright, you can use the heuristic procedure: start with a restricted set of columns; relax integrality; solve the LP; use the dual values to generate a new column; repeat until no new columns emerge; restore integrality restrictions and solve the ILP. Generating new columns amounts to solving an ILP with $T$ binary variables each time and one constraint (that they sum to $E$) each time.

Option 3: If $N$ is big, you need a provably optimal solution, and option 2 doesn't get you one, resort to branch and price as Rob said.