[MATH-390] Simplex Solver is very inaccurate on a large problem, even a very low value for epsilon

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 2.1

Environment

Windows Vista Enterprise
Runtime:
java version "1.6.0_20"
Java(TM) SE Runtime Environment (build 1.6.0_20-b02)
Java HotSpot(TM) Client VM (build 16.3-b01, mixed mode, sharing)

Compiler:
javac 1.6.0_13

• Assignee: Unassigned
• Reporter: Paul Bouman
• Created: 20/Jul/10 22:47
• Updated: 20/Jul/10 23:32
• Resolved: 20/Jul/10 23:32

Description

I'm currently playing with a program for solving a rather simple chess puzzle. The goal is to place 12 knights on a 8x8 board, such that each field is either attacked by a knight, or contains a knight. To solve this problem (and different variants) I want to use a handcrafted Branch and Bound algorithm that uses Linear Programming to calculate an upperbound on the number of fields that can be covered by a certain amount of knights.

The idea is to create variables for each field that has to be covered, and to create variables for each field to contain a knight. A cover variable can only become positive if a corresponding knight variable for an adjacent field is also positive, there is a limit to the amount of knights we may place (so the sum of all knight variables cannot be larger than 12) and the cover variables cannot be larger than one. Also, only the cover variables have a coefficient of one in the objective function, all other variables have zero. Because we want to cover the entire board our goal will be to maximize the objective function, since we want to maximize the number of fields that are covered.

Since a basic chessboard has 64 fields and since it is possible to cover the chessboard with 12 knights, we know there is an integer solution that has value 64. Since we are solving a relaxed variant of the problem, the value should be at least 64. However, when I use the Simplex Solver, I get a value of around 58.6, which is much too low. Even when I relax the constraints in such a fashion that 64 knights may be placed on the board, the solution value remains the same. I've lowered the value of epsilon as much as I can and it still gives the incorrect value. What makes it worse is that the calculation is totally useless as an upperbound (if the value would have been around 70, it would have been an upperbound at least).

I've heard that using the revised simplex method is a lot better with respect to stacked errors, so I am not sure this is really a bug, or just a problem that arises when the two phase simplex method is used for large problems.

I will try to attach a code example that implements the problem (but possibly isn't that readable).