# How to solve this convex problem heuristically?

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

• Be careful when you edit and delete part of the question which has been answered. Instead, I suggest to add an "EDIT" paragraph below and specify that you would like to ignore a constraint (instead of deleting it). – Kuifje Nov 16 '20 at 16:14

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}$$.

• the constraint was deleted mistakenly. I still have the same problem and the same constraints. – dipak narayanan Nov 18 '20 at 22:31
• of course, I am able to solve it optimally using some solver. But I need a heuristic solution. – dipak narayanan Nov 18 '20 at 22:33
• OK, then you can still start with the greedy algorithm and then try to repair the resulting solution if needed. If you exceed $a_\max$ for some $i$, change some (possibly more than one) $X_{i,j}$ from $1$ to $0$. If you are below $a_\min$ for some $i$, try to change some (possibly more than one) $X_{i,j}$ from $0$ to $1$ without exceeding $a_\max$ or $b_\max$. – RobPratt Nov 18 '20 at 22:42

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.