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 '20 at 2:07
  • $\begingroup$ For EDIT-2, you should not mix $\sum_u$ and $\forall u$. $\endgroup$
    – RobPratt
    Nov 24 '20 at 2:08
  • $\begingroup$ @RobPratt, yes, I have other constraints. The constraints are on $D$. Please see my update. $\endgroup$ Nov 24 '20 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$ Nov 25 '20 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 '20 at 14:07
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$ Nov 23 '20 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 '20 at 14:07
  • $\begingroup$ @MarkL.Stone, I state that the denominator is nonnegative. Please see my edit. $\endgroup$ Nov 23 '20 at 14:28
  • 1
    $\begingroup$ @MarkL.Stone I added more detail. You just need a separate multiplier for each ratio. $\endgroup$
    – RobPratt
    Nov 23 '20 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$ Nov 24 '20 at 0:04

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.