MATH 381 Assignment 2
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH 381 Assignment 2
1 Short Exercises
Due July 11th
● Problem 2 from Chapter 6
● Consider the following linear programming problem:
Minimize 4x1 ＋ 5x2 ＋6x3 ,
subject to the constraints:
x1 ＋x2 > 11
x1 - x2 ≤ 5
-x1 - x2 ＋x3 = 0
7x1 ＋ 12x3 > 35
x1 > 0
x2 > 0
x3 > 0
Formulate the dual linear program and find the optimum solution using the simplex algorithm.
● Recall from the lecture on graph coloring that scheduling can be formulated as a graph coloring optimization problem. In this question, you’ll formulate this as an integer programming problem that could potentially be input into a solver. Let G = (V, E, w) be a weighted graph.
(a) Letting n = lV l, define a binary integer variable xv,i for each edge v e V and 1 ≤ i ≤ n. This
variable is 1 if the edge v is colored i and 0 if it is not. In a graph coloring, each vertex is colored exactly one color. Write down linear constraints to ensure that this is the case.
(b) Define additional integer variables xu,v for each edge (u, v) e E . Write down a set of linear constraints to ensure that xu,v is 1 if u and v are colored the same color and 0 if u and v are colored different colors.
(c) Define an objective function that represents the quantity we want to minimize, which is the sum of w(u, v) over all edges (u, v) where u and v are colored the same color.
For parts (a) and (b), you may express your linear constraints along the lines of “for every vertex v and integer i between 1 and n, we introduce a constraint of the form . . .” or “for every edge (u, v) e E and integer i between 1 and n, we introduce a constraint of the form . . .” .
2 Modeling Project - Security Cameras
Due July 18th
2.1 Introduction
In this assignment you will be designing an optimal placement of security cameras for the Isabella Stewart Gardner museum in Boston, Massachusetts. The museum houses the personal collection of art collector Isabella Stewart Gardner and contains 3 floors full of various types of artwork. On the early morning of March 18, 1990, a major theft occurred where 13 pieces were stolen from the museum. It is known that the two suspects dressed up as police, subdued the guards on duty at the time, stole the 13 art works, and left within 81 minutes. There was no alert of the robbery until the next guard shift arrived onto the scene. To this current day, the suspects have not been caught and the art pieces have not been recovered.
At the time, there were 4 security cameras that guarded the outside of the museum and infrared sensors in the interior that were able to track the thieves’ movements. However, there was a distinct lack of security cameras in the interior of the museum and the only information authorities have for tracking down the thieves is based on a verbal description by the subdued guards. Interior security cameras were not installed due to prohibitive costs, but would have helped authorities in identifying the thieves. In this assignment, you will be given a simplified floor plan of the Isabella Stewart Gardner museum and use integer programming to identify the minimum number of cameras needed to achieve full coverage of the museum floor.
2.2 Floor Plan Representation
A simplified floor plan of the museum can be found on the official website’s map. The three floors have been cropped out and provided for you as floor1 .png, floor2 .png, and floor3 .png. Additionally, each floor plan’s image has been processed for you into a bitmap file, which consists of a black and white image, where black pixels cannot be seen past and white pixels are floor space that must be covered by cameras. Some additional choices have been made such as not installing cameras in the restrooms.
The full floor plan has a resolution of 824 x 640 pixels and the corresponding integer program generated based on a bitmap of the full floor plan will unfortunately be too large to run on most laptops. As a result, a bitmap at 1/8th the resolution (103 x 80 pixels) has been provided for you. You will solve the integer programming solution on the smaller bitmap and the starter code will scale the solution up to render cameras on the full resolution image. In addition, you can page through the various floors of the Isabella Stewart Gardner museum with the up and down arrow keys.
There is a TEXTURE SET variable provided for you in the starter code. Setting the TEXTURE SET to 0 will run your solver on a sample image which consists of only the lower half of the first floor of the museum. This will be a good baseline to test your solution before moving on to the full museum floor plan, which may take up to 10 minutes to solve optimally. For the sample floor plan, you should require 7 cameras in an optimal solution.
2.3 Security Cameras
A security camera class has been provided for you that takes in the (x, y) coordinates of the camera, its field of view, the direction it is facing, and the floor bitmap it belongs to. Given this information, the class will compute a 2d visibility matrix that you can access to check which floor coordinates are visible to that camera. The field of view for a camera indicates how wide of an angle it can see and a default value of 90o has been provided for you. This is a fairly typical of a wide angle security camera, though some go up to 110o . As you work on this modeling assignment, you will want to modify the field of view to see how it affects the number of cameras required.
Once you have computed security cameras in your implementation of the solve() function, the starter code will render the cameras and their visible line of sight. You may notice that the line of sight does not fully cover the floor plan. This is because the integer programming problem was solved on a downscaled image and hence the solution is not exact when scaled back up. In addition, if you decide to experiment with mixing cameras with different field of view angles, you may wish to modify the rendering code to use different colors for different types of cameras.
2.4 Defining the Integer Program
As mentioned in class, there are often multiple ways to formulate a problem into a linear or integer pro- gramming problem. A major component of this modeling assignment is determining how to translate this optimization problem into an integer program with a reasonable number of variables and constraints. Here are some guidelines and tips:
● Cameras should only be placed adjacent to a wall, as is typical in museums. This will also limit the number of camera positions you need to consider.
● In the starter code, NUM DIRECTIONS is set to a default of 8, allowing for cameras to be positioned at angles that are multiples of 45o . You may decide to change this later, but 8 possible directions per camera is a good starting point.
● Any given (x, y) coordinate should only contain a single camera.
● The biggest constraint you have is that every white pixel in the bitmap must lie in the viewable space of at least one camera. These should constitute the bulk of your constraints.
2.5 Integer Programming with OR-Tools
There are a multitude of linear programming and mixed integer programming solving tools out there. The commercial solvers are often an order of magnitude faster and implement sophisticated heuristics in addition to having very optimized code. We will be using the free OR-Tools which is developed by Google. It provides a single library that is easy to install and compatible with both Java and Python. In addition, it allows you to use try out different free solvers within the library in the chance that one of them works better than the others. The default solver in the starter code is SCIP. Another built-in mixed integer programming solvers you may wish to try is CBC. The commercial solver Gurobi provides free licenses for students and you may optionally try it as well.
A basic guide for using OR-Tools to solve an integer programming problem can be found here. You can create IntVar to represent integer valued variables. If your variables should only take on values of 0 or 1, you can define BoolVar’s instead. These are essentially IntVar’s with two constraints providing a lower bound of 0 and an upper bound of 1. To define constraints, you will be calling the makeConstraint() function to get an MPConstraint object. The non-zero coefficients for each variable in the constraint can then be set using setCoefficient().
2.6 Write Up Instructions
In your writeup, you should describe how you formulated the security camera placement problem into an integer programming and describe the results of experimenting with custom floor layouts and different field of view angles on the camera.
● Write in detail what each variable represents and how the inequalities you defined represent the con- straints that need to be imposed on the problem.
● Draw out some custom floor bitmaps and test your linear program on them. What sort of layouts seem to generate an integer program that is faster to solve and what sort of layouts seem to generate an integer program that is slower to solve?
● Try out different field of view angles on cameras, such as 60o or 110o . Optionally, assign different costs to different field of view options and modify your code to compute a placement of cameras that allows for a mix of field of view angles and minimizes the total cost.
2023-07-12