Simplex Solver is very inaccurate on a large problem, even a very low value for
epsilon
---------------------------------------------------------------------------------------
Key: MATH-390
URL: https://issues.apache.org/jira/browse/MATH-390
Project: Commons Math
Issue Type: Bug
Affects Versions: 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
Reporter: Paul Bouman
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).
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
