TP-recherche-operationnelle/TP2/test.jl

function readKnapInstance(filename)
    price = []
    weight = []
    capacity = -1
    open(filename) do f
        for i = 1:3
            tok = split(readline(f))
            if (tok[1] == "ListPrices=")
                for i = 2:(length(tok)-1)
                    push!(price, parse(Int64, tok[i]))
                end
            elseif (tok[1] == "ListWeights=")
                for i = 2:(length(tok)-1)
                    push!(weight, parse(Int64, tok[i]))
                end
            elseif (tok[1] == "Capacity=")
                capacity = parse(Int64, tok[2])
            else
                println("Unknown read :", tok)
            end
        end
    end
    return price, weight, capacity
end

function TestsSondabilite_relaxlin(x, price, weight, capacity, BestProfit, Bestsol, affich)
    TA, TO, TR = false, false, false

    if (!Constraints(x, weight, capacity)) # Test de faisabilite
        TA = true
        if affich
            println("TA\n")
        end

    elseif (Objective(x, price) <= BestProfit) # Test d'optimalite
        TO = true
        if affich
            println("TO\n")
        end

    elseif (AllDef(x)) # Test de resolution
        TR = true
        if affich
            println("TR : solution ", " de profit ", Objective(x, price), "\n")
        end
        if (Objective(x, price) >= BestProfit) # Le profit de la solution trouvée est meilleur que les autres
            if affich
                println("\t-> Cette solution a un meilleur profit.\n")
            end
            # On remplace la solution et le profit par les nouvelles valeurs
            Bestsol = x
            BestProfit = Objective(x, price)
        else
            if affich
                println("\t-> Cette solution est moins bonne.\n")
            end
        end

    elseif affich
        println("non sondable\n")
    end

    return TA, TO, TR, Bestsol, BestProfit
end

function SeparerNoeud_relaxlin(price, listvars, listvals)
    # Le noeud est non-sondable. Appliquer le critère de séparation pour le séparer en sous-noeuds 
    # Cas du noeud le plus à gauche
    # On sépare le noeud actuel en 2 sous-noeuds
    predX = pop!(listvars)
    nextX0 = copy(predX)
    nextX1 = copy(predX)

    # On initialise leurs valeurs à zéro
    val0 = 0
    val1 = 0

    # On fixe la nouvelle variable des deux sous-noeuds
    n = length(predX)
    for i = 1:n
        if predX[i] == -1
            # L'un a zéro
            nextX0[i] = 0
            # L'autre a un
            nextX1[i] = 1

            # On calcule leurs valeurs
            val0 = Objective(nextX0, price)
            val1 = Objective(nextX1, price)
            break
        end
    end

    # On ajoute les sous-noeuds a la pile des noeuds a explorer
    push!(listvars, nextX0)
    push!(listvars, nextX1)

    # On ajoute aussi leurs valeurs
    push!(listvals, val0)
    push!(listvals, val1)

    return listvars, listvals
end

function ExplorerAutreNoeud_relaxlin(listvars, listvals)
    # Le noeud est sondable, on l'enlève de la pile des noeuds à sonder

    stop = false
    if (length(listvars) > 1)
        # On passe au noeud suivant
        var = pop!(listvars)
        val = pop!(listvals)
    else
        # Il n'y a pas d'autre noeud
        stop = true
    end

    return listvars, listvals, stop
end

# Fonction objectif que l'on souhaite maximiser/minimiser (évalué dans le meilleur des cas)
Objective(x, price) =
    sum(
        if x[i] < 0
            price[i]
        else
            price[i] * x[i]
        end
        for i = 1:length(x)
    )

# Fonction permettant de vérfier toutes les contraintes du modèle (dans le meilleur des cas)
Constraints(x, weight, capacity) =
    sum(
        if x[i] < 0
            0
        else
            weight[i] * x[i]
        end
        for i = 1:length(x)
    ) <= capacity

# Fonction qui nous dis si toutes les variables de x sont fixées
function AllDef(x)
    for i = 1:length(x)
        if x[i] < 0
            return false
        end
    end
    return true
end

function SolveKnapInstance(filename)

    stop = false
    affich = true

    # Extraction des données
    price, weight, capacity = readKnapInstance(filename)

    tri = true
    if tri
        couples = zip(price, weight)
        couples = sort(collect(couples), by = x -> x[1] / x[2])
        unzip(a) = map(x->getfield.(a, x), fieldnames(eltype(a)))
        price, weight = unzip(couples)
    end

    expected = split(split(filename, "-")[2], ".")[1]
    nodes_nb = length(price)
    nodes_max = 2^nodes_nb

    if affich
        println("---", filename, "---")
        println("Capacity = ", capacity)
        println("Number of objects = ", nodes_nb)
        println("Expected optimal value = ", expected)
        println("Maximum number of nodes = ", nodes_max)
        println()
    end

    # Liste des variable pour naviguer de noeuds en noeuds
    listvars = []
    listvals = []
    listnodes = []

    # La meilleur solution et sa valeur
    BestProfit = -1
    LastBestProfit = -1
    Bestsol = []

    # Compter le nombre de noeud explorés
    current_node_number = 0

    # On ajoute le premier noeud à explorer (la racine)
    push!(listvars, [-1 for p in price])
    push!(listvals, Objective(last(listvars), price))
    push!(listnodes, 1)
    newnodeid = 2

    while (!stop)

        # Le noeud actuel
        x = last(listvars)

        if affich && LastBestProfit != BestProfit
            println("Node n°", current_node_number, ": \tBestProfit = ", BestProfit)
            LastBestProfit = BestProfit
        end

        # Test de sondabilité du noeud actuel
        #   -> On mets a jour la solution et sa valeur si besoin
        TA, TO, TR, Bestsol, BestProfit = TestsSondabilite_relaxlin(x, price, weight, capacity, BestProfit, Bestsol, false)

        is_node_sondable = TA || TO || TR
        if (!is_node_sondable)
            # Le noeud n'est pas sondable, on le sépare en 2 sous-noeuds
            listvars, listvals = SeparerNoeud_relaxlin(price, listvars, listvals)
            newnodeid += 2
        else
            # Le noeud est sondable, on passe au noeud suivant
            listvars, listvals, stop = ExplorerAutreNoeud_relaxlin(listvars, listvals)
        end

        current_node_number += 1
    end

    println("\n--------------------------------------------------")
    println("Expected optimal value = ", expected)
    println("Optimal value = ", BestProfit)
    println("Optimal x = ", Bestsol)
    println("Maximum number of nodes = ", nodes_max)
    println("Nodes explored = ", current_node_number)
    if parse(Int64, expected) == BestProfit
        return 0
    else
        return 1
    end

end

SolveKnapInstance(ARGS[1])