jump-dev/GLPK.jl

Feasibility of CallbackVariablePrimal in LazyConstraintCallback

blegat opened this issue · 2 comments

In the doc, we say for LazyConstraintCallback:

The feasible primal solution is accessed through CallbackVariablePrimal.

which indicates that we can expect the variable primal values to be feasible.

In GLPK.jl, the LazyConstraintCallback is called when the reason is IROWGEN.
At page 123 of https://most.camden.rutgers.edu/glpk.pdf#a8, we can read

The callback routine is called with the reason code GLP_IROWGEN if LP relaxation of the current
subproblem has just been solved to optimality and its objective value is better than the best known
integer feasible solution

it's not clear there that it is feasible, it just says that it is feasible for the relaxation.
However, it then says

The callback routine is called with the reason code GLP_ICUTGEN if LP relaxation of the current
subproblem being solved to optimality is integer infeasible (i.e. values of some structural variables
of integer kind are fractional), though its objective value is better than the best known integer
feasible solution.

so it seems that if it is integer infeasible, it will rather use ICUTGEN than IROWGEN so the fact that ICUTGEN redirects to UserCutCallback and IROWGEN redirects to LazyConstraintCallback makes sense.
However, in this example:

import GLPK, MathOptInterface
const MOI = MathOptInterface
model = GLPK.Optimizer()
v = MOI.add_variables(model, 5)
fv = MOI.SingleVariable.(v)
for f in fv
    MOI.add_constraint(model, f, MOI.ZeroOne())
end
MOI.add_constraint(model, [2.0, 8.0, 4.0, 2.0, 5.0]'MOI.SingleVariable.(v), MOI.LessThan(10.0))
MOI.set(model, MOI.ObjectiveSense(), MOI.MAX_SENSE)
MOI.set(model, MOI.ObjectiveFunction{MOI.ScalarAffineFunction{Float64}}(), [5.0, 3.0, 2.0, 7.0, 4.0]'MOI.SingleVariable.(v))
function cb(cb_data)
    @show UInt8(GLPK.glp_ios_reason(cb_data.tree))
    @show MOI.get(model, MOI.CallbackVariablePrimal(cb_data), v)
end
MOI.set(model, GLPK.CallbackFunction(), cb)
MOI.optimize!(model)

we can see below that while it is integer infeasible, it still uses IROWGEN instead of ICUTGEN

UInt8(GLPK.glp_ios_reason(cb_data.tree)) = 0x06 # => GLP_ISELECT
MOI.get(model, MOI.CallbackVariablePrimal(cb_data), v) = [1.0, 0.0, 0.25, 1.0, 1.0]
UInt8(GLPK.glp_ios_reason(cb_data.tree)) = 0x07 # => GLP_IPREPRO
MOI.get(model, MOI.CallbackVariablePrimal(cb_data), v) = [1.0, 0.0, 0.25, 1.0, 1.0]
UInt8(GLPK.glp_ios_reason(cb_data.tree)) = 0x01 # => GLP_IROWGEN
MOI.get(model, MOI.CallbackVariablePrimal(cb_data), v) = [1.0, 0.0, 0.25, 1.0, 1.0]
UInt8(GLPK.glp_ios_reason(cb_data.tree)) = 0x03 # => GLP_IHEUR
MOI.get(model, MOI.CallbackVariablePrimal(cb_data), v) = [1.0, 0.0, 0.25, 1.0, 1.0]

Any idea what's happening ?

odow commented

Nope. But this doesn't seem like something to fix on our end. You could argue that at present it doesn't have a feasible integer solution, so the current subproblem has just been solved to optimality and its objective value is better than the best known integer feasible solution is true.

odow commented

Closing because there isn't anything to fix on the GLPK side.