Spot the bug: C# Simplex implementation

[NewsBot]

I've got a massivly important Desicion Math exam tomorrow morning, so to help me become familar with the Simplex method for solving Linear Programming problems I wrote a quick and dirty implementation in 15 minutes.

 

It works fine for the first three example problems I've hardcoded into the program, but it cannot solve the 4th problem. I can't see why though, since it follows the instructions in my textbook verbatim.

 

So... the first Spot the Bug competition of 2008.

 

Here's the code, and my apologies for using gotos and public fields.

 

 

using System;

using System.Text;

 

namespace Math.Simplex {

 

public class Program {

 

public static Int32 Main(string[] args) {

 

///////////////////////////

// Set up grid

///////////////////////////

 

SimplexGrid grid = new SimplexGrid();

 

String example;

 

if(args.Length != 1) {

INPUT_EXAMPLE:

Console.WriteLine("Select example to run: 1, 2, 3 or 4.");

example = Console.ReadLine();

Int32 dontCare;

if(!Int32.TryParse(example, out dontCare)) {

goto INPUT_EXAMPLE;

}

} else {

example = args[0];

}

 

switch(example) {

case "1":

 

grid.Rows = new SimplexGridRow[] {

// x, y, z, r, s, t, val , isObjective

new SimplexGridRow( new double[] { 12, 4, 5, 1, 0, 0, 246 }, false ),

new SimplexGridRow( new double[] { 9, 6, 3, 0, 1, 0, 153 }, false ),

new SimplexGridRow( new double[] { 5, 2, -2, 0, 0, 1, 171 }, false ),

new SimplexGridRow( new double[] { -2, -4, -3, 0, 0, 0, 0 }, true )

};

 

grid.ValueColIdx = 6;

 

break;

case "2":

 

grid.Rows = new SimplexGridRow[] {

// p.168 x, y, r, s, val , isObjective

new SimplexGridRow( new double[] { 3, 3, 1, 0, 120 }, false ),

new SimplexGridRow( new double[] { 2, 4, 0, 1, 150 }, false ),

new SimplexGridRow( new double[] { -10, -12, 0, 0, 0 }, true )

};

 

grid.ValueColIdx = 4;

 

break;

case "3":

 

grid.Rows = new SimplexGridRow[] {

// x, y, z, s, t, val , isObjective

new SimplexGridRow( new double[] { 2, 3, 4, 1, 0, 3 }, false ),

new SimplexGridRow( new double[] { 6, 6, 2, 0, 1, 8 }, false ),

new SimplexGridRow( new double[] { -8, -9, -5, 0, 0, 0 }, true )

};

 

grid.ValueColIdx = 5;

 

break;

case "4":

 

grid.Rows = new SimplexGridRow[] {

// p.176 #6 x, y, z, s, t, val , isObjective

new SimplexGridRow( new double[] { 1, 4, 2, 1, 0, 40 }, false ),

new SimplexGridRow( new double[] { 1, 0, 4, 0, 1, 8 }, false ),

new SimplexGridRow( new double[] { -1, -4, -10, 0, 0, 0 }, true )

};

 

grid.ValueColIdx = 5;

 

break;

default:

Console.WriteLine("Invalid example, go die in a fire");

return 1;

}

 

///////////////////////////

// Begin

///////////////////////////

int iterations = 1;

Console.WriteLine("Initial grid");

Console.WriteLine( grid.ToString() );

begin:

 

// find pivotal column, by the smallest objective row value

Double smallestObjectiveRowValue = 0;

Int32 smallestObjectiveRowValueIdx = -1;

 

SimplexGridRow objectiveRow = grid.Rows[ grid.ObjectiveRowIdx ];

 

foreach(Int32 col in objectiveRow.variables) {

if( col < smallestObjectiveRowValue ) {

smallestObjectiveRowValue = col;

smallestObjectiveRowValueIdx++;

}

}

if(smallestObjectiveRowValue == 0 && iterations == 0)

throw new Exception("No subzero objective row value");

else if(smallestObjectiveRowValue == 0) {

Console.WriteLine("Done");

Console.Read();

return 0;

}

 

// found it

grid.PivotColIdx = smallestObjectiveRowValueIdx;

 

// find theta values, and find the smallest, the row with the smallest theta becomes the pivot row

Double smallestThetaValue = Double.MaxValue;

for(int i=0;i