13
$\begingroup$

Typically OR-projects steps are: observing a situation, modeling it, solving the model, implementing the solution, and evaluating the situation.

In the area of production and logistics, the models are typically NP-hard combinatorial optimization problems. Typically, the contribution of these papers is to determine the complexity status of the problem and give a solution method with a small optimality gap. Some give some managerial insights based on the model. The focus is on the optimization and the steps that come after modeling and before the implementation of the solution.

But any optimization model also has a predictive element to it. (The prediction is if you take this solution, the objective value will be X and the solution will be implementable.)

Are there any studies on the predictive element of OR models? I would be especially interested in studies of the "implementation gap", i.e. the difference in cost predicted by the model and the real cost (or travel distance or ...).

I could so far not find any such studies, but I think such a study would be highly relevant:

The question of the gap between practice and theory is not new: e.g. Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling ask it in 1993.

There still seems to be a large gap with many models: e.g. for cross-docking, this study Cross-docking operations: Current research versus industry practice finds (in 2015):

But the cross-docking optimization literature evoked earlier seems somewhat disconnected from the actual industrial implementations of cross-docking".

There would probably be a considerable implementation gap if the model is "disconnected from the actual industrial implementations of cross-docking".

Assuming that literature reviews are somewhat representative of literature, we can look at: A ‘‘Meta survey’’ analysis in Operations Research and Management Science: A survey of literature reviews and find that "there is a fair concentration of topical coverage in the broad field of OR/MS, focusing on supply chain and logistics, sustainability, and scheduling". This therefore doesn't seem to be a small niche.

Obviously there is research in the more mathematical sense on strongly abstracted problems like the TSP, CVRP or the RCPSP. I also understand, that studying special cases, can lead to insights that might later be abstracted. However, most extensions of these models typically come with the claim, that it is "relevant for practice", yet I've never seen any inclusion of an "implementation gap".

(I'm aware of the informs journal of applied analytics, which does publish case studies, but even there I couldn't find anything on an "implementation gap").

My question: Is there any research on this "implementation gap". Is there maybe a different name/search term for it?

And why is it not always included anyway; some information on the quality of the model seem almost indispensable to me?

$\endgroup$
2
  • 1
    $\begingroup$ I think measuring the "implementation gap" is very difficult. The implementation gap depends on how "locally" you measure it, as there can be so many side-effects of an implemented solution, both positive and negative, that it becomes very hard to quantify where the effects come from. For example, optimizing routes might result in slightly longer routes than the model prescribed, but it might lead to higher customer satisfaction, as products arrive at the right time, which again increase sales. Does this mean that the implementation gap is positive or negative? $\endgroup$
    – Sune
    Dec 20, 2019 at 12:10
  • $\begingroup$ @Sune I agree, studying it isn't easy, however, any other field of economic studies deals with similar problems. I mean the entiere field of econometrics is about finding ways to interprete data. $\endgroup$
    – PSLP
    Dec 20, 2019 at 12:16

4 Answers 4

13
$\begingroup$

The implementation gap may not be a function of the "quality of the model" (or the algorithm used to solve it, which is a separate dimension). I had an experience with a logistics problem where the model was a simple shortest-path network model and the solution method was Dijkstra's shortest path algorithm. Both are time tested and thoroughly accepted. The implementation never happened, in part because the initial test was a dud. Why? The data used to parameterize the model, taken from a corporate database, was garbage. So there was a large implementation gap, but it was unrelated to the model (or algorithm).

$\endgroup$
2
  • $\begingroup$ So I might get better answers looking into robust optimization? $\endgroup$
    – PSLP
    Dec 20, 2019 at 11:09
  • 1
    $\begingroup$ I suppose it's possible, at least if you're restricting your attention to implementations where the data varies but is generally accurate. Robust optimization would not have made a difference in the case I mentioned. $\endgroup$
    – prubin
    Dec 21, 2019 at 15:03
10
$\begingroup$

You asked two questions at the end and I only try to answer the second "why is it [implementation gap] not always included anyway":

If I understand your question correctly, I'd say there can be many reasons why such an "implementation gap" that you refer to doesn't exist or reported. For example:

  • The academic studies are not necessarily implemented. Why? It can be due to the simplicity of the model's assumptions, the specificity of the assumptions (e.g. your study is on VRP with backhauls with no time windows but I have a case for simultaneous pickups and delivery with time windows), the complexity of the solution or implementation cost of the solution (e.g. Netflix never used its 1 million dollar code!), or that nobody knows about that study (among many other reasons).
  • Today's problems can be very different from tomorrow's. You may do research on a specific case study (thus, no such implementation gap) but by introducing even the smallest tweaks or additional constraints, the algorithms you have (and thus your solutions) don't work anymore (For example, you implement a great solution for a VRP where you pick from one central depot and you can deliver to a maximum of 4 warehouses and all of a sudden, I ask you for a small tweak of picking from more than one depot, i.e. multiple picks.) So, how do you measure the implementation gap here?
    • Bear in mind that I don't mean simple models are useless or "just for insight". On the contrary, they can serve as the minimum viable product (MVP) and that may do the job. Maybe you only need a feasible solution, something you don't currently have, and a model with simple assumptions provide that for you.
  • You also mentioned that this implementation gap is like the "predictive element" in an optimization model. But for a prediction, you have actual and predicted values. How do you know the actual values? Do you consider the status quo the actual (Whether manual solutions, the solutions from another tool, or solutions that are far from being optimal)? As I mentioned above, we can't expect that even the most relevant studies are implemented, so that to have a sense of the actual vs predicted values. So, when studies perform tests against the standard library of datasets and report their results, that, IMO, is the best that they can do.

And finally, in journals such as IJAA that you mentioned where case studies are published, presumably, those implementations gaps should not exist as the study is already implemented!

$\endgroup$
1
  • $\begingroup$ I feel like all these reasons are things that explain why it is hard, but not why including any measure on the quality of the model needn't be included. Most other fields of economics of extensive studies of emperical evidence (despite it being hard). $\endgroup$
    – PSLP
    Dec 20, 2019 at 11:12
4
$\begingroup$

In solving optimization problems, the gap is a relative concept. In the academic papers, the authors, have often used small instances to represent the model under study and usually, they could solve them optimality with a small gap.

Indeed, in the real-world problems (specifically, supply chain or scheduling) the problem is large, and the solution might be accepted with a relatively large gap. (separate from which kind of method, exact/heuristic, is used to solve the model.)

On the other hand, however, many practical works have not been published for commercial reasons that are hard to predict and compare the real and academic gap.

If you are interested, some useful references (real-world case study) could be found on the optimization software host like this or this.

$\endgroup$
2
  • $\begingroup$ I think the gap could be defined as the difference between the solution we computed and the solution that is implemented in practice (like the statistics on lateness for a train). $\endgroup$
    – PSLP
    Dec 20, 2019 at 11:13
  • 1
    $\begingroup$ @Luke599999, You are right. To complete, more times in the practical situation, you could (might) implement your model and after solving, you can use its solution directly. in this way, there is no difference in the gap. :) $\endgroup$
    – A.Omidi
    Dec 20, 2019 at 11:37
4
$\begingroup$

It's unlikely that you will find a generalised study on this, as the predictive power of an optimisation model depends on the accuracy of the data we use to build the model, and on the skill of the modeler themselves.

This is also compounded by the fact that the predictive power of a model is also dependent on the solver we use, in particular on whether the solver is able to close the optimality gap and get us close to the global solution which, in many cases, is the only solution of the model which corresponds to reality.

$\endgroup$

Your Answer

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

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