Knapsack Problem Optimization: LP Relaxation, Greedy, and Local Search Implementation

Knapsack Problem Solution Methods

This implementation demonstrates several methods for solving the Knapsack Problem, including Linear Programming (LP) relaxation, the Dantzig heuristic, the standard Greedy algorithm, and a Local Search approach (Exchange Problem).

1. Initialization and Data Loading

uses "mmsystem"

declarations
    n, cap: integer
    archivo_datos = "gen300_5.txt"
end-declarations

fopen(archivo_datos, F_INPUT)
readln(n)
readln(cap)

declarations
    objetos = 1..n
    p, w, candidato: array(objetos) of integer
    t1: real
    x: array(objetos) of mpvar
    xp: array(objetos) of integer
    g: array(objetos) of real
    sol: array(objetos) of integer
    zgreedy, carga, final: integer
    ind0: array(objetos) of integer
    ind1: array(objetos) of integer
end-declarations

forall(j in objetos) read(j, p(j), w(j))
fclose(F_INPUT)

writeln("n = ", n)
writeln("Archivo: ", archivo_datos)

2. Linear Programming (LP) Formulation

The objective function and constraints define the LP relaxation of the Knapsack Problem:

valor_total := sum(j in objetos) p(j) * x(j)
r1 := sum(j in objetos) w(j) * x(j) <= cap
forall(j in objetos) x(j) is_binary

3. Dantzig Heuristic (Linear Relaxation)

We maximize the LP relaxation and use the solution to derive a heuristic integer solution.

writeln("\nHeurística de Dantzig (Relajación Lineal)\n")
maximize(XPRS_LIN, valor_total)

! Loop that indicates index k
ind := 0
forall(j in objetos) do
    if(x(j).sol <> 0) then
        ind := ind + 1
        writeln(x(j).sol, " ", ind)
    end-if
end-do

forall(j in objetos) xp(j) := floor(x(j).sol)

zLP := getobjval
zdantzig := sum(j in objetos) p(j) * xp(j)

! For checking integer values of p(j) (Commented out)
! forall(j in objetos) do
!     write(" ", p(j), " ", j)
! end-do

writeln("zdantzig = ", zdantzig, " <= z <= floor(zLP) = ", floor(zLP))

4. Optimal Integer Solution

maximize(valor_total)
z := getobjval
writeln("\nValor óptimo entero, z = ", z)

5. Greedy Algorithm Implementation

The Greedy algorithm selects items based on the highest profit-to-weight ratio $g(j) = p(j)/w(j)$ until the capacity is reached.

! ALGORITMO GREEDY
t1 := gettime
writeln("\nMétodo Greedy")

forall(j in objetos) g(j) := p(j) / w(j)
forall(j in objetos) sol(j) := 0

carga := 0
ncand := 0

forall(j in objetos | carga + w(j) <= cap) do
    candidato(j) := 1
    ncand := ncand + 1
end-do

zgreedy := 0
final := 0

while(final = 0) do
    aux := -99.
    
    ! Find the best candidate item (jmax)
    forall(j in objetos | candidato(j) = 1) do
        if(g(j) > aux) then
            aux := g(j)
            jmax := j
        end-if
    end-do
    
    sol(jmax) := 1
    carga := carga + w(jmax)
    zgreedy := zgreedy + p(jmax)
    candidato(jmax) := 0
    ncand := ncand - 1
    
    ! Update candidates: remove items that no longer fit
    forall(j in objetos | candidato(j) = 1) do
        if(carga + w(j) > cap) then
            candidato(j) := 0
            ncand := ncand - 1
        end-if
    end-do
    
    if(ncand = 0) then
        final := 1
    end-if
end-do

writeln("Solución greedy z = ", zgreedy)
writeln("tiempo = ", gettime - t1)

6. Local Search (Exchange Problem)

A local search heuristic attempts to improve the current solution (starting from the Greedy result) by exchanging one item currently in the knapsack with one item currently out, provided the capacity constraint is maintained and the profit improves.

! BÚSQUEDA LOCAL (PROBLEMA DE INTERCAMBIOS)
tiempo := gettime
writeln("\nBúsqueda Local")

zheur := zgreedy
iter := 0
final := 0

while(final = 0) do
    mejor_max := -999
    iter := iter + 1
    
    forall(j, k in objetos | sol(j) = 0 and sol(k) = 1) do
        if(carga - w(k) + w(j) <= cap) then
            mejora := p(j) - p(k)
        end-if
        
        if(mejora > mejor_max) then
            mejor_max := mejora
            jmax := j
            kmax := k
        end-if
    end-do
    
    if(mejor_max <= 0) then
        final := 1 ! Maximum local reached
        writeln("Iteración ", iter, ", z = ", zheur)
    else
        sol(jmax) := 1
        sol(kmax) := 0
        carga := carga - w(kmax) + w(jmax)
        zheur := zheur + p(jmax) - p(kmax)
    end-if
end-do

end-model