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.

  • $\begingroup$ What is your goal ? What kind of result you wish to have after the calculations ? $\endgroup$ – callculus Dec 16 '14 at 15:48
  • $\begingroup$ @calculus I will try to answer your question as I understood it. I want to come up with a vector $x$ that will satisfy these constraints. Are you asking about the real-life application of this problem ? $\endgroup$ – ubaabd Dec 16 '14 at 16:00
  • $\begingroup$ But what does x represent ? Could you give me (us) a possible numerical solution (with explanation) ? And it is known how many items with lable A,B,C,D or E are among the 100 items ? If I understand it right there will be several possible solution. Does the order of drawing play a role ? $\endgroup$ – callculus Dec 16 '14 at 16:16
  • $\begingroup$ @calculus The assumptions are i). Labels are such that at least one such combination exists that satisfies all these constraints. No the order does not matter. As I mentioned, the constraint formulation will be used in an integer program to maximize some objective function. Therefore, despite there will be many such combinations that satisfy these constraints, the program will output the one that has maximum value of the objective function. $\endgroup$ – ubaabd Dec 16 '14 at 16:32
  • $\begingroup$ Do you know, what the objective function is ? I don´t want to annoy you. I just want to understand the problem. $\endgroup$ – callculus Dec 16 '14 at 16:38

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.

  • $\begingroup$ The constraint 4 is that the seventh choice can be $A$, $B$, $C$, $D$ or $E$, i.e., any of the labels. $\endgroup$ – ubaabd Dec 16 '14 at 8:47
  • $\begingroup$ In the case of your solution, the unknown is a matrix $X$ instead of a column vector $x$. Since I am using MATLAB to solve this problem that gives solution in the form of a vector, how should I incorporate your formulation to suit MATLAB GLPK or MATLAB intlinprog. $\endgroup$ – ubaabd Dec 16 '14 at 9:05
  • $\begingroup$ Constraint 4 doesn't seem to need anything extra then. $\endgroup$ – IainDunning Dec 16 '14 at 18:21
  • $\begingroup$ You can just flatten the matrix down to a vector, i.e. map the two dimensions into a vector of length 35 $\endgroup$ – IainDunning Dec 16 '14 at 18:21
  • $\begingroup$ @IanDunning In the formulation of constraint 3, you have defined the constraint for the sixth item only. I assume $i \in \{1,2,\ldots,100\}$. If you meant that $ i \in \{1,2,\ldots,6\}$, how will I know which of the seven out of 100 items are chosen? $\endgroup$ – ubaabd Dec 17 '14 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.