Auxiliary Codes¶

This collection contains the code snippets referred to in the work¶

[1] E. Iurlano, G.R. Raidl. Complexity of Positive Influence Domination on Partial Grids (submitted).¶

In [1]:
using JuMP, HiGHS # Integer Linear Programming solving
using Graphs

function gen_complete_grid(m::Int, n::Int)
    g = SimpleGraph(m * n)
    for i in 0:m-1
        for j in 0:n-2
            add_edge!(g, i * n + j + 1, i * n + j + 2)
            add_edge!(g, (i + 1) * n + j + 1, i * n + j + 1)
        end
        add_edge!(g, (i + 1) * n + n - 1 + 1, i * n + n - 1 + 1)
    end
    return g
end

"""
Builds the ILP for calculating the optimal Positive Influence Domination number in a generalized manner.
If `alpha=0.5` we get the Pos. Infl. Dom. Problem, otherwise if `alpha>999`, the model represents `alpha/1000`-total domination, e.g., 2-total domination for `alpha=2000`.
"""
function gen_posinfluencedom_model!(model::Model, g::Graph, alpha::Float64)
    @variable(model, f[i in vertices(g)], Bin)
    @objective(model, Min, sum(f[i] for i in vertices(g))) # We want to minimize the amount of selected nodes
    for i in vertices(g)
        d_i = degree(g, i)
        if alpha > 999.0 # double total domination in case lhs = 2000.0
            @constraint(model, sum(f[j] for j in neighbors(g, i)) >= div(alpha, 1000))
        else
            @constraint(model, sum(f[j] for j in neighbors(g, i)) >= ceil(Integer, alpha * d_i))
        end
    end
    return [f] # provide the set of introduced variables
end


function gen_inductive_proof_model!(model::Model, g::SimpleGraph, dict_boundary_assumpt, alpha)
    @variable(model, f[i in vertices(g)], Bin)
    @objective(model, Min, sum(f[i] for i in [el for el in vertices(g) if !(el in collect(keys(dict_boundary_assumpt)))])) # We want to minimize the amount of selected nodes, outside of the constantly-fixed values for f(.)

    for i in [el for el in vertices(g) if !(el in sort(collect(keys(dict_boundary_assumpt)))[2:2:end])]
        d_i = degree(g, i)
        if alpha > 999.0 # e.g., for modeling double total domination
            @constraint(model, sum(f[j] for j in neighbors(g, i)) >= div(round(Integer, alpha), 1000))
        else
            @constraint(model, sum(f[j] for j in neighbors(g, i)) >= ceil(Integer, alpha * d_i))
        end
    end

    for (key, el) in dict_boundary_assumpt
        @constraint(model, f[key] == el)
    end
    return [f]
end

function calc_posinfluencedom_opt_exactly(g::SimpleGraph, alpha, TL) # timelimit TL
    model = Model(HiGHS.Optimizer)
    Highs_resetGlobalScheduler(1)
    set_attribute(model, MOI.NumberOfThreads(), 1)
    TL > 0 && set_time_limit_sec(model, TL)
    set_silent(model)

    variables = gen_posinfluencedom_model!(model, g, alpha)
    optimize!(model)
    
    optimality =  termination_status(model) == MOI.OPTIMAL ? true : false
    summary = solution_summary(model)
    
    solve_time_from_gurobi = solve_time(model)

    colvec = BitArray(undef, nv(g))
    colvec .= round.(Int, value.(variables[1]))
    @assert optimality "Optimality is a necessity for the current purpose!"
    @assert sum(colvec) == summary.objective_value "Solution must be consistent with upper bound!"
    return (colvec, optimality, summary.objective_value, solve_time_from_gurobi)
end

function candidate_PID_number_1_by_n_grid(n)
    return 2*div(n,4) + minimum([n%4,2])
    #
    #11001100110011001100 (n % 4 == 0)
    
    # ...
end

function candidate_PID_number_2_by_n_grid(n) 
    return 4*div(n,3)+ abs((n%3)-1)-abs((n%3)-2)+1
    #
    #011011011011011011 (n % 3 == 0)
    #011011011011011011
    
    #0110110110110110110 (n % 3 == 1)
    #0110110110110110110
    
    #01101101101101101101 (n % 3 == 2)
    #01101101101101101101
    
    
end
    
function candidate_PID_number_3_by_n_grid(n) 
    return 2*n-(n%2)
    # Adapted from paper Bermudo et al. 2019:
    #
    #1111111111111111 (n % 2 == 0)
    #0000000000000000
    #1111111111111111
    
    #01110111011101110 (n % 4 == 1)
    #01010101010101010
    #11011101110111011
    
    #0111011101110111011 (n % 4 == 3)
    #0101010101010101010
    #1101110111011101110
