4
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ You could also try the following. 1. Select $i$ with largest $u_i$. 2. If the problem $\{r_i \le g_m(y) \; \forall m, y\in \Omega \}$ is feasible, you are done, else, try the next largest $i$. $\endgroup$
    – Kuifje
    Commented Jan 21, 2022 at 13:27
  • $\begingroup$ en.m.wikipedia.org/wiki/Special_ordered_set $\endgroup$
    – RobPratt
    Commented Jan 21, 2022 at 14:14
  • $\begingroup$ @Kuifje thanks for your reply. The problem is more complicated than shown herein. Keeping track of all variables makes it somewhat difficult. I am looking for something more systematic. $\endgroup$
    – Duns
    Commented Jan 21, 2022 at 14:27
  • $\begingroup$ Would you please, try clarifying your problem with a simple numerical example? $\endgroup$
    – A.Omidi
    Commented Jan 23, 2022 at 8:31
  • $\begingroup$ @A.Omidi I have added an example. $\endgroup$
    – Duns
    Commented Jan 23, 2022 at 11:59

1 Answer 1

3
$\begingroup$

Depending on the solver used, you may be able to prioritize the $x$ variables so that variables with higher indices are branched on before variables with lower indices (and elements of $x$ are branched on before any other integer variables). You may also be able to instruct the solver, after branching on $x_i$, to prioritize the child with $x_i=1$ over the child with $x_i=0$. Either or both of those may (or may not) speed things up.

$\endgroup$
4
  • $\begingroup$ I think this is more or less what I had in mind. But, I am unsure if I can affect the branching process. Once, I execute the program, it will not stop until returning a solution or unitl the maximum runtime is reached. That is why I was wondering if this could be done by adding cuts to the problem. $\endgroup$
    – Duns
    Commented Jan 21, 2022 at 17:44
  • $\begingroup$ Adding cuts does not change the fact that the program will run until it proves optimality or hits a time/memory/iteration limit. $\endgroup$
    – prubin
    Commented Jan 21, 2022 at 18:54
  • $\begingroup$ Yes, you are right. But I am aiming to reduce the time to solve the problem (optimally). Sometimes adding cuts helps to tighthen the search space but also adds more constraints. I believe that the sorted structure of $ r $ can be exploited by including constraints that depicts that sorted structure but probably that requires more thought. $\endgroup$
    – Duns
    Commented Jan 21, 2022 at 20:25
  • $\begingroup$ What can you say about $g()$ (convex, linear, ...) and $\Omega$ (polyhedral, defined by explicit linear constraints, ...)? If $g()$ is nonlinear and/or $\Omega$ is not polyhedral, you may be able to add cuts on the fly to tighten the LP relaxations. $\endgroup$
    – prubin
    Commented Jan 21, 2022 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.