QA techniques for optimization problem coding

Question

I often spend much, much, more time QAing and debugging my code than I do actually writing the optimization problem or shaping my data. Are there any tools or techniques to make it easier? I am asking specifically about the challenges operations research adds to programming.

Here is an example: Let's say we wanted to solve a newsvendor problem with shortage costs. An initial optimization model may look like:

$$\max_{Q\geq 0} ~E(-cQ - e(d_i-Q)^+ +v(Q-d_i)^+ ) $$ where $Q$ is the order quantity, $d_i$ is the stochastic demand for each $i \in \{1,\ldots, N\}$, $c$ is the per-unit cost, $e$ is a shortage cost, and $v$ is a salvage value.

However, this has nonlinearities that we have to resolve. The linear model looks like:

$$\max_{Q\geq 0} ~E(-cQ - eS_i^{(1)} +vS_i^{(2)}) \\ \mbox{s.t.} ~ S_i^{(1)} > d-Q~~~~~\forall i \in \{1,\ldots, N\}~~~~~~~~~~ \\ S_i^{(2)} > Q-d~~~~~\forall i \in \{1,\ldots, N\}~~~~\\ S_i^{(1)}, S_i^{(2)} \geq 0~~~~\forall i \in \{1,\ldots, N\}.~~~$$

Even this may not be the final version though. Sometimes we might want to know details that are not easily available from the information in the optimal solution. In the past, I have sometimes added even more variables to see a particular slice of costs.

For a model this many steps from the original, I often find it slow to verify that I haven't mixed up inequalities or left something out. When I am using PuLP, I can inspect the lp model directly, but the slack variables can still make it confusing for practical-sized problems. Is there anything I'm missing in how to handle these two sources of OR-specific programming complexity?

Answer 1

The following suggestion is conjecture (I don't do it myself) and certainly not guaranteed to prevent all possible errors. Develop your initial model, run it against multiple scenarios, and store the scenarios (parameter values) and solutions. As you modify the model, be sure to retain previous model versions (perhaps using a version control system, perhaps just by storing files).

Now suppose that you have an older version A and a newer version B, and suppose that B has a modified objective function but the same constraints as A. Plug into B the parameters from each test scenario from A (make up any new objective parameters), solve B, and confirm that the solution does at least as well on the new objective as the solution from A. Also substitute the solution from A into B, solve for the values of any new variables if necessary, and confirm that the A solution satisfies all constraints in B.

Now suppose instead that B has the same objective as A but different constraints. Again, run B against each scenario used to test A. Verify that the solution to A (expanded with any new variables) either does no better than the solution to B or is infeasible in B. For extra credit, if the A solution is infeasible in B, verify that it should be (i.e., that any constraint it violates is one that it should violate).

All this is a bunch of work, so you'll have to decide if it's worth the effort. It's basically my analog of what is known in coding circles as "unit testing".