commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Paul Bouman (JIRA)" <>
Subject [jira] Updated: (MATH-390) Simplex Solver is very inaccurate on a large problem, even a very low value for epsilon
Date Tue, 20 Jul 2010 23:33:49 GMT


Paul Bouman updated MATH-390:


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:
>             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:,
> 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

This message is automatically generated by JIRA.
You can reply to this email to add a comment to the issue online.

View raw message