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's gravatar image

PhD
6317
accept rate: 0%

edited 18 Aug '14, 14:28

1

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.

(18 Aug '14, 04:28) Bo Jensen ♦
1

crossposted

[Then removed, so link is dead. --Ed.]

(18 Aug '14, 09:26) Austin Buchanan

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.

(18 Aug '14, 09:48) Bo Jensen ♦

or if it is about a solver correctness...

(18 Aug '14, 12:28) jfpuget

@BoJensen - Added clarification. Hopefully it helps. Please let me know though.

(18 Aug '14, 14:28) PhD

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.. :-) )

(18 Aug '14, 15:08) Bo Jensen ♦
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 real-world 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 non-technical terms) to the people who best know the problem/system and see if they scoff at anything or identify some missing ingredient.

link

answered 18 Aug '14, 16:27

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

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:

  1. Partition your model into Structural and Economic parts. The Structural part is the set of variables and constraints that define paths, connectivity, flow, logical implication, modeling tricks, etc. They define your search space. The Economic part is the set of variables and constraints that most directly measure tradeoffs. They represent activity levels, resource scarcity, etc. Focus your sensitivity analysis on the Economic subset of your model.
  2. From the inputs that affect the Economic subset of your model, select those which, in your application, are likely to be subject to the greatest variance. Insert some random noise into the data and chart the differences in solution structure as you crank up the synthetic variance. Can you explain the important changes in what the model recommends using terms from the application? Does normally distributed noise with small variance produce essentially the same solution structure? If you answered yes to both questions, your model is on the right track, and you have spent relatively little effort.

A more thorough validation should guarantee, in a well-defined 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.

link

answered 18 Aug '14, 23:50

Leo's gravatar image

Leo
1.1k17
accept rate: 8%

The answer to this question is actually three-fold:

  1. If you are talking about linear programming (LP, no integer variables), you can prove feasiblilty and optimality by providing a primal and a dual solution that are primal and dual feasible as well as satisfy complementarity (a simplex basis would also do). Something similar holds for infeasible or unbounded LPs (they can provide dual/primal rays). If you don't know what all this means, look it up in a text book on LP.

  2. If you have integer variables, in general there is no "short" proof of optimality, except for special cases. For example, if the LP relaxation of your problem (potentially after adding valid inequalities) is integer feasible, that solution is also optimal (and that can be checked like an LP). Obviously, feasibility of a solution can be checked realatively easily. And running the same (or different) solver software with different options and random seeds can also detect many wrong optimal conclusions, but beware of tolerances and gap parameters.

  3. If your problem is that you don't know if your model correctly represents the real world you have to verify your solutions in the real world or a simulation. It is sometimes possible to compute new solutions for things from the past and then verify that the solution would have worked as well or better as the real solution that was implemented. Simulation is also a great way to test that your solutions would be applicable in the real world and can point out problems with your modelling or you data.

I hope this helps.

link

answered 18 Aug '14, 09:18

Philipp%20Christophel's gravatar image

Philipp Chri...
1.0k27
accept rate: 22%

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.

link

answered 19 Aug '14, 05:04

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

3

Once again nice graphics always wins :-)

(19 Aug '14, 05:33) Bo Jensen ♦
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.

link

answered 18 Aug '14, 09:16

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×190
×28
×6
×2

Asked: 18 Aug '14, 04:18

Seen: 2,833 times

Last updated: 19 Aug '14, 09:48

OR-Exchange! Your site for questions, answers, and announcements about operations research.