This is related to my previous question: Is there an efficient way to solve this discrete optimization problem?
although for the problem sizes I am working with, using an IP solver works fine. I'll restate the formulation below: \begin{align} \max &\quad\sum_{j=1}^n x_j\\ \mathrm{s.t.}&\quad \sum_{i=1}^n Q_iy_{ij} \geqslant Q_0x_j,\quad 1\leqslant j\leqslant n\\ &\quad \sum_{j=1}^n y_{ij} \leqslant 1,\quad 1\leqslant i\leqslant n\\ &\quad x_j\in\{0,1\},\quad 1\leqslant j\leqslant n\\ &\quad y_{ij}\in\{0,1\},\quad 1\leqslant i,j\leqslant n, \end{align} where $Q_0$ is a fixed positive integer and the $Q_j$ are fixed positive integers with $Q_j<Q_0$. Given an optimal solution $(x^\star, y^\star)$, define the "waste" $w_j$ for each $1\leqslant j\leqslant n$ by $$ w_j := \max\left\{\sum_{i=1}^n Q_j y^\star_{ij} - Q_0, 0 \right\}. $$ Then $y^\star$ need not minimize $w:=\sum_{j=1}^n w_j$; for example, $Q_0=40$ and $Q=\{11,10,10,10,10\}$.
I'd like to minimize $w$ as well, but it is a nonlinear function of the decision variables, so I'm not sure how to formulate this as an (integer) linear program. Is this possible? (I'm also open to other ideas on how to solve this problem.)
You could first solve the original problem, and then a modified problem where $\sum x_i$ is fixed to the optimum value while as objective you take minimization of $\sum w_i$, that is
$$ \begin{array}{ll} \min & \sum t_j \\ & t_j \geq 0, \\ & t_j \geq \sum_i Q_jy_{ij}-Q_0, \\ & \sum_i x_i = c,\\ & \mbox{other stuff.} \end{array} $$