[
https://issues.apache.org/jira/browse/MATH-390?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Paul Bouman updated MATH-390:
-----------------------------
Attachment: CorrectLPTestCase.java
The correct and more readable example, which actually works.
> 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
> Attachments: CorrectLPTestCase.java, LPTestCase.java
>
>
> 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.
