How to model this constraint for a QP problem?

Question

I have a system with 100 users. There are 6 resources. At any point of time, only 2 resources are made available and those resources can be shared among the users.

Some users may not get any resource, e.g., it may not have any demand or other users may have higher priority. As resources are shared among more users, the efficiency of the resources is reduced.

I have defined a variable x as follows.

${\bf x}=[x_1\hspace{1mm} x_2\hspace{1mm} x_3\hspace{1mm} x_4\hspace{1mm} x_5\hspace{1mm} x_6\hspace{3mm}x_7\hspace{1mm} x_8\hspace{1mm} x_9\hspace{1mm} x_{10}\hspace{1mm} x_{11}\hspace{1mm} x_{12}\cdots \hspace{1mm} \cdots \hspace{1mm}x_{595}\hspace{1mm} x_{596}\hspace{1mm} x_{597}\hspace{1mm} x_{598}\hspace{1mm} x_{599}\hspace{1mm} x_{600} ]$

Here the tuples are defines as

${\bf x}=[\lbrace u,r \rbrace,\hspace{1mm}u=1,2,\cdots, 100, r=1,2,\cdots, 6]$

The tuples are ordered as

$x_1=\lbrace u=1,r=1 \rbrace$

$x_2=\lbrace u=1,r=2 \rbrace$

$x_3=\lbrace u=1,r=3 \rbrace$

$x_4=\lbrace u=1,r=4 \rbrace$

$x_5=\lbrace u=1,r=5 \rbrace$

$x_6=\lbrace u=1,r=6 \rbrace$

then

$x_7=\lbrace u=2,r=1 \rbrace$

$x_8=\lbrace u=2,r=2 \rbrace$

$x_9=\lbrace u=2,r=3 \rbrace$

$x_{10}=\lbrace u=2,r=4 \rbrace$

$x_{11}=\lbrace u=2,r=5 \rbrace$

$x_{12}=\lbrace u=2,r=6 \rbrace$

and so on...

Now, I want model the constraint as a linear inequality constraint in the form

$$\bf Ax \le b$$

So, $x_1=1,\hspace{1mm}x_8=1$ is a valid case. Resource 1 and resource 2 {<=2} are activated

$x_3=1,\hspace{1mm}x_9=1$ is a valid case. Only Resource 3 (<=2) activated

but

$x_1=1,\hspace{1mm}x_8=1,\hspace{1mm}x_{15}=1$ is not a valid case. Resource 1, resource 2 and resource 3 (>2) are activated.

How can I model this constraint for a QP problem.

Answer 1

I assume that $x$ is binary. A more natural indexing would be $x_{ur}$, in which case you can introduce binary decision variables $y_r$ and impose linear constraints: \begin{align} x_{ur} &\le y_r &&\text{for all $u$ and $r$} \tag1\label1 \\ \sum_r y_r &\le 2 \tag2\label2 \end{align} Constraint \eqref{1} enforces $x_{ur} \implies y_r$, and constraint \eqref{2} allows at most $2$ resources to be activated.

If you really need your original indexing, replace $x_{ur}$ with $x_{6(u-1)+r}$ in \eqref{1}.

---

You can also avoid introducing new variables, but at the cost of imposing more constraints. For each ordered triple $(u_1,u_2,u_3)$ of distinct users and ordered triple $(r_1,r_2,r_3)$ of distinct resources, you want to enforce the following logical proposition: $$\lnot(x_{u_1 r_1} \land x_{u_2 r_2} \land x_{u_3 r_3})$$ Rewriting in conjunctive normal form somewhat automatically yields linear constraints: $$ \lnot x_{u_1 r_1} \lor \lnot x_{u_2 r_2} \lor \lnot x_{u_3 r_3} \\ (1-x_{u_1 r_1}) + (1-x_{u_2 r_2}) + (1-x_{u_3 r_3}) \ge 1 \\ x_{u_1 r_1} + x_{u_2 r_2} + x_{u_3 r_3} \le 2 $$