A feasible region drawn as a shaded polygon, its boundary traced in blue, with Pacman sitting at the optimal vertex and ghosts crowding the infeasible region outside.

Optimization

Pacman must stay safe,
Don't violate the constraints,
Shrink that objective.

Introduction

In this project, you will implement algorithms to solve optimization problems formulated as linear and integer programs: a vertex-enumeration LP solver (Questions 1-3), branch and bound for integer programs (Question 5), and the formulation of two word problems (Questions 4, 6 and 7).

Download: all the code and supporting files are in optimization.zip. Download it, unzip it, and change into the optimization directory. The code needs numpy:

python3 -m pip install numpy

(Use the same python3 command you use to run the autograder. The commands below assume it is Python 3.12.)

As in previous programming assignments, this assignment includes an autograder for you to grade your answers on your machine. This can be run with the command:

python3 autograder.py

See the autograder tutorial in Project 0 for more information about using the autograder.

The code for this project consists of several Python files, some of which you will need to read and understand in order to complete the assignment, and some of which you can ignore.

Files you will edit

`optimization.py`	Where all of your optimization code will reside.

Files you might want to look at

`pacmanPlot.py`	Plots 2-D feasible regions, with Pacman at the optimal point and ghosts at the infeasible intersections.
`util.py`	Data structures, including the `PriorityQueue` you may want for branch and bound.
`test_cases/`	Directory containing the test cases for each question

Files you will not edit

`optimizationTestClasses.py`	Project specific autograding test classes
`autograder.py`	Project autograder
`testParser.py`	Parses autograder test and solution files
`testClasses.py`	General autograding test classes
`textDisplay.py`, `grading.py`	Support for the autograder
`graphicsDisplay.py`, `graphicsUtils.py`	Graphics for Pacman
`pacman.py`, `game.py`, `layout.py`	The Pacman game, its logistics, and its layouts
`pacmanAgents.py`, `ghostAgents.py`, `keyboardAgents.py`	Agents to control Pacman and the ghosts

Files to Edit and Submit: You will fill in portions of optimization.py during the assignment. You should submit this file with your code and comments. Please do not change the other files in this distribution or submit any of our original files other than this file.

Evaluation: Your code will be autograded for technical correctness. Please do not change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. However, the correctness of your implementation, not the autograder's judgements, will be the final judge of your score. If necessary, we will review and grade assignments individually to ensure that you receive due credit for your work.

Academic Dishonesty: We will be checking your code against other submissions in the class for logical redundancy. If you copy someone else's code and submit it with minor changes, we will know. These cheat detectors are quite hard to fool, so please don't try. We trust you all to submit your own work only; please don't let us down. If you do, we will pursue the strongest consequences available to us.

Getting Help: You are not alone! If you find yourself stuck on something, contact the course staff for help. Office hours, section, and the discussion forum are there for your support; please use them. If you can't make our office hours, let us know and we will schedule more. We want these projects to be rewarding and instructional, not frustrating and demoralizing. But, we don't know when or how to help unless you ask.

Discussion: Please be careful not to post spoilers.

The Pacman graphics in this assignment are based on the Pacman AI projects developed at UC Berkeley, http://ai.berkeley.edu. Although the graphics are not needed to solve the problems in this programming assignment, they are there to help make linear programming more fun :).

Assignment FAQ

We have compiled a list of frequently asked questions and common mistakes on various problems in this assignment. Please read this list carefully, and refer back to this before asking any questions on the discussion board.

All questions: Every function takes constraints as a list of ((a1, ..., aN), b) pairs meaning $a_1 x_1 + \dots + a_N x_N \le b$. A $\ge$ constraint is a $\le$ constraint with both sides negated, and the objective is always minimized, so a problem that maximizes utility minimizes its negative.
Questions 2 and 5: Compare floating point values with a tolerance of 1e-12, using np.abs. Q2 checks feasibility against the bound; Q5 checks whether a value is within 1e-12 of the nearest integer (so floor alone is not enough).
Question 1: The equality test (==) is not defined for numpy arrays the way it is for lists. Convert arrays with .tolist() (or build tuples) before comparing them, and remember that some comparisons are implicit, for example inside the priority queue.
Question 5: Push a fresh constraint list onto the priority queue for each branch. Do not append to a list that is already on the queue, and do not mutate anything you have pushed.
Question 5: The problems in the test cases are small and should solve in well under a second. If your implementation is slow, it is probably branching forever on a value it thinks is not an integer, or re-solving the same subproblem.

Question 1 (7 points): Find Intersections

Implement the function findIntersections in optimization.py to return a list of all intersection points given a list of linear inequality constraints.

You can test your implementation with the following:

python3 autograder.py -t test_cases/q1/test2D_1

python3 autograder.py -q q1

You may want to start with a 2-D implementation, getting the first set of test cases working, before proceeding to support N dimensions. In 2-D, you can use your plotting skills to help visualize and debug your work.

