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

array([ 8, 77, 65, 43, 43, 85,  8, 69, 20,  9])

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

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

array([52, 97, 73, 76, 71, 78, 51, 12, 83, 45])

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

	f0
0	0
1	45
2	83
3	128
4	12
...	...
1019	626
1020	510
1021	555
1022	593
1023	638

1024 rows × 1 columns

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

	v0
0	0.00
1	0.00
2	0.00
3	0.00
4	0.00
...	...
1019	37.75
1020	77.75
1021	86.75
1022	97.75
1023	106.75

1024 rows × 1 columns

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

load_data(easy_kp)

distr_v(easy_kp)

({'v0_min': 0.0,
  'v0_max': 106.75,
  'v0_mean': 3.44970703125,
  'v0_med': 0.0,
  'v0_q1': 0.0,
  'v0_q3': 0.0,
  'v0_sd': 13.357994114263755,
  'v0_skew': 4.768478928911753,
  'v0_kurt': 24.55073996467836,
  'v0_feas_rate': 0.896484375,
  'overall_feas_rate': 0.896484375},
 <Figure size 300x600 with 2 Axes>)

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

array([ 8,  8,  9, 20, 43, 43, 65, 69, 77, 85])

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

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

array([12, 45, 51, 52, 71, 73, 76, 78, 83, 97])

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

	f0
0	0
1	97
2	83
3	180
4	78
...	...
1019	560
1020	458
1021	555
1022	541
1023	638

1024 rows × 1 columns

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

	v0
0	0.0
1	35.0
2	27.0
3	112.0
4	19.0
...	...
1019	308.0
1020	215.0
1021	300.0
1022	292.0
1023	377.0

1024 rows × 1 columns

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

load_data(hard_kp)

distr_v(hard_kp)

({'v0_min': 0.0,
  'v0_max': 377.0,
  'v0_mean': 163.943359375,
  'v0_med': 163.5,
  'v0_q1': 106.0,
  'v0_q3': 221.0,
  'v0_sd': 80.36536019395639,
  'v0_skew': 0.06657601903200383,
  'v0_kurt': -0.5064531918475104,
  'v0_feas_rate': 0.017578125,
  'overall_feas_rate': 0.017578125},
 <Figure size 300x600 with 2 Axes>)