end
    
function candidate_PID_number_4_by_n_grid(n)
    return div(12*n + 8 - 2*((n-1)%5), 5)
    # Feasible solutions of above specified weight
    # can be found in the subsequent illustration.
end
Out[1]:
candidate_PID_number_4_by_n_grid (generic function with 1 method)

Figure for $m=4$¶

Periodic labeling schemes for $\gamma_{\operatorname{PID}}$ on $P_4\square P_{n}$ for $n\equiv0,1,2,3,4\pmod{5}$. Black vertices indicate an assigned $1$-label, white ones a $0$-label.

In [2]:
using Images, IJulia; img = load("optimal_sketch_four_by_n_grid.pdf"); IJulia.display(img)
In [3]:
function verify_PID_number_mprime_times_n(mprime,alpha)
    for n in 2:20         
        g = gen_complete_grid(mprime, n)
        colvec, optimality, primal_bound_val, solve_time_from_gurobi = calc_posinfluencedom_opt_exactly(g, alpha, 3600)
        formula_specified = -1
        if mprime == 1
            formula_specified = candidate_PID_number_1_by_n_grid(n)
        elseif mprime == 2
            formula_specified = candidate_PID_number_2_by_n_grid(n)
        elseif mprime == 3
            formula_specified = candidate_PID_number_3_by_n_grid(n)
        elseif mprime == 4
            formula_specified = candidate_PID_number_4_by_n_grid(n)
        end
        println("The $(mprime)x$n grid: ILP-optimum=$(Int(primal_bound_val)); postulated formula=$(formula_specified) ||| (n,primal,formulabound)=($n,$(Int(primal_bound_val)),$formula_specified)")
    end
end
Out[3]:
verify_PID_number_mprime_times_n (generic function with 1 method)
In [4]:
verify_PID_number_mprime_times_n(1, 0.5)

The 1x2 grid: ILP-optimum=2; postulated formula=2 ||| (n,primal,formulabound)=(2,2,2)
The 1x3 grid: ILP-optimum=2; postulated formula=2 ||| (n,primal,formulabound)=(3,2,2)
The 1x4 grid: ILP-optimum=2; postulated formula=2 ||| (n,primal,formulabound)=(4,2,2)
The 1x5 grid: ILP-optimum=3; postulated formula=3 ||| (n,primal,formulabound)=(5,3,3)
The 1x6 grid: ILP-optimum=4; postulated formula=4 ||| (n,primal,formulabound)=(6,4,4)
The 1x7 grid: ILP-optimum=4; postulated formula=4 ||| (n,primal,formulabound)=(7,4,4)
The 1x8 grid: ILP-optimum=4; postulated formula=4 ||| (n,primal,formulabound)=(8,4,4)
The 1x9 grid: ILP-optimum=5; postulated formula=5 ||| (n,primal,formulabound)=(9,5,5)
The 1x10 grid: ILP-optimum=6; postulated formula=6 ||| (n,primal,formulabound)=(10,6,6)
The 1x11 grid: ILP-optimum=6; postulated formula=6 ||| (n,primal,formulabound)=(11,6,6)
The 1x12 grid: ILP-optimum=6; postulated formula=6 ||| (n,primal,formulabound)=(12,6,6)
The 1x13 grid: ILP-optimum=7; postulated formula=7 ||| (n,primal,formulabound)=(13,7,7)
The 1x14 grid: ILP-optimum=8; postulated formula=8 ||| (n,primal,formulabound)=(14,8,8)
The 1x15 grid: ILP-optimum=8; postulated formula=8 ||| (n,primal,formulabound)=(15,8,8)
The 1x16 grid: ILP-optimum=8; postulated formula=8 ||| (n,primal,formulabound)=(16,8,8)
The 1x17 grid: ILP-optimum=9; postulated formula=9 ||| (n,primal,formulabound)=(17,9,9)
The 1x18 grid: ILP-optimum=10; postulated formula=10 ||| (n,primal,formulabound)=(18,10,10)
The 1x19 grid: ILP-optimum=10; postulated formula=10 ||| (n,primal,formulabound)=(19,10,10)
The 1x20 grid: ILP-optimum=10; postulated formula=10 ||| (n,primal,formulabound)=(20,10,10)
In [5]:
verify_PID_number_mprime_times_n(2, 0.5)

