search

msakai / toysolver

My sandbox for experimenting with solver algorithms.
Other
154 stars 11 forks source link

Incorrect output from MIPSolverHL #5

Open jmcarthur opened 10 years ago

jmcarthur commented 10 years ago

Try the following program:

test :: OptResult Double
test =
  let a = var 1
      b = var 2
  in maximize (3*^a ^-^ b)
     [ Rel a Ge zeroV
     , Rel b Ge zeroV
     , Rel a Le (constant 1)
     , Rel (3*^b) Ge (4*^a)
     ]
     (IntSet.fromList [1,2])

The output is Optimum 0.0 (fromList [(1,0.0),(2,0.0)]). However, I expected Optimum 1.0 (fromList [(1,1.0),(2,2.0)]).

I am using the version on Hackage.

jmcarthur commented 10 years ago

I just discovered that I get the expected answer if I change constant 1 to constant 1.1. Perhaps this is a rounding error somewhere?

jmcarthur commented 10 years ago

I just realized that the issue (which I am now certain is due to rounding) is easily surmountable (at least in my case) by using Rational instead of Double. I will leave the ticket open, since I still believe this indicates a bug; after all, Double is a common instantiation for this sort of problem.

msakai commented 10 years ago

Thank you for reporting and sorry for the late reply. As you guessed, the problem is due to numerical error of floating point numbers.

After introducing a mixed integer Gomory cut and branching, the expected solution is excluded due to the slight violation of feasibility condition (non-negative variable took the value -5.551115123125783e-17).

To fix the problem, it is necessary to tolerate small amounts of violation and also add parameters for controlling the degree of tolerance, as all all practical MIP solvers do.