Description of a constraint for a mixed integer program.

Question

Suppose we have 100 items that are labelled from the set $P = \{A, B, C, D, E\}$. My constraints are as follows:

1. I want to choose exactly seven items.
2. The choice should have at least one item of each type (covers five choices).
3. The sixth choice can be either $D$ or $E$.
4. The seventh choice can be either of the labels.

I was trying to pose this problem as an integer programming problem where I am looking for a $100\times1$ column vector $x \in \{0,1\}$. Each element $x_i$ in $x$ represents whether the item corresponding to $x_i$ is chosen or not.

I am thinking of assigning integers to different labels in the set $P$, but currently unable to perceive how can this be turned into a constraint of the form $c^Tx$, where $c$ is a column vector.

Is this the right way to solve this problem? If yes, can you please explain how to create such a constraint equation. If not, can you please suggest an alternative method.

Answer 1

Define variable $x_{i,j}$ to be 1 if the $i$th item is the $j$th item in the set $P$.

Constraint 1:

$$\sum_j x_{i,j} = 1 \quad \forall i$$

ensures we pick something for each "slot" $i$.

Constraint 2:

$$\sum_i x_{i,j} \geq 1 \quad \forall j$$

ensures we pick at least one of each item $j$

Constraint 3:

$$x_{6,4} + x_{6,5} == 1$$

I assume it mean it has to be either D or E.

Constraint 4:

This doesn't need any extra inequalities.