<jupyter_start><jupyter_text>Linear Programming, Optimization**Fundamental theorem of linear programming**"... Any linear program either is infeasible, is unbounded, or has an optimal solution with a finite objective value. In each case, [the algorithm] SIMPLEX acts appropriately." I.e. simplex will return an optimal solution or 'unbounded' or 'infeasible.' - *Introduction to Algorithms*, Third Edition, Cormen, Leirson, Rivest and Stein, 2009, MIT, Cambridge, Massachussetts, pg. 891*Note:*- "The Simplex algorithm does not run in polynomial time in the wors case, but it is fairly efficient and widely used in practice." (Ibid, 864)😎 **In other words:** *If you can formulate a problem as a system of linear equations, and you have more than two variables (dimensions) then the simplex algorithm is probably your best bet to solving it.*  Contents:- pending completion  Basic Example: Optimizing farming profitSuppose a farmer has 240 acres of land. - they can farm corn for a profit of \$40/acre and time cost of 2hr/acre- they can farm oats for a profit of \$30/acre and time cost of 1hr/acre- they only have 320 farmable hours before harvest is dueHow many acres of each should they plant to maximize profits?  We formulate the word problem as a linear program**Objective function: **profits = `p = 40*c + 30*o`subject to:**Constraint 1:** `c + o <= 240` total acres farmed **Constraint 2:** `2c + o <= 320` total hours farmed**Constraint 3:** `c, o >= 0` because they can't farm negative acres  We can graph the system of linear equations and constraints<jupyter_code>import plotly.plotly as py
import plotly.graph_objs as go
acres = [a for a in range(0, 240)] #we only include non-negative values since we can't farm negative acres.
    # notice the non-negativity constraint (i.e. constraint 3) is baked into the code here
acres_trace = go.Scatter(
    x = acres,
    y = [240 - a for a in acres], # for y <= 240 - x
    fill = 'tozeroy',
    name = 'farmable acres'
    
)
data = [acres_trace]
layout = go.Layout(
    title = 'Feasible Solution Area',
    xaxis = {'title': 'acres of corn'},
    yaxis = {'title': 'acres of oats'},
    showlegend = True,
)
fig = go.Figure(data = data, layout = layout)<jupyter_output><empty_output><jupyter_text>We'll start by graphing the solution space for the number of farmable acres<jupyter_code>py.iplot(fig, filename = 'linear-programming', 
                   fileopt = 'overwrite', sharing = 'public',
                  )<jupyter_output><empty_output><jupyter_text>We add the constraint of farmable hours<jupyter_code>hours = [h for h in range(0, 320)]
hours_trace = go.Scatter(
    x = hours,
    # y <= 320 - 2x
    y = [320 - 2*h for h in hours if 320 - 2*h >= 0], 
        #we add the conditional to the list comprehension to satisfy the non-negativity constraint
    fill = 'tozeroy',
    name = 'farmable hours',
)

data = [acres_trace, hours_trace]
layout = go.Layout(
    title = 'Feasible Solution Area',
    xaxis = {'title': 'acres of corn'},
    yaxis = {'title': 'acres of oats'},
    showlegend = True,
)
fig = go.Figure(data = data, layout = layout)<jupyter_output><empty_output><jupyter_text>And overlay the plot of it's solution space onto the first constraint<jupyter_code>py.iplot(fig, filename = 'linear-programming', 
                   fileopt = 'overwrite', sharing = 'public',
                  )<jupyter_output><empty_output><jupyter_text>Notice the intersection of the solution spaces is a solution space to the system of equations resulting from combining both constraints  Now we add the objective function to the system`p = 40c + 30o`, substitutting corn for x and oats for y we can isolate y for a version of the familiar **y = mx + b** => `p = 40x + 30y` => `y = (p/30) - (40/30)x` substitute the constant for the slope intercebt `b` we get=> `y = b - (4/3)x`  Example Word Problem, Integer Programming: Capital Budgeting?Suppose you need to buy as many notebooks as possible with a given budget ```n```. And notebooks are sold in "bundles" where each bundle has an integer quantity of books , ```q```, for an integer cost ```c```.Input format:1. n - an integer representing your budget    - ex: 8072. bundleQuantities - an array of length ```m``` of positive integers representing book quantities in each bundle    - ex: [176,  98, 105,  65,  61,  30, 113,  60,  67,  80]3. bundleCosts - an array of length ```m``` of positive integers representing book quantities in each bundle    - ex: [194, 180,   1, 143, 131,  30,  73,  93,  55, 178]     Write a function buyBooks(n, bundleQuantities, bundleCosts) which returns an integer representing the maximum number of books you can buy.Constraints:1. You can only buy whole numbers of bundles2. You can't buy "negative" bundles3. 0< n, m, q, b <= cap<jupyter_code>import pandas as pd
