share/simplex/Tests/klee_minty.mac

   1 /*****************************************************************************
   2  *                                                                           *
   3  * ************************************************************************* *
   4  * ***                                                                   *** *
   5  * ***                         ~*~ SIMPLEX ~*~                           *** *
   6  * ***                                                                   *** *
   7  * ***               A simple implementation of the simplex              *** *
   8  * ***             algorithm for Linear Programming for Maxima.          *** *
   9  * ***                                                                   *** *
  10  * ***   This file provides function klee_minty, which produces a linear *** *
  11  * ***   program, which requires exponential time to solve using the     *** *
  12  * ***   standard simplex method with no scaling. This file is part of   *** *
  13  * ***   the simplex package for Maxima.                                 *** *
  14  * ***                                                                   *** *
  15  * ***                                                                   *** *
  16  * ***   Version: 1.0 (September 2004)                                   *** *
  17  * ***   Author:  Andrej Vodopivec <andrej.vodopivec@fmf.uni-lj.si>      *** *
  18  * ***                                                                   *** *
  19  * ************************************************************************* *
  20  *                                                                           *
  21  *****************************************************************************/
  22
  23 klee_minty(n) := block(
  24   [A, b, c],
  25   A : zeromatrix(n,2*n),
  26   for i:1 thru n do (
  27     for j:1 thru i-1 do
  28       A[i,j] : 2*10^(i-j),
  29     A[i,i] : 1,
  30     A[i,i+n] : 1
  31   ),
  32   b : makelist(100^i, i, 0, n-1),
  33   c : -makelist(10^(n-i), i, 1, n),
  34   for i:1 thru n do c : append(c, [0]),
  35   [A, b, c]
  36   )$