The 2x2 grid: ILP-optimum=2; postulated formula=2 ||| (n,primal,formulabound)=(2,2,2)
The 2x3 grid: ILP-optimum=4; postulated formula=4 ||| (n,primal,formulabound)=(3,4,4)
The 2x4 grid: ILP-optimum=4; postulated formula=4 ||| (n,primal,formulabound)=(4,4,4)
The 2x5 grid: ILP-optimum=6; postulated formula=6 ||| (n,primal,formulabound)=(5,6,6)
The 2x6 grid: ILP-optimum=8; postulated formula=8 ||| (n,primal,formulabound)=(6,8,8)
The 2x7 grid: ILP-optimum=8; postulated formula=8 ||| (n,primal,formulabound)=(7,8,8)
The 2x8 grid: ILP-optimum=10; postulated formula=10 ||| (n,primal,formulabound)=(8,10,10)
The 2x9 grid: ILP-optimum=12; postulated formula=12 ||| (n,primal,formulabound)=(9,12,12)
The 2x10 grid: ILP-optimum=12; postulated formula=12 ||| (n,primal,formulabound)=(10,12,12)
The 2x11 grid: ILP-optimum=14; postulated formula=14 ||| (n,primal,formulabound)=(11,14,14)
The 2x12 grid: ILP-optimum=16; postulated formula=16 ||| (n,primal,formulabound)=(12,16,16)
The 2x13 grid: ILP-optimum=16; postulated formula=16 ||| (n,primal,formulabound)=(13,16,16)
The 2x14 grid: ILP-optimum=18; postulated formula=18 ||| (n,primal,formulabound)=(14,18,18)
The 2x15 grid: ILP-optimum=20; postulated formula=20 ||| (n,primal,formulabound)=(15,20,20)
The 2x16 grid: ILP-optimum=20; postulated formula=20 ||| (n,primal,formulabound)=(16,20,20)
The 2x17 grid: ILP-optimum=22; postulated formula=22 ||| (n,primal,formulabound)=(17,22,22)
The 2x18 grid: ILP-optimum=24; postulated formula=24 ||| (n,primal,formulabound)=(18,24,24)
The 2x19 grid: ILP-optimum=24; postulated formula=24 ||| (n,primal,formulabound)=(19,24,24)
The 2x20 grid: ILP-optimum=26; postulated formula=26 ||| (n,primal,formulabound)=(20,26,26)
In [6]:
verify_PID_number_mprime_times_n(3, 0.5)

The 3x2 grid: ILP-optimum=4; postulated formula=4 ||| (n,primal,formulabound)=(2,4,4)
The 3x3 grid: ILP-optimum=5; postulated formula=5 ||| (n,primal,formulabound)=(3,5,5)
The 3x4 grid: ILP-optimum=8; postulated formula=8 ||| (n,primal,formulabound)=(4,8,8)
The 3x5 grid: ILP-optimum=9; postulated formula=9 ||| (n,primal,formulabound)=(5,9,9)
The 3x6 grid: ILP-optimum=12; postulated formula=12 ||| (n,primal,formulabound)=(6,12,12)
The 3x7 grid: ILP-optimum=13; postulated formula=13 ||| (n,primal,formulabound)=(7,13,13)
The 3x8 grid: ILP-optimum=16; postulated formula=16 ||| (n,primal,formulabound)=(8,16,16)
The 3x9 grid: ILP-optimum=17; postulated formula=17 ||| (n,primal,formulabound)=(9,17,17)
The 3x10 grid: ILP-optimum=20; postulated formula=20 ||| (n,primal,formulabound)=(10,20,20)
The 3x11 grid: ILP-optimum=21; postulated formula=21 ||| (n,primal,formulabound)=(11,21,21)
The 3x12 grid: ILP-optimum=24; postulated formula=24 ||| (n,primal,formulabound)=(12,24,24)
The 3x13 grid: ILP-optimum=25; postulated formula=25 ||| (n,primal,formulabound)=(13,25,25)
The 3x14 grid: ILP-optimum=28; postulated formula=28 ||| (n,primal,formulabound)=(14,28,28)
The 3x15 grid: ILP-optimum=29; postulated formula=29 ||| (n,primal,formulabound)=(15,29,29)
The 3x16 grid: ILP-optimum=32; postulated formula=32 ||| (n,primal,formulabound)=(16,32,32)
The 3x17 grid: ILP-optimum=33; postulated formula=33 ||| (n,primal,formulabound)=(17,33,33)
The 3x18 grid: ILP-optimum=36; postulated formula=36 ||| (n,primal,formulabound)=(18,36,36)
The 3x19 grid: ILP-optimum=37; postulated formula=37 ||| (n,primal,formulabound)=(19,37,37)
The 3x20 grid: ILP-optimum=40; postulated formula=40 ||| (n,primal,formulabound)=(20,40,40)
In [7]:
verify_PID_number_mprime_times_n(4, 0.5)

