Ttdfjt

Within the subject of simulation I have found some literature on validation and verification (e.g. Sargent's paper). My question is, what techniques do you use to validate and verify your mathematical (optimization) models and their implementation?

Generally speaking, verification refers to evaluating the conformation of a system, product, or service with its intended requirements and design specifications. On the other hand, validation refers to evaluate how much that system, product, or service is in accordance with the customers' or stakeholders' expectations.

AFAIK, there is no concrete literature on verification and validation of optimization models. Over the years, I gathered some useful points and methods based on my own and other colleagues' experiences as well as what is mentioned in the literature.

Verification in Optimization:

Here, verification refers to the extent to which the model/solution method is performing in accordance with the initial modeling assumptions. Some useful methods are as follows:

• Double-check the mathematics/coding of your model/algorithm with the problem definition and assumptions to make sure everything is OK (i.e., no assumption is violated or left out of the model/algorithm).


• Check whether the solution provided by a solver or your implemented algorithm is sound and logical (e.g., it doesn't violate any constraint).


• Feed deliberately designed (either by hand or the solutions obtained from the experts or the real system) feasible and infeasible solutions to your model and solution method and see if it can confirm the feasibility/infeasibility of the provided solution.


• Fix some decision variables and/or change input data to see if the model/algorithm behavior changes. It's possible that the model is OK with some input data, but not with some others (this could either be due to the input data or the model itself).


• Compare the solutions provided by the model (obtained via a solver) and your implemented solution method to see if there is any concerning disparity.

Validation in Optimization:

Here, validation refers to the extent to which the model/algorithm is satisfying the expectations of the problem owner. Some useful methods are as follows:

• Compare your solution with the current solution in the system and see whether it can outperform the incumbent.


• Use standard problem instances and compare your results with the best-known solutions form the literature.


• 
  

  If there are no standard problem instances, create random ones (either according to the literature with some tweaks or completely from scratch), and then do one of the following:

  
  
  

  • Compare your algorithm with solutions obtained from solving the mathematical model using a solver.

  
  

  • Compare your model/algorithm with solutions obtained from the state-of-the-art models/algorithms.

  
  

  • Develop a lower/upper bound on the objective function (e.g., using linear programming relaxation or Lagrangian relaxation). This could also be useful when you have real-world data from the system but no previously implemented solution exists.

  
  

This is just to complement the answer that @Ehsan gave.

For both verification and validation, if possible, visualize your results. For example, if you are solving a routing problem, simply visualizing the resulting routes may provide great insights.

• Does the solution (routes) make sense?


• Are there constraints in the model that are violated and I had no idea about (assume you had no idea about subtour elimination and visualizing the routes may help you identify them)?


• Should I add more constraints that I was not considering, simply by looking at the results? Imagine you see a route that starts in FL, goes to NY and then CA. Maybe it doesn't violate any of your current constraints, but it's something you don't like to have.

Also, check this answer which shares a procedure for debugging an optimization code which can be very useful in your verification process.

For models being deployed in the "real world" (something that, as an academic, I have heard rumors about), one element of validation is to describe both the objective criteria and the constraints to the decision makers (in their language, not in algebraic terms) and see if they agree with you. Another is to run the model on historical inputs and see if the resulting solution makes sense to them. This is an opportunity for them to discover constraints they kinda sorta forgot to mention the first time around, or to modify the objective criterion.

Switching to verification, if the model parameterized by historical inputs is infeasible, then you have likely found a flaw in the model. If the model using historical data is feasible but either (a) the historical solution is not feasible or (b) the historical solution is better than the "optimal" solution, the model is likely wrong.

Kleijnen (1995) analyses various methods of model verification and validation (V&V). Quoting the abstract (with slight changes to formatting):

For verification it discusses

1. general good programming practice (such as modular programming),




2. checking intermediate simulation outputs through tracing and statistical testing per module,




3. statistical testing of final simulation outputs against analytical results, and




4. animation.

For validation it discusses

1. obtaining real-world data,




2. comparing simulated and real data through simple tests such as graphical, Schruben-Turing, and t-tests,




3. testing whether simulated and real responses are positively correlated and moreover have the same mean, using two new statistical procedures based on regression analysis,




4. sensitivity analysis based on design of experiments and regression analysis, and risk or uncertainty analysis based on Monte Carlo sampling, and




5. white versus black box simulation models.

Both verification and validation require good documentation, and are crucial parts of assessment, credibility, and accreditation.

_Reference

_{[1] Kleijnen, J. C. (1995). Verification and validation of simulation models. European Journal of Operational Research. 82(1):145-162. https://doi.org/10.1016/0377-2217(94)00016-6}

I really like the paper by Coffin and Saltzman (INFORMS JOC, 2000), which argues that we should be using much more rigorous statistical tests when we compare the performance of one algorithm/heuristic against another.

This is not exactly about validation (which I interpret as "checking correctness") but rather about comparison, so feel free to tell me if this answer is off-topic.