Skip to content

Feasibility of CallbackVariablePrimal in LazyConstraintCallback #146

@blegat

Description

@blegat

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 ?

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions