# Exploiting ordering to removing infeasible solutions in MILP

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.

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

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.

• 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.
– Duns
Jan 21 at 17:44
• Adding cuts does not change the fact that the program will run until it proves optimality or hits a time/memory/iteration limit.
– prubin
Jan 21 at 18:54
• 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.
– Duns
Jan 21 at 20:25
• 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.
– prubin
Jan 21 at 21:54