My optimization problem is to design a $n*m$ matrix consisting of only $0$ and $1$ as elements, such that the sum of each column is not less than a number given as the constraints. The constraints is given in a form of an integer vector with length of m (so, $m$ is known).
My objective is to work out the matrix with the minimal $n$ (i.e. number of rows).
To construct a new row in the matrix, a coding schema (as shown below, it is a pattern of $0$, $1$ digits with repetition on the pattern, e.g. assuming a pattern of $[1,1,0]$ and repeat it twice to $[1,1,0,1,1,0]$) was required to satisfy.
I will give a simple example below:
Assuming the constraint vector for the sum of each column is $$ [3,4,5,2,2,5,3,4,2,5] $$
The row allowed in the matrix is in a form like
$$ [1,0,0,1,1,0,1,1,0,0] $$
which is consisting of only $0$ and $1$ as aforementioned.
Besides, each row is a $10$-element vector with a fixed pattern repeated twice in the row. The pattern is $[1,1,0,0,0]$.
To begin with the construction of the $n*10$ matrix, I add $3$ rows to meet the first number in constraint vector, i.e.$3$.
$$ [1,1,0,0,0,1,1,0,0,0] \\ [1,1,0,0,0,1,1,0,0,0] \\ [1,1,0,0,0,1,1,0,0,0] $$
So, in current matrix, the sum of first column equals to $3$. Also $n = 3$ at this stage.
Then I move to the next number in constraint vector. It is $4$. That means I need to add one extra row in that pattern.
$$ [1,1,0,0,0,1,1,0,0,0] \\ [1,1,0,0,0,1,1,0,0,0] \\ [1,1,0,0,0,1,1,0,0,0] \\ [0,1,1,0,0,0,1,1,0,0] $$
The new row takes a form of $[0,1,1,0,0,0,1,1,0,0]$. This is from my transforming the standard form $[1,1,0,0,0,1,1,0,0,0]$ by moving it rightward one step and looped the last element $0$ to the head of the new row. This process just makes sure the second column and all its leftward columns meet the sum of constraints.
Then just execute this process $10$ times until all elements in constraint vector were considered and met.
As a result, I will get the derived $n*10$ matrix. And the n is the solution I found.
In my real problem, the problem size is larger than this where $m=336$, also the coding schema is much more complex than just repeating $[1,1,0,0,0]$. So the searching space of the optimal solution is much larger than the case above. I have no idea how to program an algorithm to search the optimal solution. What kind of programming problem it belongs to and any existing algorithm can help? Cheers
Enumerate the allowed row patterns, and let $x_i$ be the number of rows in pattern $i$ you use. Then you have an integer linear programming problem:
Minimize $\sum_i x_i$
subject to $$ \sum_i a_{ij} x_i \ge b_j \ \text{for}\ 1 \le j \le m$$ $x_i$ integers $\ge 0$
where $a_{ij}$ is the $j$'th element in pattern $i$ and $b_j$ is the minimum required sum for column $j$.