I have the following (integer) program:

$ \max \sum_{i\in I} \frac{a_i}{b_i + \sum_{j\in J} c_{ij} x_{ij}} $

s.t. $ x \in X $

$ x_{ij}\in \{0,1\}, \quad\forall i\in I \wedge j\in J $,

where $ a_i > 0 $, $ b_i > 0 $, and $ c_{ij} > 0 $, for all $ i\in I $ and $ j\in J $. Here, $ x $ represents the vector of binary variables $ x_{ij} $ and $ X $ is a nonempty convex set defined by a set of linear inequalities/constraints.

Is there a way to reformulate it or to write an equivalent program that is not much harder to solve?

Of course, it can be transformed in a straightforward fashion by setting the objective as $ \max \sum_{i\in I} y_i $, where $ y_i \leq \frac{a_i}{b_i + \sum_{j\in J} c_{ij} x_{ij}}, ~y_i\geq 0 ~(\forall i\in I) $. This will lead to additional constraints

$ b_i y_i + \sum_{j\in J} c_{ij} z_{ij} \leq a_i, ~\forall i\in I $,

where $ z_{ij} = x_{ij} y_i $ is a product of binary and continuous variable (easily linearized). But the solver runtime can be greatly affected if $ |J| $ is large.

If the objective is not a sum, then this would be a special case of linear-fractional programming, and thus an equivalent minimization model could be easily written.

Therefore, my question is if there is an another way, that does not involve too many additional constraints, i.e., if there is, maybe, a way to write an equivalent model in the terms of optimal solutions?

  • $\begingroup$ The post is changed, so that only summations are used. $\endgroup$ – DDCh Mar 12 at 0:34
  • $\begingroup$ X is a convex nonempty set. The variables $ x_{ij} $ should satisfy some constraints, which define that set X. $\endgroup$ – DDCh Mar 12 at 21:58
  • $\begingroup$ Where does this optimization problem come from? At first glance, it looks kind of hopeless. However, knowing its origin can help one reformulate it in a way that is less hopeless. $\endgroup$ – Rodrigo de Azevedo Mar 12 at 22:05

Your Answer

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

Browse other questions tagged or ask your own question.