Example of supplier selection with discounts

I am working on a supplier selection model, so it is useful to see how my formulation compares to what others have come up with. The next paper is not really identical to my situation but it is useful to look at it anyway. (In my case I have more strange discount and incentive rules – it is amazing what sales people can come up with to make you buy their product – and we also want to look at procurement and administrative cost and at the impact of limiting the number of suppliers).

This model involves selecting carriers for shipping. The notation and data used is as follows:

We have i shipping companies to select from, and j transportation links we need to send goods along. Not every shipper handles all lanes. There is a simple discount schedule for each shipper: when we ship more than certain thresholds we get a discount on all shipments using this carrier. The model the paper proposes is:

This is a small, compact and simple model, but nevertheless there are many points we can make about this model:

1. The objective is missing an = sign after the ω. I.e. ω is not a weight on the first term in the objective but rather an objective variable. OK, no big deal, just a typo.
2. The second issue is more of a real modeling problem. I see this often: expressions are repeated in the model. In general this is bad idea. It is better to add variables and equations to the model so that we don’t have to repeat whole expressions. This can save a lot of non-zero elements in the model and make the model sparser. Even though we add variables and equations to the model, usually this is a worthwhile reformulation.
3. Big M values in the model are always a problem. Especially as stated like this: one value M for all cases. We need to choose tight values for these. I see many models with large big M values causing problems for MIP solvers. In the first case we can use an alternative formulation which is even simpler:
   
   Note that we replaced the sum by a new variable y.
4. This one can also be reformulated by introducing a parameter γ_i,k (gamma) indicating the upper bound of the discount interval. Of course we have γ_i,k=β_i,k+1. The inequality can now become:
    
   It is interesting to verify why the original version worked. It just looks at the lower bound of each interval. It is relying on discounts to increase when we move to a higher discount interval. The objective will then select the best interval. In my reformulated version we don’t rely on the objective but rather force the z to indicate the interval. In my formulation for a given z we will never be outside the corresponding interval. See also: http://yetanothermathprogrammingconsultant.blogspot.com/2015/10/discontinuous-piecewise-linear.html.
5. This equation fixes a lot of variables to zero. Besides writing this as a bound instead of an equation, we can actually make sure we never generate those inadmissible assignments. Solvers have very good presolvers that will remove these kind of equations, but in general I prefer to do this myself. I am always worried if the presolver is reducing my model by a large amount. Of course this is not always a modeling problem: if the model has a large triangular structure, we may see that the presolver takes a big bite out the model.
6. This is an interesting way to force some risk adjustment: we don’t want a single shipper to be the only and dominant shipper over a given lane. Therefore it can not handle more than q*100% of the shipments over a link. In practice one would want to see what the trade-offs are between cost and this risk measure.

The authors claim the MIP formulation does not solve fast enough for large instances so they developed a heuristic. I was able with some reformulations and some tinkering to solve the large instances within a few minutes to a 1% gap. Current MIP solvers are very good in finding good solutions very quickly. MIP solvers also have the unique capability to establish the quality of a solution (the gap). Note that this gap is often somewhat conservative. When we stop on a 1% gap, most likely we are much closer to the optimal solution than this 1% (but not guaranteed).

There are sometimes very good reasons to use heuristics. However I believe in quite a few cases developers prematurely dismiss MIP models, sometimes based on poorly formulated models.