0
$\begingroup$

I have a resource allocation problem. There are $M$ users and $N$ resources (machines). One user can be assigned to multiple resources/machines. But maximum $B$ machines can be activated at a time for all the users.

The assignment variable (binary) vector is defined as $x$, $x$ is of length $M*N$

$x_1$: {user 1, machine 1}

$x_2$: {user 1, machine 2}

. . .

$x_N$: {user 1, machine $N$}

$x_{N+1}$: {user 2, machine 1}

$x_{N+2}$: {user 2, machine 2}

. . .

$x_{2*N}$: {user 2, machine $N$}

. . .

$x_{M*N}$: {user $M$, machine $N$}

I have modeled the constraint as

$L0$ norm of $(Ux)<=B$

where $U$ is a matrix carefully designed based on how $x$ is arranged $U$ has $N$ rows and $M*N$ columns. 1's in each row correspond to the positions of differents users paired with the given resource.

I want to get a better model for this constraint without $L0$ norm. We can linearize $L0$ norm but in that case I need to introduce new variables and constraints which I don't want.

I can also a follow a different approach as mentioned in How to linearize this L0 norm of a vector?, but that will introduce a large number of constraints as U and R are vary large numbers, e.e., $M=100$, $N=100$; $B=5$;

Is there a better/easier modeling?

$\endgroup$
13
  • $\begingroup$ @Kuifje can you provide me some more details? This constraint is part of a problem. There are other constraints also. $\endgroup$
    – KGM
    Commented Apr 22 at 11:20
  • $\begingroup$ I think it would help if you described in detail the whole problem. For example, is the trivial solution "0 users allocated to 0 machines" feasible? $\endgroup$
    – Kuifje
    Commented Apr 22 at 11:33
  • $\begingroup$ @KGM, why do you actually want to use a $L-norm$ to restrict the required resources? Why not try to minimize e.g. the number of required or idle resources as the objective function? Also, this link may be relevant. $\endgroup$
    – A.Omidi
    Commented Apr 22 at 12:07
  • $\begingroup$ When you say $x$ is of length $U*R,$ do you mean $M*N?$ $\endgroup$
    – prubin
    Commented Apr 22 at 15:18
  • $\begingroup$ Have you considered a mixed integer linear program with binary variables to indicate which machines are in use? $\endgroup$
    – prubin
    Commented Apr 22 at 15:19

1 Answer 1

1
$\begingroup$

Why don't you define the follwing variables

$x_{ij}:=\{0,1\}$ if user i assigned to machine j

to use these constraints,

$\sum_j x_{ij}\geq 1$ for each user i

at least one machine assigned to each user i

$\sum_i x_{ij}\leq 1$ for each machine j

at most one user assigned to each machine j

$\sum_{i,j} x_{ij}\leq B$

at most B machines are activated

But, if it possible to assigne a machine to more than one user, then, define the following variables

$y_{j}:=\{0,1\}$ if machine j is activated

to use these constraints,

$\sum_j x_{ij}\geq 1$ for each user i

at least one machine assigned to each user i

$M.y_j\geq \sum_i x_{ij}$ for each machine j

Only activated machine j can assigned to some users

$y_j\leq \sum_i x_{ij}$ for each machine j

If machine j does not assigned to some users then it is not activated

$\sum_j y_j \leq B$

at most B machines are activated

$\endgroup$
2
  • $\begingroup$ The constraint that an unused machine cannot be activated, while correct, is unnecessary. An activated but unused machine can just be ignored. $\endgroup$
    – prubin
    Commented May 3 at 17:57
  • $\begingroup$ @prubin Yes. We can ignore it. $\endgroup$ Commented May 3 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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