# Generating random linear programming problems

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.

-

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