How to reformulate (linearize/convexify) a budgeted assignment problem?

Question

I have a scheduling problem at hand. In my system, there is a service station with $M$ service outlets, therefore, the service station can serve $M$ users at a time. But, there are $N$ users $N>M$ in the system requesting for service. There, the scheduler needs to schedule $M$ users out of $N$ users along with some signal processing. The service station has some money budget. At any point of operation, the money spending for serving $M$ users cannot exceed the budget. Let us assume that the scheduling frequency is one hour. So, each hour, the service station serves (at most) $M$ users.

There exists a path between the service point and any user. Let vector ${\bf h}_i\in\mathbb{C}^{M\times 1}$ define the path between the service station and user $i$. If user $i$ is schduled, the amount of money spent after user $i$ is given by $||{\bf w}_i||_2^2=P_i$, where, ${\bf w}_i\in\mathbb{C}^{M\times 1}$ is some financial tool employed by the service station. Note that ${\bf h}_i\in\mathbb{C}^{M\times 1},i=1,2,\dots,N$ are known. Here, ${\bf w}_i, i=1,2,\dots,M$ are optimization variables.

The objective of the optimization is

$$\underset{\mathcal{M}\subset \mathcal{N}}{\max}\hspace{2mm}\underset{{\bf w}_i,i\in \mathcal{M} }{\max}\hspace{2mm}\sum_{i\in\mathcal{M}}\alpha_i \log_2(1+\gamma_i)$$

with

\begin{equation}\label{1} {\gamma}_i = \frac{\left|\mathbf{h}_i^H\mathbf{w}_i\right|^2}{\sum\limits_{j=1,j\ne i}^N\left|\mathbf{h}_i^H\mathbf{w}_j\right|^2 + {\sigma^2}}. \end{equation}

subject to

$$\sum_{i\in\mathcal{M}}||{\bf w}_i||^2_2\le P$$

Here, $\mathcal{M}=\{1,2,\dots,M\}$ is a finite set of $M$ scheduled users, and $\mathcal{N}=\{1,2,\cdots,N\}$ is a finite set of all users. $\alpha_i$s are also known positive (>0) numbers. Therefore, I want to find the subset $\mathcal{M}$, i.e., schedule $M$ users out of $N$ so that the objective is maximized while fulfilling the constraint.

Note that this is a complex scheduling problem. Anyway, is this formulation reflecting what I just described?

Note: ${\bf w}_i$ is the interference (at user $i$) cancelling vector used at the sevice station.

${\textbf{The approach:}}$

Let us introduce a binary variable $x_i\in\{0,1\}$. If user $i$ is scheduled, $x_i=1$, else $x_i=0$. Now, I have a mixed integer programming problem as below

$$\underset{{\bf w}_i }{\max}\sum_{i=1}^N x_i\alpha_i \log_2(1+\gamma_i)$$ subject to $$\sum_{i=1}^N x_i||{\bf w}_i||^2_2\le P$$ $$\sum_{i=1}^Nx_i=M$$ $$x_i\in\{0,1\}$$

How can we deal with the objective and the constraints to have an efficient linear/convex formulation?

Can we take advantage of the monotonic behavior of the logarithm in the transformation?

Answer 1

Cool problem! There are a couple of things you can do to make this problem more tractable. Before starting, do you really need the variables and some parameters to be complex numbers? In particular, according to your notation, are the $|\cdot|$ the complex modulus of the vectors? For more details of (MI)LP over complex numbers check this other question. There are some tools that allow you to do optimization over complex number using a bijective mapping between the complex and the real numbers. But well, the following reformulation stands for real or complex variables.

Let's begin.

1) Objective function

Notice that the objective function can be written as $$\sum\limits_{i=1}^N x_i\alpha_i \log_2 \left(1+\frac{|\bf{h}_i^Hw_i|^2}{\sigma^2+\sum\limits_{j=1\\ j\neq i}^N|\bf{h}_j^Hw_j|^2}\right).$$ You can write the $\log_2$ term as follows (just distribute the denominator and use the logarithm properties)

