Linear programming: model to only pick 10% of the variables as non zero

Question

I am building a linear programming model. For the sake of simplicity, Imagine that I'm trying to fill a bunch of items into a bunch of boxes. I have a lot of box types I can choose from but the model must pick up to 10 box types. There are unlimited amount of boxes in each type. for each box type it picks, the model must use that type for at least 5% of the total volume. Here's what I have:
Minimize Cost to put items in the boxes subject to the following constraints:

All items must be packed
of all the box types available, the model can only choose up to 10 box types to be used.
Each of those 10 types to be filled, the model has to use a minimum of 5% of those box types

The model isn't very complicated, but I'm stuck at how to model constraint #2. So of the 100s of box types available, the model must pick up to 10 to match the minimize equation

RobPratt · Answer

Let $v_i$ be the volume of item $i$, and let $c_{i,b}$ be the cost of placing item $i$ in a box of type $b$.  Let binary decision variable $x_{i,b}$ indicate whether item $i$ is placed in a box of type $b$, and let binary decision variable $y_b$ indicate whether box type $b$ is used.  The problem is to minimize $sum_{i,b} c_{i,b} x_{i,b}$ subject to:
begin{align}
sum_b x_{i,b} &= 1 &&text{for all $i$}\
x_{i,b} &le y_b &&text{for all $i$ and $b$}\
sum_b y_b &le 10 \
left(0.05 sum_i v_iright) y_b &le sum_i v_i x_{i,b} &&text{for all $b$}
end{align}

Linear programming: model to only pick 10% of the variables as non zero

One Answer

Add your own answers!

Ask a Question