I kindly ask for some ideas or references to exploit ordering in MILPs.
In particular, there are resources $ r = [r_1, r_2, ..., r_K] $ such that $r_{i} \leq r_{i+1} $. These are input to the problem.
In addition, there are binary variables $ x = [x_1, x_2, ..., x_K] $ such that $ \sum_i x_i = 1 $ used to select the resources. Besides, there are also continuous-valued variables $y$ in a convex set $ \Omega $.
The objective is $ \max_{x,y} \sum_i u_i x_i $ where $ u = [u_1, u_2, ..., u_K] $, $u_{i} \leq u_{i+1} $ represent utility.
My problem looks like this:
$$ \max_{x,y} \sum_i u_i x_i \\ g_m(y) \geq \sum_i r_i x_i, m = 1, \dots, M, \\ \sum_i x_i = 1, \\ y \in \Omega, $$.
One can see that selecting $ x_{i+1} = 1 $ may generate better objectives than $ x_{i} = 1 $.
I would like to exploit the fact that $r_i$ are ordered. For instance, if allocating $ r_j $ does not yield a feasible solution, then it makes no sense to try with $ r_{j+1} $. I am using MOSEK and GUROBI to solve this problem, and I understand that this kind of structure is very particular to my problem and perhaps not exploited by these solvers. I have randomly changed the order of the elements in $ r $ and $ u $ (keeping the one-to-one correspondence) and I get comparable execution times.
Is it possible to add cuts that exploit this structure and reduce the number of evaluations (branches)? I would be very grateful!
Example:
$ r = [0.5, 2.1, 3.7, 5.1] $
$ u = [9.8, 12.5, 18.1, 25.2] $
$ x = [x_1, x_2, x_3, x_4] $
$ y \in \Omega (convex) $
$$ \max_{x,y} \sum_i 9.8 x_1 + 12.5 x_2 + 18.1 x_3 + 25.2 x_4 \\ g (y) \geq 0.5 x_1 + 2.1 x_2 + 3.7x_3 + 5.1 x_4, \\ x_1 + x_2 + x_3 + x_4 = 1, \\ y \in \Omega, $$.
As explained above, if $ x_2 = 1 $ is not feasible, that means that $ g (y) \geq 2.1 $ cannot be satisfied. Thus, evaluating $ x_3 = 1 $, $ x_4 = 1 $ is not necessary due to the sorted strcuture of $ r $. Instead, $ x_1 = 1 $ should be evaluated. I would like to add a constraint that considers this to reduce the number of evalautions.
