7
$\begingroup$

I'm using cvxpy to model a problem. Inside a very large and complex LP, I create two continuous, affine (unconstrained) expressions: $x$ and $y$. Due to how they are created, I know that $0\lt x \lt y \leq U$. Obviously: $x/y \lt 1$.

In my LP objective, how do I maximize the ratio $x/y$?

Things I tried:

  • Maximizing x*cp.inv_pos(y) states my problem is non DCP (also if I try to minimize the inverse)
  • I found various LP formulations for maximizing ratios (e.g. here or here) but these requires rewriting the constraints on all the terms in the expressions for $x$ - I have no idea how to do that with cvxpy.
    If this is the way to go then an example would be very helpful!
$\endgroup$
1
  • $\begingroup$ @Mason the measure I need to maximize needs to be a “unitless” proportion between 0-1 so that it it properly scaled with other measures in the objective. $\endgroup$
    – Adi Shavit
    Oct 15 '20 at 18:05
4
$\begingroup$

CVXPY makes this easy to do, using its disciplined quasiconvex programming (DQCP) capability.

An example is provided at https://www.cvxpy.org/examples/dqcp/concave_fractional_function.html . Fractional Linear programming, as you have, is a simple special case of this.

$\endgroup$
4
  • $\begingroup$ This works fine for a single ratio, but my objective is, unfortunately, an affine combination (weighted-sum) of such ratios. $\endgroup$
    – Adi Shavit
    Feb 9 at 9:00
  • $\begingroup$ You neglected to state that in your original question. Your newly state problem is a different problem. Perhaps you can provide the complete problem, with all constraints? $\endgroup$ Feb 9 at 14:16
  • $\begingroup$ You're right. My original question was about ratios - which as you suggested I can maximize. However, I then realized that my true objective is a weighted-sum of ratios. I can post that as a separate question if you prefer. $\endgroup$
    – Adi Shavit
    Feb 9 at 14:18
  • $\begingroup$ Yes, that would be better as a new question. $\endgroup$ Feb 9 at 16:35

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.