Generating random linear programming problems

Question

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.

Answer 1

If you want a given vector $v \in {\mathbb R}^n$ as a solution:

1. take a random $m \times n$ matrix $A$

2. choose a vector $b \in{\mathbb R}^m$ such that $b \ge A v$.

   You can generate b by taking $b=Av+\delta, \delta_i\ge0$

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

1. pick vectors $u$ and $v$ with $v \ne 0$.
2. 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$.
3. Choose $b$ such that $b \ge A u$. Then $u + t v$ satisfies the constraints $Ax \le b$ for all $t \ge 0$.
4. 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.