6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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