The 4x2 grid: ILP-optimum=4; postulated formula=6 ||| (n,primal,formulabound)=(2,4,6)
The 4x3 grid: ILP-optimum=8; postulated formula=8 ||| (n,primal,formulabound)=(3,8,8)
The 4x4 grid: ILP-optimum=10; postulated formula=10 ||| (n,primal,formulabound)=(4,10,10)
The 4x5 grid: ILP-optimum=12; postulated formula=12 ||| (n,primal,formulabound)=(5,12,12)
The 4x6 grid: ILP-optimum=16; postulated formula=16 ||| (n,primal,formulabound)=(6,16,16)
The 4x7 grid: ILP-optimum=18; postulated formula=18 ||| (n,primal,formulabound)=(7,18,18)
The 4x8 grid: ILP-optimum=20; postulated formula=20 ||| (n,primal,formulabound)=(8,20,20)
The 4x9 grid: ILP-optimum=22; postulated formula=22 ||| (n,primal,formulabound)=(9,22,22)
The 4x10 grid: ILP-optimum=24; postulated formula=24 ||| (n,primal,formulabound)=(10,24,24)
The 4x11 grid: ILP-optimum=28; postulated formula=28 ||| (n,primal,formulabound)=(11,28,28)
The 4x12 grid: ILP-optimum=30; postulated formula=30 ||| (n,primal,formulabound)=(12,30,30)
The 4x13 grid: ILP-optimum=32; postulated formula=32 ||| (n,primal,formulabound)=(13,32,32)
The 4x14 grid: ILP-optimum=34; postulated formula=34 ||| (n,primal,formulabound)=(14,34,34)
The 4x15 grid: ILP-optimum=36; postulated formula=36 ||| (n,primal,formulabound)=(15,36,36)
The 4x16 grid: ILP-optimum=40; postulated formula=40 ||| (n,primal,formulabound)=(16,40,40)
The 4x17 grid: ILP-optimum=42; postulated formula=42 ||| (n,primal,formulabound)=(17,42,42)
The 4x18 grid: ILP-optimum=44; postulated formula=44 ||| (n,primal,formulabound)=(18,44,44)
The 4x19 grid: ILP-optimum=46; postulated formula=46 ||| (n,primal,formulabound)=(19,46,46)
The 4x20 grid: ILP-optimum=48; postulated formula=48 ||| (n,primal,formulabound)=(20,48,48)
In [8]:
function proof(m, alpha, TL, dict_boundary_assumpt, dict_boundary_assumpt2)
    ########################################
    # Optimum on the long grid:
    ########################################

    model = Model(HiGHS.Optimizer)
    Highs_resetGlobalScheduler(1)
    set_attribute(model, MOI.NumberOfThreads(), 1)
    TL > 0 && set_time_limit_sec(model, TL)
    set_silent(model)
    
    if m == 1
        g = gen_complete_grid(1, 10)
    elseif m == 2
        g = gen_complete_grid(2, 8)
    elseif m == 3
        g = gen_complete_grid(3, 8)
    elseif m == 4
        g = gen_complete_grid(4, 12)
    end

    variables = gen_inductive_proof_model!(model, g, dict_boundary_assumpt, alpha)
    optimize!(model)
    primal_bound_val = objective_value(model)
    dual_bound_val = dual_objective_value(model)
    relative_gap_val = relative_gap(model)
    solve_time_from_gurobi = solve_time(model)
    status = termination_status(model)
    if status == MOI.INFEASIBLE
        if m == 1
            primal_bound_val = -2 # fictive value
        elseif m == 2
            primal_bound_val = -4 # fictive value
        elseif m == 3
            primal_bound_val = -4 # fictive value
        elseif m == 4
            primal_bound_val = -12 # fictive value
        end
    end

    colvec = BitArray(undef, nv(g))
    if status != MOI.INFEASIBLE
        colvec .= round.(Int, value.(variables[1]))
    end
    
    ########################################
    # Optimum on the shortened grid:
    ########################################

    model2 = Model(HiGHS.Optimizer)
    Highs_resetGlobalScheduler(1)
    set_attribute(model2, MOI.NumberOfThreads(), 1)
    TL > 0 && set_time_limit_sec(model2, TL)
    set_silent(model2)

    if m == 1
        g2 = gen_complete_grid(1, 6)
    elseif m == 2
        g2 = gen_complete_grid(2, 5)
    elseif m == 3
        g2 = gen_complete_grid(3, 6)
    elseif m == 4
        g2 = gen_complete_grid(4, 7)
    end

    variables2 = gen_inductive_proof_model!(model2, g2, dict_boundary_assumpt2, alpha)
    optimize!(model2)
    primal_bound_val2 = objective_value(model2)
    dual_bound_val2 = dual_objective_value(model2)
    relative_gap_val2 = relative_gap(model2)
    solve_time_from_gurobi2 = solve_time(model2)
    status2 = termination_status(model2)
    if status2 == MOI.INFEASIBLE
        if m == 1
            primal_bound_val2 = -4
        elseif m == 2
            primal_bound_val2 = -8
        elseif m == 3
            primal_bound_val2 = -8
        elseif m == 4
            primal_bound_val2 = -24
        end
    end

    colvec2 = BitArray(undef, nv(g2))
    if status != MOI.INFEASIBLE
        colvec2 .= round.(Int, value.(variables2[1]))
    end

    @show(primal_bound_val - primal_bound_val2)
