How to solve this convex problem heuristically?

Question

I have the following problem

$$\max_{X_{i,j},i\in N_{U},j\in N_{B}}\sum_{i=1}^{N_U}\sum_{j=1}^{N_B}R_{i,j}X_{i,j}$$ $$\text{subject to}$$ $$a_{\min}\le\sum_{j=1}^{N_B}X_{i,j}\le a_{\max}, \forall i$$ $$\sum_{i=1}^{N_U}X_{i,j}\le b_{\max}, \forall j$$

It is a convex problem,b ut I need a heuristic approach to solve this.

Here, $R$ is a knowm matrix. $X$ is a binary matrix. $a_{\min}$, $a_{\max}$ and $b_{\max}$ are also know. and positive

Any suggestions

Answer 1

Now that you have removed the range constraints, the problem decomposes by $j$ and can be solved optimally for each $j$ by a greedy algorithm: set $X_{i,j}=1$ for the $b_\max$ largest (positive) values of $R_{i,j}$.

Answer 2

This is a minimum cost flow problem in the bipartite graph $G=(V,A)$ with $V=N_U \cup N_B$.

Add a source node and link it to each vertex $v\in N_U$. On each of these arcs, constrain the flow to be in the range $[a_{min},a_{max}]$. Note that if $a_{min} > |N_B|$ the problem is infeasible.

Likewise with a sink node, that you link to each vertex $v \in N_B$, and constrain the flow such that it does not exceed $b_{max}$.

Then, on edges $(i,j) \in A$, add a cost $-R_{ij}$, a capacity $Q_{ij}=1$, and find a minimum cost flow in this graph.

Not only is this problem convex : it can be solved in polynomial time with the above approach. Are you sure you want a heuristic when you have a free optimal solution ? I guess if you really want a heuristic for such problems you can checkout for example this paper.