commons-issues mailing list archives

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

                 Key: MATH-390
             Project: Commons Math
          Issue Type: Bug
    Affects Versions: 2.1
         Environment: Windows Vista Enterprise
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)

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.

View raw message