Incorrect output from MIPSolverHL

[jmcarthur]

trafficstars

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]

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]

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]

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.