import numpy as np<jupyter_output><empty_output><jupyter_text>initialize values<jupyter_code># set random seed for reproducible results
np.random.seed(seed = 57)
# generate budget, and array lengths
cap = 1000
n = np.random.randint(1, cap)
print('budget is: ', n)
m = np.random.randint(1, cap)
print('array length is: ', m)
bundleQuantities = np.random.randint(1, cap, size = m)
bundleQuantities[0:10]
bundleCosts = np.random.randint(1,cap, size = m)
bundleCosts[0:10]
books_purchasable = [int(n/bc)*bq for bc,bq in zip(bundleCosts, bundleQuantities)]
books_purchasable[0:10]
max_books_purchased = max(books_purchasable)
max_books_purchased
for i in range(len(books_purchasable)):
    if books_purchasable[i] == max(books_purchasable):
        ix = i
ix
change_remaining = n - bundleCosts[ix]
change_remaining
df = pd.DataFrame()
df['bdgt_1'] = [n for i in range(len(bundleCosts))]
df['bundle_qty'] = bundleQuantities
df['bundle_cst'] = bundleCosts
df['bks_per_dollar'] = df['bundle_qty']/df.bundle_cst
df['mx_bndls_1'] = (df.bdgt_1/df.bundle_cst).apply(int)
df['mx_books1'] = df.mx_bndls_1*df.bundle_qty
df['exp_1'] = df.mx_bndls_1*df.bundle_cst
df['bdgt_2'] = df.bdgt_1 - df.exp_1
df.head()<jupyter_output><empty_output><jupyter_text>naive maximization attemptUsing greedy stepwise decisions<jupyter_code>def maximizeBooksStepwise(n, bq, bc, verbose = False):
    '''Takes integer n, two integer arrays: bundleQuantities and 
    bundleCosts respectively (both of which are length m) and returns 
    integer sum of the max books purchasable at every iteration.
    Note: This algorithm does not guarantee an optimal solution.
    Ex: n = 510, bq = [500, 498, 3], bc = [500, 499, 12] has an optimal solution:
    bq[1]+bq[2] > bq[0]
    498 + 3 > 500
    but maximizeBooksStepwise returns the solution
    500. See algorithms on integer linear programming'''
    books_purchased = 0
    iteration = 0
    while n >= min(bc): #while we can afford any of the packages #O(m)
        bp = [int(n/c)*q for c,q in zip(bc, bq)] # max books purchasable for every bundle #O(m)
        mbp = max(bp) #O(m)
        if verbose:
            iteration += 1
            print(iteration, 'books_purchasable: ', bp[0:5], '...', bp[-5:])
        if verbose:
            print(iteration, 'purchased ', mbp, ' books')
        books_purchased += mbp
        if verbose:
            print(iteration, 'for a running total of: ', books_purchased)
        for i in range(len(bp)):
            if bp[i] == mbp: #retrieve the index of max books purchasable at this iteration #O(m)
                j = i
                break
        n = n - bc[j]*int(n/bc[j]) #adjust remaining budget
        if verbose:
            print(iteration, n, ' budget remaining')
            print('-----------------------------')
    return books_purchased
# generate budget, and array lengths
cap = 10000
n = np.random.randint(cap, 2*cap)
print('budget is: ', n)
m = np.random.randint(1, cap)
print('array length is: ', m)
bundleQuantities = np.random.randint(1, cap, size = m)
print('bundleQuantities[0:5]', bundleQuantities[:5])
bundleCosts = np.random.randint(1,cap, size = m)
print('bundleCosts[0:5]', bundleCosts[:5])
print('')
maximizeBooksStepwise(n, bundleQuantities, bundleCosts, verbose = True)<jupyter_output>budget is:  10247
array length is:  3197
bundleQuantities[0:5] [1324 6513 9076 2908 5348]
bundleCosts[0:5] [6380 9984 2358 6669   46]

1 books_purchasable:  [1324, 6513, 36304, 2908, 1187256] ... [9560, 689, 3496, 8491, 128490]
1 purchased  7862013  books
1 for a running total of:  7862013
1 2  budget remaining
-----------------------------<jupyter_text>Using scipy.optimize.linprog()Non integral implementation<jupyter_code>from scipy.optimize import linprog
c = [-q/c for q,c in zip(bundleQuantities, bundleCosts)] # books/dolar coefficients
    #notice we have negated the values in c because linprog minimizes the given objective function
A = [bundleCosts] 
b = n # sum of Ax must be <= budget, n

res = linprog(c, A_ub = A, b_ub = b, options = {"disp": True})
print(res)<jupyter_output>Optimization terminated successfully.
         Current function value: -1572709.560000
         Iterations: 1
     fun: -1572709.56
 message: 'Optimization terminated successfully.'
     nit: 1
   slack: array([0.])
  status: 0
 success: True
       x: array([0., 0., 0., ..., 0., 0., 0.])
{'fraction_non_alphanumeric': 0.11685197296708089, 'fraction_numerical': 0.03989535644211903, 'mean_word_length': 3.751424132573796, 'pattern_counts': {'":': 1, '<': 38, '<?xml version=': 0, '>': 39, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '323076', 'license': 'MIT', 'n_tokens_mistral': 3229, 'n_tokens_neox': 2900, 'n_words': 1073, 'path': 'old-drafts/Linear Programming.ipynb', 'repo_name': 'MSS-AI/linear-programming', 'size': '9174'}