You will probably want to take advantage of the numpy library for doing linear algebra in Python (python3 -m pip install numpy if you don't already have it, using the same python3 you run the autograder with, and here is a quick tutorial). The following operations will be particularly useful:

np.dot(A,x): Matrix-vector multiplication
np.linalg.solve(A,b): Solve the system of linear equations $Ax=b$ for $x$
np.linalg.matrix_rank(A): A matrix has to be square ($N\times N$) and full rank (rank = $N$) in order for np.linalg.solve to work. Note: What is the relationship between rank and intersecting hyperplanes (defined by rows of $A$ and $b$)?
A[(1,3,5), :]: Select the first, third, and fifth rows of $A$ (and all columns)
itertools.combinations(A, n): Creates n length subsequences of elements from the input A.
Note that the equality test (==) is undefined for numpy arrays. You should use np.tolist() to convert arrays into lists before comparing them. Some of the comparisons may be implicit (e.g., the ones in the priority queue).

The autograder plots each 2-D test case as it passes: the constraints, the feasible region, and your intersection points as ghosts. If you want to pause the graphics on the screen, you can change the occurrences of graphicsUtils.sleep(1) to self.takeControl() in pacmanPlot.py. Note that the program will quit after you close the window if you make this change, so only do so if you're running one test case at a time. To skip the plots entirely, run the autograder without graphics:

python3 autograder.py -q q1 --no-graphics

Question 2 (2 points): Find Feasible Intersections

Implement the function findFeasibleIntersections in optimization.py to return a list of all feasible intersection points given a list of linear inequality constraints. Feasible intersection points are intersection points where all the constraints are satisfied.

Important: Because it is problematic to compare floating point values, you will still want to allow values to be feasible if they are within 1e-12 of their corresponding limit. (To clarify, this is the same as $10^{-12}$, but Python supports writing 1e-12 as a number.) You can check to see if borderline floating point values in your program are within the constraints by seeing if they are within 1e-12 of the bound. You should use np.abs, not math.abs.

You can test your implementation with the following:

python3 autograder.py -t test_cases/q2/test2D_1

python3 autograder.py -q q2

Question 3 (2 points): Find Optimal Intersection

Implement the function solveLP in optimization.py to return a feasible intersection point that minimizes the objective. Your algorithm can simply step through all feasible intersection points, looking for the one that gives the minimal objective value. You may assume that if a solution exists that it will be bounded, i.e., not infinity.

The output from this function should be a tuple (an N-dimensional optimal point, the corresponding objective value at that point). Return None if there is no feasible solution.

You can test your implementation with the following:

python3 autograder.py -t test_cases/q3/test2D_1

python3 autograder.py -q q3

Question 4 (2 points): Problem Formulation (LP)

Represent the following problem as a linear program. Implement the function wordProblemLP in optimization.py to construct constraints and a cost vector, then call your solveLP function to return the optimal solution.

Pat is packing for his trip to Hawaii. He wants to bring sunscreen and Tantrum energy drink, the two most important things to pack for a vacation. Help Pat determine how many fluid ounces of sunscreen and how many fluid ounces of Tantrum he wants to pack while making sure he doesn't pay extra for a heavy bag.

Assume that Pat is checking a suitcase filled entirely with sunscreen and Tantrum. Pat needs at least 20 fluid ounces of sunscreen and at least 15.5 fluid ounces of Tantrum. Pat's suitcase can fit 100 units of stuff. A fluid ounce of sunscreen takes 2.5 units of space and a fluid ounce of Tantrum takes 2.5 units of space. Furthermore, to avoid baggage fees, the suitcase can weigh at most 50 pounds. A fluid ounce of sunscreen weighs 0.5 pounds and a fluid ounce of Tantrum weighs 0.25 pounds. We want to make sure Pat has a good time in Hawaii so we want to pack things that maximize Pat's happiness in Hawaii. Each fluid ounce of sunscreen gives Pat a utility of 7 while each fluid ounce of Tantrum gives Pat a utility of 4. How can we pack so that Pat has the best vacation ever?

Return ((sunscreen_amount, tantrum_amount), maximal_utility). Note that solveLP minimizes, and the utility here is to be maximized.

You can test your implementation with the following:

python3 autograder.py -q q4

Question 5 (7 points): Branch and Bound

Now that you're a linear programming wizard, let's take things a step farther. Solve integer programming problems by implementing the branch and bound algorithm in the solveIP function in optimization.py. Given a list of linear inequality constraints and a cost vector, use the branch and bound algorithm to find a feasible point with integer values that minimizes the objective.

Pseudocode for branch and bound can be found in the course notes.

Important: You should check to see if floating point values in your program are integers by seeing if they are within 1e-12 of the nearest integer value (hint: the floor function is not enough). You should use np.abs, not math.abs. This problem will also build on your LP solver from Question 3. Even if you pass the autograder for Question 3, it may fail you here if you are not using the correct tolerance checks.

You can test your implementation with the following:

python3 autograder.py -t test_cases/q5/test2D_1

python3 autograder.py -q q5

Hint: Consider making use of the PriorityQueue or PriorityQueueWithFunction (which takes in an extra argument of the priority function) classes in util.py. Note the difference between the push and the update function. Make sure you do not mutate objects pushed onto a priority queue.

Note: The problems in these test cases should be short to solve, so if your implementation isn't solving them quickly, there may be a bug.

Food Distribution

No Poverty and Zero Hunger are listed as the top two Sustainable Development Goals by the United Nations. Food rescue service provides a promising way to reduce food waste, overcome food insecurity and improve environmental sustainability. Organizations providing food rescue service rescue the surplus food from different food providers and redistribute it to local communities that are in need of food.

For Questions 6 and 7, you will help a food rescue organization FS to decide how to redistribute the food in an efficient way. The problem is abstracted in the following way: There are $M$ food providers (referred to as providers) and $N$ local communities in need of food (referred to as communities). Community $j$ needs at least $C_j$ integer units of food. The transportation cost per unit of food from provider $i$ to community $j$ is $T_{i,j}$. Assume that there is no limit on the amount of food that a provider can supply.

When transporting food from a provider to a community, trucks cannot be overweight. All trucks have the same weight limit per truck, and only exactly one truck moves between one provider $i$ and one community $j$. The food coming from provider $i$ has weight $W_i$ per unit.

We need to determine the integer number of food units to transport from each provider to each community, while meeting the above constraints and minimizing transportation costs.

Question 6 (2 points): Problem Formulation (IP)

Represent the following food distribution problem as an integer program. Implement the function wordProblemIP in optimization.py to construct constraints and a cost vector, then call your solveIP function to return the optimal solution.

Before solving world hunger, we will practice with campus hunger following the food distribution setup above. In this specific case, we have three providers (Dunkin Donuts, Eatunique, and the Au Bon Pain) and two communities (Gates and Sorrells).

The communities require at least the following number of units of food:

Gates: 15
Sorrells: 30

The truck weight limit is 30 and exactly one truck is allowed between each provider and community (i.e., one truck per provider-community pair). The weight per unit and transportation cost per unit are as follows:

	Weight	Gates	Sorrells
Dunkin Donuts	1.2	$12	$20
Eatunique	1.3	$4	$5
Au Bon Pain	1.1	$2	$1

Return the six food amounts in the order given in the docstring, provider by provider (Dunkin Donuts to Gates, Dunkin Donuts to Sorrells, Eatunique to Gates, and so on), followed by the minimal cost.

You can test your implementation with the following:

python3 autograder.py -q q6

Note: Some people find it more convenient to implement the more general food distribution in Question 7 before implementing this specific problem.

Question 7 (3 points): Food Distribution IP

Implement the function foodDistribution in optimization.py to handle the general food distribution integer programming problem:

Given $M$ food providers and $N$ communities, return the integer number of units that each provider should send to each community to satisfy the constraints and minimize transportation cost.

You can test your implementation with the following:

python3 autograder.py -q q7

Submission

Complete Questions 1 through 7 as specified in the project instructions. Then upload optimization.py to Gradescope.

Prior to submitting, be sure you run the autograder on your own machine. Running the autograder locally will help you to debug and expedite your development process. The autograder can be invoked on your own machine using the command:

python3 autograder.py

To run the autograder on a single question, such as question 3, invoke it by

python3 autograder.py -q q3

Note that running the autograder locally will not register your grades with us. Remember to submit your code to Gradescope when you want to register your grades for this assignment.

The autograder on Gradescope might take a while but don't worry: so long as you submit before the due date, it's not late.

What Now?

Great job completing this assignment! This section is dedicated to extension projects and readings related to the concepts in LP and optimization you've now learned and applied, should you be interested in further exploration.

Optimization is a HUGE topic in both industry and research, finding practical applications in areas like machine learning and operations research.

You can find open source optimization software which you can try out and use yourself from Google's OR-Tools. If you have pip, you can install OR-Tools via

python3 -m pip install ortools

Alternative installation options here.

This is an example demonstrating mixed integer linear program formulation and optimization with OR-Tools. As you can see, doing so is as simple as creating variables, defining the constraints and objective, and calling Solve().

More examples can be found here. These include code samples tackling problems involving vehicle routing, flows, integer and linear programming, and constraint programming.

We list some pertinent examples below:

Another state-of-the-art tool for optimization is Gurobi Optimizer. Gurobi provides an API for constructing and solving a variety of optimization problems, including linear and mixed integer linear programs.

Here are a couple of case studies of Gurobi's usage in industry:

Note that you do need to obtain a license to use Gurobi (which you can do through the university).