7

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!
Adi Shavit
  • 195
  • 5
  • @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. – Adi Shavit Oct 15 '20 at 18:05

1 Answers1

4

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.

Mark L. Stone
  • 13,392
  • 1
  • 31
  • 67
  • This works fine for a single ratio, but my objective is, unfortunately, an affine combination (weighted-sum) of such ratios. – Adi Shavit Feb 09 '21 at 09:00
  • 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? – Mark L. Stone Feb 09 '21 at 14:16
  • 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. – Adi Shavit Feb 09 '21 at 14:18
  • Yes, that would be better as a new question. – Mark L. Stone Feb 09 '21 at 16:35