12
$\begingroup$

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?

$\endgroup$
8
  • 3
    $\begingroup$ Tell us in detail what kinds of problems you are trying to solve, then perhaps we can give concrete advice on tools which can address them in easy to formulate, modify, understandable, and low error-propensity way You may also have to decide whether you are willing to give up execution speed for ease of use and low error-propensity. $\endgroup$ Jun 25, 2019 at 20:43
  • $\begingroup$ I added some details from the most recent case. I think part of the answer is just that I work on fairly complex models so it takes time to get them right. $\endgroup$ Jun 25, 2019 at 21:21
  • $\begingroup$ You haven't addressed such things as whether the model boils down to a MILP, has nonlinearoitues, and if so, apart from integer restrictions, is it convex, etc. Which solvers you have used or would like to use, etc. $\endgroup$ Jun 25, 2019 at 21:58
  • $\begingroup$ Thanks for the guidance on what to add. Most of how I avoid errors is good naming conventions and lots of QA, so I was unsure how much of the challenge is specific to my problem. $\endgroup$ Jun 25, 2019 at 22:40
  • 1
    $\begingroup$ I would suggest to concretize the question to OR-specific problems along the suggestions of Mark. For discussing that complex models take more time to get them right, best naming conventions and the importance of (general) QA, you can probably get better answers on Stack Overflow. $\endgroup$ Jun 25, 2019 at 23:26

1 Answer 1

10
$\begingroup$

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".

$\endgroup$
3
  • $\begingroup$ I did something along these lines when adding an additional batch of variables strictly for reporting (saved some outputs before changing the model. Then confirmed my changes didn't impact the optimal decisions). Maybe it is indeed the best solution for that half of my question. $\endgroup$ Jun 26, 2019 at 21:40
  • 1
    $\begingroup$ The optimization analog of unit testing -- I like that a lot. $\endgroup$ Jun 26, 2019 at 23:06
  • 1
    $\begingroup$ This is "best practice" for building a test suite. Good post. $\endgroup$ Jun 27, 2019 at 0:07

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.