3
$\begingroup$

I have a known matrix, $H$ of size $U\times B$. The optimization variable is $D$ of same size, which is binary

Now I have $$S_u=\frac{\sum\limits_{b=1}^{B} D_{u,b}H_{u,b}}{\sum\limits_{b=1}^{B}H_{u,b}-\sum\limits_{b=1}^{B} D_{u,b}H_{u,b}},\quad \forall u\in\{1,\cdots, U\}$$ and I want to maximize $\sum\limits_{u=1}^US_u$.

UPDATE:

with $b_\min\le \sum_{b=1}^B D_{u,b}\le b_\max, \forall u$ and $\sum_{u=1}^{U}D_{u,b}\le u_\max, \forall b$

Can I perform some alternative formulation so that the function becomes convex, or any convex approximation?

EDIT:

The denominator is strictly non-negative. The first or positive part of the denominator denotes the case where $D_{u,b}=1, \forall b, b=1,\cdots, B$

Also, the elements in $H$ are non-negative.

$\endgroup$
6
  • $\begingroup$ Do you have any other constraints? If not, you can solve a separate problem for each $u$. $\endgroup$
    – RobPratt
    Nov 24, 2020 at 2:07
  • $\begingroup$ For EDIT-2, you should not mix $\sum_u$ and $\forall u$. $\endgroup$
    – RobPratt
    Nov 24, 2020 at 2:08
  • $\begingroup$ @RobPratt, yes, I have other constraints. The constraints are on $D$. Please see my update. $\endgroup$
    – KGM
    Nov 24, 2020 at 8:41
  • $\begingroup$ @RobPratt, how can I enforce the equality constraint? does it make much sense to add an equality constraint in optimization? $\endgroup$
    – KGM
    Nov 25, 2020 at 10:15
  • $\begingroup$ In your new denominator, you have $\sum_u$ when the ratio itself depends on $u$. Should the sum instead be over a dummy index $v$ or just omitted? $\endgroup$
    – RobPratt
    Nov 25, 2020 at 14:07

1 Answer 1

6
$\begingroup$

You can reformulate exactly as a MILP problem by performing a Charnes-Cooper transformation and then a linearization of the resulting products of binary and continuous variables, as described in my answer here.

Because you have a sum of ratios here, introduce a new variable $T_u$ for each summand $S_u$. The idea is to multiply numerator and denominator by $T_u$ so that the denominator becomes 1. You want to maximize $$\sum_{u,b} D_{u,b} H_{u,b} T_u$$ subject to $$\sum_b H_{u,b} T_u - \sum_b D_{u,b} H_{u,b} T_u = 1$$ for each $u$. Now introduce $Y_{u,b} = T_u\cdot D_{u,b}$ to linearize both objective and constraint: $$\text{maximize $\sum_{u,b} H_{u,b} Y_{u,b}$ subject to $\sum_b H_{u,b} T_u - \sum_b H_{u,b} Y_{u,b}=1$}$$ Finally, linearize the relationship between $Y$ and $D$.


For your new question in EDIT 2, first linearize $P_{u,b}D_{u,b}$ and then apply Charnes-Cooper.

$\endgroup$
9
  • $\begingroup$ Thanks for your answer. would you please elaborate a bit. That mean I should introduce additional variable! $\endgroup$
    – KGM
    Nov 23, 2020 at 14:02
  • 1
    $\begingroup$ Can you provide the details of how this is done when the objective is the sum of linear fractionals, as it is in this case? And of course, the transformation is dependent on the nonnegativty of the denominator, which the OP did not state.holds, so should be added as an assunption in the solution.. $\endgroup$ Nov 23, 2020 at 14:07
  • $\begingroup$ @MarkL.Stone, I state that the denominator is nonnegative. Please see my edit. $\endgroup$
    – KGM
    Nov 23, 2020 at 14:28
  • 1
    $\begingroup$ @MarkL.Stone I added more detail. You just need a separate multiplier for each ratio. $\endgroup$
    – RobPratt
    Nov 23, 2020 at 15:31
  • $\begingroup$ @RobPratt, thanks for your answer. I am now implementing it. In fact, I posted a simplified version of my problem. In my original problem, I have another variable, $P_{u,b}$. How can I deal with it? See my EDIT-2. $\endgroup$
    – KGM
    Nov 24, 2020 at 0:04

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.