end

function fullproof(m)
    P = []
    if m == 1
        Base.Cartesian.@nloops 2 prefix _ -> 0:1 begin
            push!(P, [Int(el) for el in Base.Cartesian.@ntuple 2 prefix])
        end
    elseif m == 2
        Base.Cartesian.@nloops 4 prefix _ -> 0:1 begin
            push!(P, [Int(el) for el in Base.Cartesian.@ntuple 4 prefix])
        end
    elseif m == 3
        Base.Cartesian.@nloops 6 prefix _ -> 0:1 begin
            push!(P, [Int(el) for el in Base.Cartesian.@ntuple 6 prefix])
        end
    elseif m == 4
        Base.Cartesian.@nloops 8 prefix _ -> 0:1 begin
            push!(P, [Int(el) for el in Base.Cartesian.@ntuple 8 prefix])
        end
    end
    sort!(P)
    alpha = 0.5
    #alpha = 2000.0 # this parameter would address double domination
    for p in P[1:end]
        # The keys of the dict-entries represent positions in the grid as number, see `gen_complete_grid` where vertices are enumerate row-wise from left to right.
        # The values of dict-entries represent assigned labels to the respective position.
        if m == 1
            proof(1, alpha, 3600, Dict([(9, p[1]), (10, p[2])]), Dict([(5, p[1]), (6, p[2])]))
        elseif m == 2
            proof(2, alpha, 3600, Dict([(7, p[1]), (8, p[2]), (15, p[3]), (16, p[4])]), Dict([(4, p[1]), (5, p[2]), (9, p[3]), (10, p[4])]))
        elseif m == 3
            proof(3, alpha, 3600, Dict([(7, p[1]), (8, p[2]), (15, p[3]), (16, p[4]), (23, p[5]), (24, p[6])]), Dict([(5, p[1]), (6, p[2]), (11, p[3]), (12, p[4]), (17, p[5]), (18, p[6])]))
        elseif m == 4
            proof(4, alpha, 3600, Dict([(11, p[1]), (12, p[2]), (23, p[3]), (24, p[4]), (35, p[5]), (36, p[6]), (47, p[7]), (48, p[8])]), Dict([(6, p[1]), (7, p[2]), (13, p[3]), (14, p[4]), (20, p[5]), (21, p[6]), (27, p[7]), (28, p[8])]))
        end
    end
end
Out[8]:
fullproof (generic function with 1 method)

We give a computer-aided proof of Lemma 4; needed to show Proposition 1 ($m=4$). Below numbers printed as floats represent true differences between optima; integers represent artificially introduced differences in case the boundary conditions were already infeasible (hence ex falso quodlibet).¶

In [9]:
fullproof(4) # m=4

primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0
primal_bound_val - primal_bound_val2 = 12.0

The same can be done for proving respective lemmas needed to show Proposition 3 ($m\in\{1,2,3\}$)¶

In [10]:
fullproof(1) # m=1

primal_bound_val - primal_bound_val2 = 2.0
primal_bound_val - primal_bound_val2 = 2.0
primal_bound_val - primal_bound_val2 = 2.0
primal_bound_val - primal_bound_val2 = 2.0
In [11]:
fullproof(2) # m=2

primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
In [12]:
fullproof(3) # m=3

primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
primal_bound_val - primal_bound_val2 = 4.0
In [ ]: