Violation Distribution (distr_V)

import numpy as np
import pandas as pd
from itertools import product

from pyxla import load_data, distr_v

Easy Knapsack

• Large maximum weight

• Weight and profit are uncorrelated

# number of items
n = 10
l_bound = 0
u_bound = 100

rng = np.random.default_rng(seed=42)
weights = rng.integers(l_bound, u_bound, size=10) 
weights

# max weight
max_weight = weights.sum() * 0.75

profits = rng.integers(l_bound, u_bound, size=10)
profits

binary_numbers = [p for p in product('01', repeat=n)]
X = pd.DataFrame(binary_numbers).astype(int)

# compute profit
def profit(x, profits):
    chosen = np.where(x == 1)
    return profits[chosen].sum()

# compute violation
def weight_violation(x, weights):
    chosen = np.where(x == 1)
    diff = weights[chosen].sum() - max_weight
    return diff if diff > 0 else 0

F = pd.DataFrame()
F['f0'] = X.apply(lambda x: profit(x, profits), axis=1)
F

V = pd.DataFrame()
V['v0'] = X.apply(lambda x: weight_violation(x, weights), axis=1)
V

easy_kp = {
    'name': 'easy_kp',
    'X': X,
    'F': F,
    'V': V,
    max: True
}

load_data(easy_kp)

feat, plot = distr_v(easy_kp, title=False)

Hard knapsack

• Small maximum weight

• Weight and profit are correlated

# combination with repetition?
rng = np.random.default_rng(seed=42)
weights = rng.integers(l_bound, u_bound, size=10)
weights.sort()
weights

# max weight
max_weight = (u_bound + l_bound) / 2

profits = rng.integers(l_bound, u_bound, size=10)
profits.sort()
profits

F = pd.DataFrame()
F['f0'] = X.apply(lambda x: profit(x, profits), axis=1)
F

V = pd.DataFrame()
V['v0'] = X.apply(lambda x: weight_violation(x, weights), axis=1)
V

hard_kp = {
    'name': 'hard_kp',
    'X': X,
    'F': F,
    'V': V,
    max: True
}

load_data(hard_kp)

feat, plot = distr_v(hard_kp, title=False)