<jupyter_start><jupyter_text>Intro to Mathematical Optimization And maybe a quick intro to Excel Solver... And possibly some stuff about snakes, er... Python  Mathematical Optimization BackgroundFrom [Wikipedia](https://en.wikipedia.org/wiki/Mathematical_optimization):>**Mathematical optimization** (alternatively spelled *optimisation*) or **mathematical programming** is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimization problems of sorts arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.>In the simplest case, an optimization problem consists of maximizing or minimizing a real function by systematically choosing input values from within an allowed set and computing the value of the function. The generalization of optimization theory and techniques to other formulations constitutes a large area of applied mathematics. More generally, optimization includes finding "best available" values of some objective function given a defined domain (or input), including a variety of different types of objective functions and different types of domains.  A series of mathematical methods to find the best option out of a wide range of possible options  Linear Programming! A method of describing and solving a mathematical optimization problem by using linear inequalities Which may or may not actually involve programming...  Linear programming is used across a wide variety of domains for many different applications.  Some common ones are: - Determining how many of each item a production facility should make in order to maximize profits. - Minimizing staffing costs. - Selecting candidates for interviews/research studies.  Components of an LP model - Decision variables    - How much of X am I going to make?    - How many employees will I assign to shift N?    - What percentage of the formula should be of Z material? - Constraints    - Linear Inequalities    - $10x <= 197$    - $3x > 12$ - Objective function    - A formula representing the thing we want to minimize/maximize    - $3x + 10y$  Linear Programming Example 1: Furniture Inc. Production Problem >  Example 1: Furniture Inc. Production Problem > Furniture Inc. makes two products, tables and chairs, which are processed through the Assembly and Finishing departments.  > Assembly can handle up to 150 hours of work per week.  Finishing has 42 hours available per week.> Manufacturing one table requires:  &emsp; 10 hours of assembly and 2 hours of finishing.   Manufacturing one chair requires:  &emsp; 5 hours of assembly and 3 hours of finishing.  >If the profit is \\$8 per table and \$6 per chair, determine the number of chairs and tables to be produced so the total profit is maximized.  Formulating the problem: Identify the decision variables- \ of tables to make = $ T $- \ of chairs to make = $ C $  Formulating the problem: Identify the objective function1. The objective function is the outcome that we want to minimize or maximize2. The objective function must be formulated as a linear functionWe get \\$8 per table and \$6 per chair, so we could represent this with the following function:$$ profit = 8T + 6C $$Or in Excel, we could use a function like:`=(8 * A1) + (6 * B1)`Where cell A1 is the quantity of tables and cell B1 is the quantity of chairs.  Formulating the problem: Identify the constraintsWe have two constraints:- 150 hours of assembly time available- 42 hours of finishing time availableWe know that:- Tables take 10 hours of assembly time and 2 hours of finishing time- Chairs take 5 hours of assembly and 3 hours of finishing So total assembly time can be described as:$$ assembly = 10T + 5C $$And assembly time must be <= 150 hours.  For our linear programming problem, we could formulate this as a **linear inequality** such as:$$ 10T + 5C <= 150 $$ and finishing time can be described as:$$ finishing = 2T + 3C $$And finishing time must be <= 42 hours.  For our linear programming problem, we could formulate this as a **linear inequality** such as:$$ 2T + 3C <= 42 $$ $$ Maximize:$$$$8T + 6C \tag{Profit}$$$$ Subject\ to: $$$$ 10T + 5C <= 150 \tag{Manufacturing Constraint} $$$$ 2T + 3C <= 42 \tag{Finishing Constraint} $$  So, how do we do this in Excel?<jupyter_code># Import the solver from ortools
from ortools.linear_solver import pywraplp

# Instantiate the solver
solver = pywraplp.Solver('Furniture Inc. Example',
                           pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

# Create variables for tables and chairs.
# solver.IntVar() creates an integer variable (since we can only 
#create whole tables and chairs) and adds it to the solver.
# The parameters for IntVar are solver.IntVar(minimum, maximum, variable_name)
tables = solver.IntVar(0, solver.infinity(), 'Tables')  
chairs = solver.IntVar(0, solver.infinity(), 'Chairs')
# Next, we create the first constraint for manufacturing time:
#     
#    10 * tables + 5 * chairs <= 150
#
# For this, we use solver.Constraint(minimum, maximum) to add the constraint
# and use SetCoefficient(variable, coefficient) to add the variables and their 
# coefficient in from the functions above to this constraint.
manufacturing_constraint = solver.Constraint(0, 150)
manufacturing_constraint.SetCoefficient(tables, 10)
manufacturing_constraint.SetCoefficient(chairs, 5)
# Next, we add the finishing constraint:
#
#    2 * tables + 3 * chairs <= 42
finishing_constraint = solver.Constraint(0, 42)
finishing_constraint.SetCoefficient(tables, 2)
finishing_constraint.SetCoefficient(chairs, 3)
# Next, we add our objective function to the solver in a similar manner
# using solver.Objective() to create the objective function:
#
#    8 * tables + 6 * chairs = profit
objective = solver.Objective()
objective.SetCoefficient(tables, 8)
objective.SetCoefficient(chairs, 6)

# We use objective.SetMaximization() to tell the solver that our goal is to maximize
# the objective function.
objective.SetMaximization()
# Finally, we call solver.Solve() to solve this problem.
solver.Solve()

# Get the solution value for each variable and multiply by the coefficient in our
# objective function to get our maximum profit.
maximum_profit = 8 * tables.solution_value() + 6 * chairs.solution_value()

# Print the solution
print('Solution:')
print('Tables = %d' % round(tables.solution_value(), 0))
print('Chairs = %d' % round(chairs.solution_value(), 0))
# The objective value of the solution.
print('Maximum Profit =', maximum_profit)<jupyter_output>Solution:
Tables = 12
Chairs = 6
Maximum Profit = 132.0<jupyter_text>Further resources:- [Excel Solver course on Linkedin Learning](https://www.linkedin.com/learning/microsoft-excel-using-solver-for-decision-analysis)- [Google OR Tools Library](https://developers.google.com/optimization)- [Quick Solver Intro on on Ablebits.com](https://www.ablebits.com/office-addins-blog/2016/06/22/how-to-use-solver-in-excel-with-examples/)- [This Jupyter notebook hosted on Github so you can see the other examples](https://github.com/gaw89/OR/blob/master/lp_or_tools_slides.ipynb)  Linear Programming Example 2: Workforce SchedulingHere's the prompt for this problem given in the class notes:>The manager of a department store has decided to operate 24 hours a day.  On the basis of estimates of trade throughout thisperiod, he feels that he requires at least the following number of employees during the given time periods:>| Time Period | Minimum Employees ||------|------|| 0:01 - 4:00 | 10 || 4:01 - 8:00 | 15 || 8:01 - 12:00 | 8 || 12:01 - 16:00 | 9 || 16:01 - 20:00 | 11 || 20:01 - 24:00 | 10 |>His employees may be scheduled to report to work at midnight, 4AM, 8AM, noon, 4PM, or 8PM.  Once employees report in, they must stay continuously for an 8-hour shift.  How many employees should be scheduled to report at each of the six periods so that overall number of personnel is minimized?  >We will formulate this as a linear programming model.To solve this problem, we first need to determine our decision variables which will be the number of employees starting at each time period:p1 = Number of employees reporting at the start of period 1p2 = Number of employees reporting at the start of period 2...for all time periods.Our goal will be to minimize the sum of all variables p1 to p6.$$ minimize: p1 + p2 + p3 + p4 + p5 + p6 $$For our constraints, we need to make sure that we have enough employees present in each period.  The tricky part is that employees are always there for two periods (since they have to work a continuous 8 hour shift.  To do this, we must have:| Time Period | Minimum Employees ||------|------|| p6 + p1 | >= 10 || p1 + p2 | >= 15 || p2 + p3 | >= 8 || p3 + p4 | >= 9 || p4 + p5 | >= 11 || p5 + p6 | >= 10 |Since those who start in period 6 will still be working during period 1 and those starting in period 1 will still be working during period 2, and so on...Now that we have our objective function and constraints, we can formulate our problem in Python. Example 2 Google OR Tools Solution<jupyter_code># Instantiate the solver
solver = pywraplp.Solver('Furniture Inc. Example',
                           pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

# Create variables for the number of employees starting 
# in each period.
p1 = solver.IntVar(0, solver.infinity(), 'Employees starting in period 1:')
p2 = solver.IntVar(0, solver.infinity(), 'Employees starting in period 2:')
p3 = solver.IntVar(0, solver.infinity(), 'Employees starting in period 3:')
p4 = solver.IntVar(0, solver.infinity(), 'Employees starting in period 4:')
p5 = solver.IntVar(0, solver.infinity(), 'Employees starting in period 5:')
p6 = solver.IntVar(0, solver.infinity(), 'Employees starting in period 6:')

# Create the constraints as listed above.

# p6 + p1  >= 10 
# p1 + p2  >= 15 
# p2 + p3  >= 8 
# p3 + p4  >= 9 
# p4 + p5  >= 11 
# p5 + p6  >= 10 

# The minimum number of employees working during period 1 is 10
minimum_employees_in_period_1 = solver.Constraint(10, solver.infinity())
minimum_employees_in_period_1.SetCoefficient(p6, 1)
minimum_employees_in_period_1.SetCoefficient(p1, 1)

# The minimum number of employees working during period 2 is 15
minimum_employees_in_period_2 = solver.Constraint(15, solver.infinity())
minimum_employees_in_period_2.SetCoefficient(p1, 1)
minimum_employees_in_period_2.SetCoefficient(p2, 1)

# The minimum number of employees working during period 3 is 8
minimum_employees_in_period_3 = solver.Constraint(8, solver.infinity())
minimum_employees_in_period_3.SetCoefficient(p2, 1)
minimum_employees_in_period_3.SetCoefficient(p3, 1)

# The minimum number of employees working during period 4 is 9
minimum_employees_in_period_4 = solver.Constraint(9, solver.infinity())
minimum_employees_in_period_4.SetCoefficient(p3, 1)
minimum_employees_in_period_4.SetCoefficient(p4, 1)

# The minimum number of employees working during period 5 is 11
minimum_employees_in_period_5 = solver.Constraint(11, solver.infinity())
minimum_employees_in_period_5.SetCoefficient(p4, 1)
minimum_employees_in_period_5.SetCoefficient(p5, 1)

# The minimum number of employees working during period 6 is 10
minimum_employees_in_period_6 = solver.Constraint(10, solver.infinity())
minimum_employees_in_period_6.SetCoefficient(p5, 1)
minimum_employees_in_period_6.SetCoefficient(p6, 1)

# Next, we add our objective function to the solver in a similar manner
# using solver.Objective() to create the objective function:
#
#    8 * tables + 6 * chairs = profit
objective = solver.Objective()
objective.SetCoefficient(p1, 1)
objective.SetCoefficient(p2, 1)
objective.SetCoefficient(p3, 1)
objective.SetCoefficient(p4, 1)
objective.SetCoefficient(p5, 1)
objective.SetCoefficient(p6, 1)

# Since we are trying to minimize the objective function, we call
# objective.SetMinimization()
objective.SetMinimization()

# Solve the problem
solver.Solve()

# List the variables
variables = [p1, p2, p3, p4, p5, p6]

# Print the solution
print('Optimal Solution:')
for var in variables:
    print('    ', var.name(), var.solution_value())<jupyter_output>Optimal Solution:
     Employees starting in period 1: 2.0
     Employees starting in period 2: 13.0
     Employees starting in period 3: 0.0
     Employees starting in period 4: 9.0
     Employees starting in period 5: 2.0
     Employees starting in period 6: 8.0<jupyter_text>Linear Programming Example 3: Interview SelectionHere's the prompt:>A marketing research firm has been retained to conduct focus group interviews for a real estate company. Plans are made to classify the participants as to age: over 45, or 45 or under, and whether or not they have recently bought and/or sold a house (within the last 2 years). Somespecific guidelines have been developed.> 1. At least 100 people must be selected.2. At least 3/4 of the participants must have bought orsold recently.3. Of those who have not bought or sold recently, at least 40%must be over 45.4. No more than 40% of the participants should be 45or under.> There is a preliminary screening of participants. The cost to screen each participant begins at `$`10. Additional contact with those over 45 raises the cost by `$`12. Additional time with the recent buyers and sellers adds `$`7 to the cost of including those participants. > In order to minimize total cost, how many people in each category should be in the group? Formulate as an LP problem.For this problem, our decision variables are:1. Number of people over 45 who have bought or sold recently (x1)2. Number of people over 45 who have **not** bought or sold recently (x2)3. Number of people 45 or under who have bought or sold recently (x3) 4. Number of people 45 or under who have **not** bought or sold recently (x4)The constraints will look like:1. Total people selected is at least 1002. Number of people who have bought or sold recently must be at least .75 * (x1 + x2 + x3 + x4)3. x2 / (x2 + x4) >= .44. (x3 + x4) / (x1 + x2 + x3 + x4) < .4And the objective function is:    x1 cost: = 29    x2 cost: = 22    x3 cost: = 17    x4 cost: = 10     minimize:    x1 * 29 + x2 * 22 + x3 * 17 + x4 * 10    With our variables, constraints, and objective function in place, we can formulate our problem in OR Tools: Example 2 Google OR Tools Solution<jupyter_code># Instantiate the solver
solver = pywraplp.Solver('Furniture Inc. Example',
                           pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

# Create variables for the number of employees starting 
# in each period.
x1 = solver.IntVar(0, solver.infinity(), 'Number of people over 45 who have bought/sold recently:')
x2 = solver.IntVar(0, solver.infinity(), 'Number of people over 45 who have not bought/sold recently:')
x3 = solver.IntVar(0, solver.infinity(), 'Number of people 45 or under who have bought/sold recently:')
x4 = solver.IntVar(0, solver.infinity(), 'Number of people 45 or under who have not bought/sold recently:')

# List the variables and cost of each for later use:
variables = [x1, x2, x3, x4]
costs = [29, 22, 17, 10]


# Since a number of our constraints depend on the total number of people
# we create a separate variable to hold that total.  We can then use that variable in our
# constraints
var_total = sum([x1, x2, x3, x4])

# Instantiate constraints

# Here, we'll use a slightly different syntax to add the constraints.  Using solver.Add()
# we can simply write out our expression as a linear inequality

# Constraint number 1:
#    Minimum number of people selected is 100
solver.Add(var_total >= 100)


# Constraint number 2:
#    Number of people who have bought or sold recently must be at least 75% of total
#    or x1 + x3 >= .75 * var_total

# Create a variable for the total number * .75
min_bought_sold = var_total * .75

# Use solver.Sum() to get the total of x1 and x3.
solver.Add(solver.Sum([x1, x3]) >= min_bought_sold)

# Constraint number 3:
#    Of those who have not bought or sold recently, at least 40% must be over 45.
#    The total number of people who haven't bought or sold is the sum of x2 and x4, so:
#        x2 > (x2 + x4) * .4
#    However, since the solver can't take greater than or less than, we must adjust our coefficient 
#    on the right-hand side of this equation.  Since we know that the minimum number of people allowed is 100,
#    we can simply rewrite this inequality as >= .41 since 100 * .41 = 41

min_no_buy_over_45 = sum([x2, x4]) * .41
solver.Add(x2 >= min_no_buy_over_45)


# Constraint number 4:
#    No more than 40% of the participants should be 45 or under.  Using the same logic as above, we rewrite this 
#   inequality to be <= .39
#   (x3 + x4) / (x1 + x2 + x3 + x4) < .39
max_under_45 = var_total * .39

solver.Add(solver.Sum([x3, x4]) <= max_under_45)

objective = solver.Objective()

# We can use the variable and cost lists we created above to programatically add
# the coefficients to the objective function in a list comprehension.
[objective.SetCoefficient(var, cost) for var, cost in zip(variables, costs)]


# Since we are trying to minimize the objective function, we call
# objective.SetMinimization().
objective.SetMinimization()

# Solve the problem.  This time, we'll save the output of solver.Solve() so we can check whether the solution found is an 
# optimal one.
status = solver.Solve()


# Determine the total cost and print the solution.
ttl_cost = 0
print('Optimal Solution:')
for var, cost in zip(variables, costs):
    val = var.solution_value()
    
    # Add the cost to the total
    ttl_cost += val * cost
    print('\t', var.name(), val)
    
    
print() 
print("Total Cost of Interviews:")
print("\t$%0.2f" % ttl_cost)
print()


# Now, just to make sure we got our constraints input correctly, let's check them manually.
total_people = var_total.solution_value()
total_bought_sold = sum([x1, x3]).solution_value()
total_under_45 = sum([x2, x4]).solution_value()

print("Checking constraint number 1...")
print("Total number of people should be greater than or equal to 100:")
print("\tTotal number of people in solution: %d." % total_people)
print()

print("Checking constraint number 2...")
print("The number of people who have bought or sold recently must be at least 75% of the total.")
print("\tTotal number of people who have bought or sold: %d." % total_bought_sold)
print("\tThis number is %0.0f%% of the total." % ((total_bought_sold / total_people) * 100))
print()

print("Checking constraint number 3...")
print("Of those who have not bought or sold recently, at least 40% must be over 45.")
print("\tTotal number of people over 45 who have bought or sold: %d." % x1.solution_value())
print("\tThis number is %0.0f%% of all who have bought or sold recently." % ((x1.solution_value() / total_bought_sold) * 100))
print()

print("Checking constraint number 4...")
print("No more than 40% of the participants should be 45 or under.")
print("\tTotal number of participants under 45 is %d." % total_under_45)
print("\tThis number is %0.0f%% of all who have bought or sold recently." % ((total_under_45 / total_people) * 100))
print()<jupyter_output>Optimal Solution:
	 Number of people over 45 who have bought/sold recently: 50.0
	 Number of people over 45 who have not bought/sold recently: 11.0
	 Number of people 45 or under who have bought/sold recently: 25.0
	 Number of people 45 or under who have not bought/sold recently: 14.0

Total Cost of Interviews:
	$2257.00

Checking constraint number 1...
Total number of people should be greater than or equal to 100:
	Total number of people in solution: 100.

Checking constraint number 2...
The number of people who have bought or sold recently must be at least 75% of the total.
	Total number of people who have bought or sold: 75.
	This number is 75% of the total.

Checking constraint number 3...
Of those who have not bought or sold recently, at least 40% must be over 45.
	Total number of people over 45 who have bought or sold: 50.
	This number is 67% of all who have bought or sold recently.

Checking constraint number 4...
No more than 40% of the participants should be 45 or under.
	Tota[...]<jupyter_text>As we can see from the output, we have sucessfully met all of the constraints listed in the problem statement.  The question still remains, however, as to whether this is an optimal solution.  Thankfully, Google OR Tools comes with a way to check the status of our solution.  Above, we saved the output of our call to `solver.Solve()` in a variable called `status`.  Calling `solver.Solve()` returns an integer which represents the status of the solution (e.g. whether it's optimal, infeasible, etc.).  The `solver` class also comes with properties that represent each possible status.  We can compare the output of `solver.Solve()` to these properties to determine if an optimal solution was found.<jupyter_code># solver.OPTIMAL represents an optimal solution.  If the status equals solver.OPTIMAL, we can be confident that
# we have found the best possible solution to our problem given the constraints that we have.
print(solver.OPTIMAL == status)<jupyter_output>True
{'fraction_non_alphanumeric': 0.08206485771012574, 'fraction_numerical': 0.03247612744634584, 'mean_word_length': 4.3086574654956085, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 48, 'https://': 5, 'lorem ipsum': 0, 'www.': 2, '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': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '528478', 'license': 'MIT', 'n_tokens_mistral': 6606, 'n_tokens_neox': 5868, 'n_words': 2820, 'path': 'lp_or_tools_slides.ipynb', 'repo_name': 'gaw89/OR', 'size': '21154'}