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
  • 1
    $\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
    Jan 21 at 13:27
  • $\begingroup$ en.m.wikipedia.org/wiki/Special_ordered_set $\endgroup$
    – RobPratt
    Jan 21 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
    Jan 21 at 14:27
  • $\begingroup$ Would you please, try clarifying your problem with a simple numerical example? $\endgroup$
    – A.Omidi
    Jan 23 at 8:31
  • $\begingroup$ @A.Omidi I have added an example. $\endgroup$
    – Duns
    Jan 23 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
    Jan 21 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
    Jan 21 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
    Jan 21 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
    Jan 21 at 21:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.