Suppose that we have the following optimization problem:
$$Maximize_{x_{j,i}} ~ {{\sum_t \sum_i \sum_j (a_{0,i;t}+\sum_i \sum_j a_{j,i;t} x_{j,i;t})}\over{\sum_t\sum_i\sum_j x_{j,j;t} b_{j,i;t}}}$$
$$s.t. ~\sum_t\sum_i\sum_j x_{j,j;t} b_{j,i;t} \leq C, ~~~C\in R_{>0}$$
In the combinatorial scenario where it holds that $x\in {\{0,1\}}$, it can be shown that the solution space increases exponentially with $t, i, j$, and that the time-complexity of an exhaustive search would be of the scale $O(k^n)$. I'm under the impression that, had this been a linear problem where convexity is guaranteed, NP-hardness would not be an issue and one could have solved the problem efficiently (correct me if I'm wrong here). But the non-linearity cases confuses me. I understand that a problem can be both convex and NP-hard, though I'm not sure that what that implies in practice.
My questions:
- What ways are there to prove convexity in this problem?
- Is there a point in trying to prove convexity? Does convexity supersede NP-hardness or is that a false impression of mine?
Your problem can be summarized as $$\max_{x \in \{0,1\}^n} \left\{ \frac{a^Tx + b}{d^Tx} : 1 \leq d^Tx \leq C \right\}.$$ You can solve the relaxed problem ($0 \leq x_i \leq 1$) and round the solution to get a binary solution, but then you lose optimality. You could do branch & bound on the fractional solution, but that is a bit hard to implement because the relaxed problem needs to be reformulated before it can be solved. Below I explain an easier way to feed this problem into mixed integer optimization software such as CPLEX or Gurobi by making it linear.
You can reformulate the problem as: $$\max_{x \in \{0,1\}^n, y \geq 1} \left\{ (a^Tx + b)y : 1 \leq y \leq C, (d^Tx)y = 1\right\}.$$ This is not linear yet, but you can recognize the product of a binary and a continuous variable. Adding $z_i = x_i y$ and McCormick envelopes you get an equivalent linear formulation: $$\max_{x \in \{0,1\}^n, y \geq 1, z \geq 0} \left\{ a^Tz + by : 1 \leq y \leq C, d^Tz = 1, z_i \leq x_i C, z_i \geq y - C(1-x_i) \right\}.$$