4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Kuifje Nov 16 '20 at 16:14
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ the constraint was deleted mistakenly. I still have the same problem and the same constraints. $\endgroup$ – dipak narayanan Nov 18 '20 at 22:31
  • $\begingroup$ of course, I am able to solve it optimally using some solver. But I need a heuristic solution. $\endgroup$ – dipak narayanan Nov 18 '20 at 22:33
  • $\begingroup$ 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$. $\endgroup$ – RobPratt Nov 18 '20 at 22:42
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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