Can you generate random linear programming problems?

Question

I looked at Linear Programming, and it are problems like this:

You know that Cabinet X costs 10 cents per unit, requires 6 square feet of floor space, and holds 8 cubic feet of files. Cabinet Y costs 20 dollars per unit, requires 8 square feet of floor space, and holds 12 cubic feet of files.

You have been given 140 dollar for this purchase, though you don't have to spend that much. The office has room for no more than 72 square feet of cabinets.

How many of which model should you buy, in order to maximize storage volume?

But you notate them in special form, so that you can genericly describe many of such problems.

Now suppose I replace all the values in this problem (10, 6, 8, 20, 12, 140, 72) with random other numbers, so I randomly create a completely new problem.

• Do they take longer to solve, than to verify the solution?
• Can I check that they are solveable without solving them?
• Can I check how difficult they will be to solve, without solving them?

Answer 1

Sure, of course you can create random linear programming problems. Why not?

Yes, in general, you can usually verify the solution to a linear programming problem faster than you can find the solution. Verifying the solution just involves plugging into the equations and checking that all equations hold. Finding the solution requires a bit more work (e.g., the simplex method, interior point method, ellipsoid method, something else).

However, as you may know, linear programming problems can be solved in polynomial time, and solutions can be verified in polynomial time. Therefore, the difference between "time to solve" and "time to verify" is not as huge as for (say) NP-complete problems.

The best way to check that a linear programming problem is solvable is to solve it. If you want a slight improvement, you can simply test whether the constraints admit any feasible solution. The way you test feasibility is by omitting the objective function (or replacing it with a trivial objective function) and giving it to a LP solver; the solver will then tell you whether the linear program has a feasible solution or not. If it has a feasible solution, then it is solvable; if it doesn't have any feasible solution, it isn't solvable. In practice, testing for feasibility might be somewhat faster than solving it, for many problems. However, there are no guarantees. Based on theoretical work, we know that the worst-case running time to test for feasibility is approximately the same as the worst-case running time to find the optimal solution.

I know of no perfect way to test how difficult they will be to solve, other than solving it. In practice, though, linear programming solvers are so efficient that a problem of the sort you list (with half a dozen variables and a dozen or so constraints) will be solved almost instantaneously, no matter what values you use -- so there is no point in trying to figure out how difficult it will be to solve.