\begin{align}\log_2 \left(1+\frac{|\mathbf{h}_i^H \mathbf{w}_i|^2}{\sigma^2+\sum\limits_{j=1\\ j\neq i}^N|\mathbf{h}_j^H \mathbf{w}_j|^2}\right)&=\log_2 \left(\frac{\sigma^2+\sum\limits_{j=1}^N|\mathbf{h}_j^H \mathbf{w}_j|^2}{\sigma^2+\sum\limits_{j=1\\ j\neq i}^N|\mathbf{h}_j^H \mathbf{w}_j|^2}\right)\\&= \log_2 \left(\sigma^2+\sum\limits_{j=1}^N|\mathbf{h}_j^H \mathbf{w}_j|^2\right)-\log_2 \left(\sigma^2+\sum\limits_{j=1\\ j\neq i}^N|\mathbf{h}_j^H \mathbf{w}_j|^2\right).\end{align}

This yields an objective function that can be separated into two parts: $$\sum\limits_{i=1}^N x_i\alpha_i \log_2 \left(\sigma^2+\sum\limits_{j=1}^N|\mathbf{h}_j^H \mathbf{w}_j|^2\right) - \sum\limits_{i=1}^N x_i\alpha_i \log_2 \left(\sigma^2+\sum\limits_{j=1\\ j\neq i}^N|\mathbf{h}_j^H \mathbf{w}_j|^2\right).$$

The first term can be further simplified as $$\log_2 \left(\sigma^2+\sum\limits_{j=1}^N|\mathbf{h}_j^H \mathbf{w}_j|^2\right)\sum\limits_{i=1}^N x_i\alpha_i$$ but let's leave it inside as if it was indexed in $i$ for simplicity.

Since you are maximizing, you would like the terms in the objective function to be concave to make your problem easier to solve. Since you have a product of binary and continuous variables in both terms of your objective function, you would like to reformulate the product. Fortunately, this can be done.

For simplification assume that you have the product $x_i v_i$ and $x_i \in \{ 0,1 \}$ and $v_i \in [L_i, U_i]$. Since you correctly commented that $\log_2$ is monotonic, you can derive the lower and upper bounds for each continuous part. Once you have there, for each product you introduce a variable $z_i = x_i v_i$ and the following constraints:

\begin{cases}z_i \leq U_i x_i \\ z_i \geq L_i x_i \\ z_i \leq v_i - (1-x_i)L_i \\ z_i \geq v_i - (1-x_i)U_i\end{cases}

Notice that since you have some positive and negative values in the objective function you can ignore two of the constraints that arise from the reformulation since they will never be active.

Your objective function becomes the linear expression $$\max\limits_{x,\mathbf{w},z} \sum\limits_{i=1}^N \alpha_i(z_i^1-z_i^2).$$

You would still have some constraint of the type

\begin{cases}z_i^1 \leq \log_2 \left(\sigma^2+\sum\limits_{j=1}^N|\mathbf{h}_j^H \mathbf{w}_j|^2\right) - (1-x_i)L_i^1\\z_i^2 \geq \log_2 \left(\sigma^2+\sum\limits_{j=1}^N|\mathbf{h}_j^H \mathbf{w}_j|^2\right) - (1-x_i)U_i^2\end{cases} with some bounds that you can find (e.g. $L_i^1 \leq \log_2(\sigma^2)$) which are nonlinear because of the $\log_2$. The first set of constraints is convex though (assuming you can compute those complex norms as with real numbers), so that's something.

2) Constraints

These are easier, given that the norm is already convex, meaning that after reformulating the binary-norm product with the trick above, you will obtain a set of convex inequalities. Just use $v_i = ||\mathbf{w}_i||_2^2$. Since according to your previous comment $\mathbf{w}_i$ are unit vectors, deriving bounds to its norm is trivial. In this case, you can also ignore two of the constraints from the reformulation (given the fact that you have an inequality), and you don't need to worry about $\mathbf{w}_i$ being complex given that the $||\cdot||_2^2$ is the same as if you have a twice as large real vector (in this case a matrix).

3) Final thoughts

You are dealing with a nonconvex MINLP. Some of those nonconvexities can be easily convexified (the bilinear binary-continuous terms), while others are not so easy. It may also depend heavily on the algorithm that you are using to solve the problem and what you are interested in. If you do not mind obtaining a local optimal solution, you may just partially reformulate the problem as written here. You may even try to put all the nonlinearities and nonconvexities in the objective and see how far a local solver can get you. If you do care about global optimality, the reformulations here are valid (no relaxations or approximation were introduced) but the global solvers (e.g. BARON, ANTIGONE or SCIP) might be more successful on the original form of the problem.

I'm curious how this ends up behaving, let us know!