Excel OpenSolver: non linearity issue

Expressing the constraint of 1 supplier per region is not as easy as it seems in Excel, if we must avoid non-linear functions, or at least I can't see an easy implementation.

One way to deal with it is using a set of indicator (binary) variables that will switch to one as soon as the sum in a given region and for a given supplier is greater than zero. Once we have them, we can easily constrain their sum to be 1 for each region.

In the attached file you find a setup with one more matrix of aux_vars, and below that the constraint to force them to 1. The value of the constant (5) is as little as possible (there are at most 4 clients per region, and only 1 supplier for each).

Let me know if this works for you.

HTH,

Francesco

Let's name the main binary variables as X_i,j, where i is the client and j the supplier, and consider the set linked to the first region and supplier (from X_1,1 to X_3,3).
Saying that we want at most 1 supplier in each region is like saying that, for each of the 9 bin vars in this set, the sum with any var of another supplier must be <= 1. For instance:

X_1,1 + X_1,4 <= 1
X_1,1 + X_1,5 <= 1
...
X_1,1 + X_1,15 <= 1
X_1,1 + X_2,4 <= 1
...
X_1,1 + X_3,15 <= 1

and so on for the remaining vars, suppliers and regions. It could also be written as

X_1,1 + sum(X_i,j) <= 1, with i = 1 to 3, j = 4 to 15

As you can see, these constraints are linear, and they can be expressed in a compact form if you use some high-level mathematical/algebraic programming language as GAMS, or Pyomo. With Excel, we should add them to the model through VBA (I can't imagine doing it by hand).
Instead, we can calculate the sum for each set, and reason on a 8x5 matrix. The only problem is, now we deal with integers, not binary vars. So, to answer your second question, we need some aux vars to map the values (0 - max_sum) to (0 - 1).

Unfortunately, there is no general rule to follow. We usually add aux vars when we have discontinuous functions, and among them, if statements are by far the most common, but this rule is not written in stone.

The constant is the smallest integer greater than the max number of clients that can be allocated in a region, you are right. We can use 5 because there are also the constraints in column AK. Without them, 21 would be enough (supplier 3 - Chuvash republic).

I'm not aware of a single source dealing exactly with this topic: building a good model, and using bin vars to linearize constraints, is a skill you acquire through experience.

You may find interesting:

Integer programming tricks (from the AIMMS guide), pdf;

chapter 9 of Applied Mathematical Programming, which is freely available;

chapter 9 and 10 of Model Building in Mathematical Programming, H. Paul Williams, that has a set of classic problems whose solutions with Excel I'm publishing on my blog, sooner or later.

HTH,

Francesco

If you think your question has been answered, yes, please do mark the thread as solved.

I'll add only one thing: your model is of the integer (binary) linear kind, therefore much harder to solve compared to a continuous one.
OpenSolver has a very nice engine (there is a model in this forum with 210k bin vars!), but if your dataset is much bigger than your sample worksheet, you may need to set the Branch and Bound tolerance to higher values.

HTH,

Francesco