Script to solve root relaxations of pure 0/1 miplib problems

process_and_solve.jl

# Copyright 2018 Google LLC.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

# Written using Julia 0.6.2 and JuMP 0.18
using JuMP, GLPK, GLPKMathProgInterface, MathProgBase

function read_mps(filename)
    @assert endswith(filename, ".mps.gz")
    m = MathProgBase.LinearQuadraticModel(GLPKSolverMIP(msg_lev=GLPK.MSG_OFF))
    MathProgBase.loadproblem!(m, filename)
    return MathProgBase.getvarLB(m), MathProgBase.getvarUB(m), MathProgBase.getconstrLB(m),
           MathProgBase.getconstrUB(m), MathProgBase.getvartype(m),
           MathProgBase.getconstrmatrix(m), MathProgBase.getobj(m)
end

is_pure_binary(x_lb, x_ub, variable_types) = all(x_lb .== 0.0) && all(x_ub .== 1.0) &&
       all(t -> t == :Bin || t == :Int, variable_types)

# Takes a set of constraints of the form "constr_lb <= A*x <= constr_ub"
# and transforms them into "A_eq = b_eq, A_ineq >= b_ineq".
# Assumes no two-sided constraints (i.e., 1 <= x + y <= 2).
function process_to_standard_form(constr_lb, constr_ub, A)
    A = copy(A)
    eq_rows = constr_lb .== constr_ub
    ge_rows = .!eq_rows .& isfinite.(constr_lb)
    le_rows = .!eq_rows .& isfinite.(constr_ub)
    @assert !any(ge_rows .& le_rows)
    A_ineq = vcat(A[ge_rows,:], -A[le_rows,:])
    b_ineq = vcat(constr_lb[ge_rows], -constr_ub[le_rows])
    return A[eq_rows, :], constr_lb[eq_rows], A_ineq, b_ineq
end

function solve_relaxed_pure_binary_glpk(constr_lb, constr_ub, A, obj_vector)
    A_eq, b_eq, A_ineq, b_ineq = process_to_standard_form(constr_lb, constr_ub, A)
    m = Model(solver=GLPKSolverLP())
    @variable(m, 0 <= x[1:size(A,2)] <= 1)
    @objective(m, Min, obj_vector'x) # All instances are minimization.
    @constraint(m, A_eq*x .== b_eq)
    @constraint(m, A_ineq*x .>= b_ineq)
    status = solve(m)
    return status, getobjectivevalue(m)
end

function solve_dual_relaxed_pure_binary_glpk(constr_lb, constr_ub, A, obj_vector)
    A_eq, b_eq, A_ineq, b_ineq = process_to_standard_form(constr_lb, constr_ub, A)
    m = Model(solver=GLPKSolverLP())
    @variable(m, λ[1:length(b_eq)])
    @variable(m, α[1:length(b_ineq)] ≥ 0)
    @variable(m, s[1:size(A,2)] ≥ 0)
    @objective(m, Max, λ'b_eq + α'b_ineq - sum(s))
    @constraint(m, A_eq'λ + A_ineq'α - s .≤ obj_vector)
    status = solve(m)
    return status, getobjectivevalue(m)
end

function solve_instances(pure_binary_instances)
    for name in pure_binary_instances
        file = joinpath(MIPLIB_PATH, name)
        var_lb, var_ub, constr_lb, constr_ub, var_types, A, obj_vector = read_mps(file)
        @assert is_pure_binary(var_lb, var_ub, var_types)
        @show name
        status, objective = solve_relaxed_pure_binary_glpk(constr_lb, constr_ub, A, obj_vector)
        @show status, objective
        status, objective = solve_dual_relaxed_pure_binary_glpk(constr_lb, constr_ub, A, obj_vector)
        @show status, objective
    end
end

const MIPLIB_PATH = "/home/mlubin/miplib2010-1.1.3/instances/miplib2010"

pure_binary_instances = ["acc-tight5.mps.gz",
"air04.mps.gz",
"ash608gpia-3col.mps.gz", "bab5.mps.gz", "bley_xl1.mps.gz", "bnatt350.mps.gz",
"cov1075.mps.gz", "eil33-2.mps.gz", "eilB101.mps.gz", "ex9.mps.gz",
"iis-100-0-cov.mps.gz", "iis-bupa-cov.mps.gz", "iis-pima-cov.mps.gz",
"m100n500k4r1.mps.gz", "macrophage.mps.gz", "mine-166-5.mps.gz",
"mine-90-10.mps.gz", "mspp16.mps.gz", "n3div36.mps.gz", "n3seq24.mps.gz",
"neos-1109824.mps.gz", "neos-1337307.mps.gz", "neos18.mps.gz",
"neos-849702.mps.gz", "netdiversion.mps.gz", "ns1688347.mps.gz",
"opm2-z7-s2.mps.gz", "reblock67.mps.gz", "rmine6.mps.gz", "sp98ic.mps.gz",
"tanglegram1.mps.gz", "tanglegram2.mps.gz", "vpphard.mps.gz"]

solve_instances(pure_binary_instances)