Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've just finished writing a a linear programming problem solver which uses the simplex method. Now I would like to start optimizing my solver but before I can do this, I need a way of reliably testing it's performance.

What is a good algorithm for generating random linear programming problems of arbitrary size? If possible I would also like to be able to control whether a solution exists or not and I would like to ensure that the origin is a vertex on the simplex.

share|improve this question
add comment

1 Answer

If you want a given vector $v \in {\mathbb R}^n$ as a solution, take a random $m \times n$ matrix $A$, and choose a vector $b \in {\mathbb R}^m$ such that $b \ge A v$. Then the constraints can be $A x \le b$. Generically, if $m \ge n$ and $b - Av$ has at least $n$ zero entries, $v$ will be a basic solution.

If you want a problem that is unbounded, pick vectors $u$ and $v$ with $v \ne 0$. Take a random matrix $A$. For each $j$ such that $(Av)_j > 0$, multiply row $j$ of $A$ by $-1$, so you get a matrix $A$ with $A v \le 0$. Choose $b$ such that $b \ge A u$. Then $u + t v$ satisfies the constraints $Ax \le b$ for all $t \ge 0$. Take for the objective any vector $c \in {\mathbb R}^n$ such that $c^T v > 0$.

If you want a problem that is infeasible, take the dual of an unbounded problem.

share|improve this answer
1  
Any suggestions about what distribution to draw your random matrix from? –  littleO Nov 25 '12 at 9:45
1  
It's really up to you. I'd use independent elements, each with some convenient continuous distribution (maybe uniform on an interval, maybe normal). –  Robert Israel Nov 25 '12 at 19:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.