In most cases that I've come up with an LP solution to a combinatorial optimization problem, I've mostly relied on "manual inspection" and discussion with peers to ascertain the correctness of the (I)LP. It has mostly been on a theoretical front. However, I've recently been involved with coding up an ILP with a rather large number of variables. My main concern is that although the ILP was well thought out, it seems there are quite a few lacunae that crop up. Every time I hope that I've "fixed" it some other sample problem seems to provide an incorrect asolution. My question is: How to go about "testing" the (I)LP for correctness? So far, I'm throwing some small/contained problems at it for which I know the solutions and see where it breaks down  i.e., compare the expected output to what we get and check which constraints are violated and fix the ILP in case the need be. This is rather cumbersome so I'm trying to "automate" the test cases after the manual inspection. Is there a recommended way of "testing" LPs? How does one approach this? I'm fairly well versed with testing software but this seems to be a different ground. There a few "cases" I can come up with but I'm not sure if I've left something out or are the cases themselves any good. Pointers? Clarification: I'm trying to validate whether my (I)LP models the real world problem correctly. I have an ILP already defined and am throwing some sample problems it to check for whether the "output" agrees with intuition and the expected output of the sample problem. I wish to know "how" to select these sample problems that would tell me with a high degree of confidence if my ILP works correctly. The assumption is that it models the reality correctly but I need to verify it by solving actual problems to know if I've missed something or overlooked some constraints or made some too tight etc., Basically, test it out with different problems and check the solutions, but want to know if the sample problems should be selected in a meaningful way and what that "way" is. asked 18 Aug '14, 04:18 PhD
showing 5 of 6
show 1 more comments

I'll answer with what I recall of the approaches used in simulation. First, we identify three distinct entities: the realworld system you are modeling (which I assume already exists and is in operation); your conceptual model (the mathematical formulation as you would present it in a slide show); and your coding of that model (in a modeling or programming language). Checking that the code matches the mathematical model is usually termed "verification". The only way I know to do that is to build a library of instances with known solutions. I recall two distinct methods for checking that the conceptual model adequate represents reality, known as "validation". "Historical validation" requires applying the model to historical instances for which decisions have already been made. What I would look for is that (a) the model considers the historical solution feasible (unless of course it wasn't) and (b) the model solution is at least as good as the historical solution. "Face validation" involves explaining the model assumptions (in nontechnical terms) to the people who best know the problem/system and see if they scoff at anything or identify some missing ingredient. answered 18 Aug '14, 16:27 Paul Rubin ♦♦ Unfortunately there is only ONE historical instance of the problem that is available. This is the first time the organization is wanting to integrate this into a production system, but they've never validated the model with reality. I'm creating artificial test problems, but don't know if they form a good 'set' for testing and wish to know if there is some of selecting/creating such a 'set'
(18 Aug '14, 16:40)
PhD

This is a tough question, and there are some great answers already, but let me add something simple. In its most basic form, there are only two steps:
A more thorough validation should guarantee, in a welldefined sense, that the instances on which you base your analysis are relevant, i.e., that they are plausible in your application. That is much harder to do, but there are data mining techniques you can use if you require that level of formalism. If you push this idea to the limit, you get Philipp's #3 answer, i.e., to use a simulation model to validate the solution. That is my favorite idea, if you can justify the extra effort in the context of your application. answered 18 Aug '14, 23:50 Leo 
The answer to this question is actually threefold:
I hope this helps. answered 18 Aug '14, 09:18 Philipp Chri... I think your answered another question than wht is asked. Indeed, the question contains this sentence: "Every time I hope that I've "fixed" it some other sample problem seems to provide an incorrect a solution". not the fact that there are several sample problems. It is why I interpreted the question as being about a solver for ILP problems.
(18 Aug '14, 11:52)
jfpuget
1
"Correctness" and "Incorrect solution" is not clarified, impossible to know what the real question is.
(18 Aug '14, 12:00)
Bo Jensen ♦

Thanks for the clarification, my other answer isn't much relevant. One way to address the problem of checking if your model is capturing the real system correctly is to design a graphical user interface (GUI) that shows the solutions of the models in a way that is familiar to operators. The GUI should be as close as possible to what people use today in production. It is our experience that this is the quickest way to get feedback on shortcomings of the model. A related point is that there should be a ramp up phase, where the model is run in the production system, but its results aren't actually used. However, results are displayed in the GUI for manual validation by operators. This way you get a set of test instances that you can reuse to validate your model each time you modify it. The goal of this ramp up phase is to capture missing constraints, and to identify those constraints that are too tight or irrelevant. The above assumes the optimization model will be used in a process that is mostly manual today, for instance operators defining a production schedule by hand. If you design a model for a new process, then you need to generate many instance problems, for instance using a simulation tool. You try to model the behavior of the system to optimize in the simulation tool, and record various runs of the simulator. You then feed these as test instances, and validate the results you obtain in each instance via the GUI mentioned above. Hope this helps. answered 19 Aug '14, 05:04 jfpuget 2
@Bo: We're OR geeks. We don't rate with gorgeous women, so pretty pictures are about the most we can hope for. :)
(19 Aug '14, 09:48)
Paul Rubin ♦♦

This is a hard question. What we do for CPLEX is to run it on a large (several thousands) of problems where we know the solution. We are adding models to that set on a regular basis, for instance when a customer reports a model where CPLEX does not find the right solution (quite rare), or when the running times are too long for the customer (more often). We have automated that testing, using a large computing farm. My advice is therefore to try to gather a set as large and diverse as possible of test problems on which you run your code. answered 18 Aug '14, 09:16 jfpuget Any specifc way of selecting those problems?
(18 Aug '14, 11:42)
PhD
We selected them by including publicly available problem sets, like MIPLIB. We also included all customer problems that seemed interesting for us. It could ber because they uncovered a bug, or because they uncovered some performance issues. We also include customer models that represent a class of problems that seem different from the ones we already have in our test suite. Our goal is to have a set as representative as possible of our users problems.
(18 Aug '14, 11:56)
jfpuget
Let me add that AFAIK our competitors do more or less the same.
(18 Aug '14, 11:57)
jfpuget

Basically you're asking "How can I ensure my model is valid for the real problem", right ? In the past there has been several cases of wrong models running in production for years, only to be proven to have flaws later, so you're not the first with this problem :) You can get a long way by having as many unit test problems as possible and doing auto sanity checks, but most often the model errors is found when the model is taken into use i.e when math solution meets real life.
crossposted
[Then removed, so link is dead. Ed.]
Please clarify if you mean validating the solution to the model or the model to the real problem. As you can see from the replies, it's not really clear what you mean.
or if it is about a solver correctness...
@BoJensen  Added clarification. Hopefully it helps. Please let me know though.
In that case I think Phillip has some good points in his section 3). Is it a model which is going to be deployed in real life or are you only trying to mimic the real life aspect ? In the latter case, I can only think of artificial unit test problems. For the first case it's often either possible to (hopefully) outperform an existing solution on offline historical data or simulation as Phillip suggest (which may or may not make this discussion recursive i.e is the simulated model correct.. :) )