367 lines
13 KiB
Plaintext
367 lines
13 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"# TP 2-3 : Branch-and-bound applied to a knapsack problem"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"### Initialisation (à faire une seule fois)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"import Pkg; \n",
|
|
"Pkg.add(\"GraphRecipes\");\n",
|
|
"Pkg.add(\"Plots\"); \n",
|
|
"using GraphRecipes, Plots #only used to visualize the search tree at the end of the branch-and-bound"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"### Récupération des données"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"function readKnaptxtInstance(filename)\n",
|
|
" price=[]\n",
|
|
" weight=[]\n",
|
|
" KnapCap=[]\n",
|
|
" open(filename) do f\n",
|
|
" for i in 1:3\n",
|
|
" tok = split(readline(f))\n",
|
|
" if (tok[1] == \"ListPrices=\")\n",
|
|
" for i in 2:(length(tok)-1)\n",
|
|
" push!(price,parse(Int64, tok[i]))\n",
|
|
" end\n",
|
|
" elseif(tok[1] == \"ListWeights=\")\n",
|
|
" for i in 2:(length(tok)-1)\n",
|
|
" push!(weight,parse(Int64, tok[i]))\n",
|
|
" end\n",
|
|
" elseif(tok[1] == \"Capacity=\")\n",
|
|
" push!(KnapCap, parse(Int64, tok[2]))\n",
|
|
" else\n",
|
|
" println(\"Unknown read :\", tok)\n",
|
|
" end \n",
|
|
" end\n",
|
|
" end\n",
|
|
" capacity=KnapCap[1]\n",
|
|
" return price, weight, capacity\n",
|
|
"end"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"### Procédure d'application des tests de sondabilités TA, TO et TR pour le cas de la relaxation linéaire"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"function TestsSondabilite_relaxlin(model2, x, varsbin, BestProfit, Bestsol)\n",
|
|
" TA, TO, TR = false, false, false\n",
|
|
" if (termination_status(model2) == MOI.INFEASIBLE)#Test de faisabilite\n",
|
|
" TA=true\n",
|
|
" println(\"TA\")\n",
|
|
" elseif (objective_value(model2) <= BestProfit) #Test d'optimalite\n",
|
|
" TO=true\n",
|
|
" println(\"TO\")\n",
|
|
" elseif ( prod(abs.([round.(v, digits=0) for v in value.(varsbin)]-value.(varsbin)) .<= fill(10^-5, size(varsbin))) \n",
|
|
" ) #Test de resolution\n",
|
|
" TR=true\n",
|
|
" println(\"TR\")\n",
|
|
" #if (value(benef) >= BestProfit)\n",
|
|
" if (objective_value(model2) >= BestProfit)\n",
|
|
" Bestsol = value.(x)\n",
|
|
" #BestProfit=value(benef)\n",
|
|
" BestProfit=objective_value(model2)\n",
|
|
" end\n",
|
|
" else\n",
|
|
" println(\"non sondable\")\n",
|
|
" end\n",
|
|
" TA, TO, TR, Bestsol, BestProfit\n",
|
|
"end"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"### Procédure de séparation et stratégie d'exploration permettant de se placer au prochain noeud à traiter"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"\n",
|
|
"function SeparerNoeud_relaxlin(varsshouldbebinary, listvars, listvals)\n",
|
|
" # le noeud est non-sondable. Appliquer le critère de séparation pour le séparer en sous-noeuds \n",
|
|
" # et choisir un noeud-fils le plus à gauche \n",
|
|
" \n",
|
|
" #find a fractionnal variable\n",
|
|
" i, var = 1, 0\n",
|
|
" while ((i <= length(varsshouldbebinary)) && (var==0))\n",
|
|
" #if (varsshouldbebinary[i] ∉ listvars)\n",
|
|
" if (abs(round(value(varsshouldbebinary[i]), digits=0) - value(varsshouldbebinary[i]) ) >= 10^-5)\n",
|
|
" var=varsshouldbebinary[i]\n",
|
|
" end\n",
|
|
" i+=1\n",
|
|
" end\n",
|
|
" \n",
|
|
" #=\n",
|
|
" #find most fractionnal variable ?\n",
|
|
" i, var, maxfrac = -1, 0, 0.0\n",
|
|
" for i in 1:length(varsshouldbebinary)\n",
|
|
" if (abs(round(value(varsshouldbebinary[i]), digits=0) - value(varsshouldbebinary[i]) ) >= maxfrac) \n",
|
|
" #if a variable is more fractinonal\n",
|
|
" var=varsshouldbebinary[i]\n",
|
|
" maxfrac=abs(round(value(varsshouldbebinary[i]), digits=0) - value(varsshouldbebinary[i]) )\n",
|
|
" #println(i, \" \", var, \" \", maxfrac)\n",
|
|
" end\n",
|
|
" end\n",
|
|
" =#\n",
|
|
" \n",
|
|
"\n",
|
|
" set_lower_bound(var,1.0)\n",
|
|
" set_upper_bound(var,1.0)\n",
|
|
"\n",
|
|
" push!(listvars,var) #stocker l'identite de la variable choisie pour la séparation\n",
|
|
" push!(listvals,1.0) #stocker la branche choisie, identifiee par la valeur de la variable choisie\n",
|
|
" listvars, listvals\n",
|
|
"end\n",
|
|
"\n",
|
|
"\n",
|
|
"function ExplorerAutreNoeud_relaxlin(listvars, listvals, listnodes)\n",
|
|
" #this node is sondable, go back to parent node then right child if possible\n",
|
|
" \n",
|
|
" stop=false\n",
|
|
" #check if we are not at the root node\n",
|
|
" if (length(listvars)>= 1)\n",
|
|
" #go back to parent node\n",
|
|
" var=pop!(listvars)\n",
|
|
" theval=pop!(listvals)\n",
|
|
" tmp=pop!(listnodes)\n",
|
|
" set_lower_bound(var,0.0)\n",
|
|
" set_upper_bound(var,1.0)\n",
|
|
"\n",
|
|
" #go to right child if possible, otherwise go back to parent\n",
|
|
" while ( (theval==0.0) && (length(listvars)>= 1))\n",
|
|
" var=pop!(listvars)\n",
|
|
" theval=pop!(listvals)\n",
|
|
" tmp=pop!(listnodes)\n",
|
|
" set_lower_bound(var,0.0) \n",
|
|
" set_upper_bound(var,1.0)\n",
|
|
" end\n",
|
|
" if theval==1.0\n",
|
|
" set_lower_bound(var,0.0)\n",
|
|
" set_upper_bound(var,0.0)\n",
|
|
" push!(listvars,var)\n",
|
|
" push!(listvals,0.0)\n",
|
|
" else\n",
|
|
" println(\"\\nFINISHED\")\n",
|
|
" stop=true\n",
|
|
" end\n",
|
|
" else\n",
|
|
" #the root node was sondable\n",
|
|
" println(\"\\nFINISHED\")\n",
|
|
" stop=true\n",
|
|
" end\n",
|
|
" listvars, listvals, listnodes, stop \n",
|
|
"end"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"### Création de la relaxation linéaire (= modèle associé au noeud 0): <span style=\"color:red\"> SECTION A SUPPRIMER !!!! </span>\n",
|
|
"\n",
|
|
"<span style=\"color:red\"> Cette section est à commenter/supprimer et remplacer par vos propres calculs de bornes supérieures et autres, par exemple basées sur les bornes 1 et 2 vues en cours, ou d'autres calculs de bornes de votre choix/conception validés au préalable par votre encadrant/e de TP </span>"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"Pkg.add(\"Clp\");\n",
|
|
"using JuMP, Clp"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"function CreationModeleLP(price, weight, capacity)\n",
|
|
"# ROOT NODE\n",
|
|
" \n",
|
|
" model2 = Model(Clp.Optimizer) # set optimizer\n",
|
|
" set_optimizer_attribute(model2, \"LogLevel\", 0) #don't display anything during solve\n",
|
|
" set_optimizer_attribute(model2, \"Algorithm\", 4) #LP solver chosen is simplex\n",
|
|
"\n",
|
|
" # define x variables as CONTINUOUS (recall that it is not possible to define binary variables in Clp)\n",
|
|
" @variable(model2, 0 <= x[i in 1:4] <= 1)\n",
|
|
" varsshouldbebinary=[x[1] x[2] x[3] x[4]]\n",
|
|
"\n",
|
|
" # define objective function\n",
|
|
" @objective(model2, Max, sum(price[i]*x[i] for i in 1:4))\n",
|
|
"\n",
|
|
" # define the capacity constraint \n",
|
|
" @constraint(model2, sum(weight[i]*x[i] for i in 1:4) <= capacity)\n",
|
|
"\n",
|
|
" println(model2)\n",
|
|
"\n",
|
|
" return model2, x, varsshouldbebinary\n",
|
|
"end\n"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"### Boucle principale : résoudre la relaxation linéaire, appliquer les tests de sondabilité, identifier le prochain noeud, répéter."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"\n",
|
|
"function SolveKnapInstance(filename)\n",
|
|
"\n",
|
|
" if (split(filename,\"/\")[end] != \"test.opb\")\n",
|
|
" println(\"This version of the code works only for the test instance !!!!\")\n",
|
|
" else\n",
|
|
" price, weight, capacity = readKnaptxtInstance(filename)\n",
|
|
" model2, x, varsshouldbebinary = CreationModeleLP(price, weight, capacity)\n",
|
|
" \n",
|
|
" #create the structure to memorize the search tree for visualization at the end\n",
|
|
" trParentnodes=Int64[] #will store orig node of arc in search tree\n",
|
|
" trChildnodes=Int64[] #will store destination node of arc in search tree\n",
|
|
" trNamenodes=[] #will store names of nodes in search tree\n",
|
|
" \n",
|
|
" #intermediate structure to navigate in the search tree\n",
|
|
" listvars=[]\n",
|
|
" listvals=[]\n",
|
|
" listnodes=[]\n",
|
|
"\n",
|
|
" BestProfit=-1\n",
|
|
" Bestsol=[]\n",
|
|
"\n",
|
|
" current_node_number=0\n",
|
|
" stop = false\n",
|
|
"\n",
|
|
" while (!stop)\n",
|
|
"\n",
|
|
" println(\"\\nNode number \", current_node_number, \": \\n-----\\n\", model2)\n",
|
|
"\n",
|
|
" #Update the search tree\n",
|
|
" push!(trNamenodes,current_node_number+1) \n",
|
|
" if (length(trNamenodes)>=2)\n",
|
|
" push!(trParentnodes,listnodes[end]+1) # +1 because the 1st node is \"node 0\"\n",
|
|
" push!(trChildnodes, current_node_number+1) # +1 because the 1st node is \"node 0\"\n",
|
|
" end\n",
|
|
" push!(listnodes, current_node_number)\n",
|
|
"\n",
|
|
"\n",
|
|
" print(\"Solve model2 to compute the bounds of the current node: start ... \")\n",
|
|
" status = optimize!(model2)\n",
|
|
" println(\"... end\")\n",
|
|
"\n",
|
|
" print(\"\\nSolution relax lin\"); \n",
|
|
" if (termination_status(model2) == MOI.INFEASIBLE)#(has_values(model2))\n",
|
|
" print(\" : NOT AVAILABLE (probably infeasible or ressources limit reached)\")\n",
|
|
" else\n",
|
|
" [print(\"\\t\", name(v),\"=\",value(v)) for v in all_variables(model2)] \n",
|
|
" end\n",
|
|
" println(\" \"); println(\"\\nPrevious Solution memorized \", Bestsol, \" with bestprofit \", BestProfit, \"\\n\")\n",
|
|
"\n",
|
|
" TA, TO, TR, Bestsol, BestProfit = TestsSondabilite_relaxlin(model2, x, varsshouldbebinary, BestProfit, Bestsol)\n",
|
|
"\n",
|
|
" is_node_sondable = TA || TO || TR\n",
|
|
"\n",
|
|
" if (!is_node_sondable)\n",
|
|
" listvars, listvals = SeparerNoeud_relaxlin(varsshouldbebinary, listvars, listvals)\n",
|
|
" else\n",
|
|
" listvars, listvals, listnodes, stop = ExplorerAutreNoeud_relaxlin(listvars, listvals, listnodes)\n",
|
|
" end\n",
|
|
"\n",
|
|
" current_node_number = current_node_number + 1\n",
|
|
" end\n",
|
|
"\n",
|
|
" println(\"\\n******\\n\\nOptimal value = \", BestProfit, \"\\n\\nOptimal x=\", Bestsol)\n",
|
|
"\n",
|
|
" return BestProfit, Bestsol, trParentnodes, trChildnodes, trNamenodes\n",
|
|
" end\n",
|
|
"\n",
|
|
"end\n"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"### Affichage du résultat final"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"BestProfit, Bestsol, trParentnodes, trChildnodes, trNamenodes = SolveKnapInstance(\"data/test.opb\")\n",
|
|
"println(\"\\n******\\n\\nOptimal value = \", BestProfit, \"\\n\\nOptimal x=\", Bestsol)\n",
|
|
"graphplot(trParentnodes, trChildnodes, names=trNamenodes, method=:tree)\n",
|
|
"println(trParentnodes)\n",
|
|
"println(trChildnodes)\n",
|
|
"println(trNamenodes)"
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "Julia 1.6.3",
|
|
"language": "julia",
|
|
"name": "julia-1.6"
|
|
},
|
|
"language_info": {
|
|
"file_extension": ".jl",
|
|
"mimetype": "application/julia",
|
|
"name": "julia",
|
|
"version": "1.6.3"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 4
|
|
}
|