Math and Accounting assignment

12/8/2020Graded homework set 6 (last)https://canvas.ucdavis.edu/courses/497959/assignments/5911591/3Graded homework set 6 (last)DueThursday by 10pmPoints20Availableafter Dec 7 at 10pm

Problem 1: Planning a professor’s moveAfter years of tiring commutes from a metropolitan area to the college campus, a professor plans tomove to an apartment in the college town. For the benefit of the campus community, help him plan hismove.

The professor has a lot of furniture. The spreadsheet furniture.csv describes the dimensions of thefurniture items and their practical and emotional values. All furniture items have a rectangular basis.They can be rotated, but only by 90 degrees.

The apartment that the professor wants to move to is reasonably nice but is smaller than his currentplace, so not all furniture will fit. All rooms are rectangular. The spreadsheet apartment1.csv describes the dimensions of all rooms.

There needs to be 3ft feet of air in the axis directions between any two items, but items can beplaced directly next to a wall. (There is a trick to simplify this requirement by making all items and allrooms larger by 1.5ft in all 4 axis directions.)The professor wishes to maximize the sum of the practical and the emotional value of all furniture itemsthat will fit into the new apartment.

(a) The most basic model of “packing problems” like this is the so-called knapsack problem. We ignorethe geometric nature of the problem and compute for each item a “weight” (= the area = length * width);we aggregate the areas of all rooms, obtaining a total “capacity”. Then the knapsack problem amounts todeciding for each item whether it should be used; this is subject to the capacity constraint; and we wishto optimize the sum of the practical and the emotional value of all items that are used. Note that thefurniture items are indivisible; it is not allowed to use 1/3 desk, for example.Write an optimization model using mathematical notation. Then model and solve it using AMPL orPyomo.(Ideally your model would be able to read the given .csv files; but you are allowed to preprocess ortransform them by hand.)

(b) The professor is concerned that he cannot fit all of his furniture items. The apartment complex offersseveral identical apartment units, so the professor considers renting several units at the same time, sothat he can fit all of his furniture. He wants to know how many units he needs.

12/8/2020Graded homework set 6 (last)https://canvas.ucdavis.edu/courses/497959/assignments/5911592/3Following part (a), we ignore the geometric nature of the packing problems and only want to pack itemsof given weights into the apartment units, each of which has the same capacity.This is the standard bin packing problem.Write an optimization model using mathematical notation. Then model and solve it using AMPL orPyomo.

Problem 2: Our personal polytopes – continued fromhomework set 5We continue working with our personal polytopes.

a. Using the method from the Monday lecture, determine the dimension of the convex hull P_{i,j} of theslice S_{i,j}, for all {i,j}. (For computing the rank of a matrix or other linear algebra tasks in thisproblem, it is allowed to use software.)b. For each of the 4 convex hulls P_{i,j},if P_{i,j} has dimension 3, then find a linear inequality that induces a facet (= face of dimension 2) thatis not a facet of the cube.if P_{i,j} has smaller dimension than 3, find a linear equation that holds for all points of it. (It is part ofthe description of the affine hull.)c. Using any method of your choice, find a linear objective function c and one of your slices S_{i,j} suchthat maximizing this objective function over the fractional no-good polytope F_{i,j} gives a fractionaloptimal solution (i.e., not all coordinates are 0 or 1). (This is an LP, not a MIP!) Use AMPL or Pyomo fordemonstrating this optimal solution.d. Change your variables x_i from real to binary. Solve the IP using the solver. Compare the optimalsolution to the one obtained in c). Discuss the result. e. Definition: Your personal extended polytope Q_{i,j} (slice) is the polytope in variables x_i (i=0,…4)and lambda_s for s in S_{i,j}, where lambda_s are convex multipliers and x = sum_{s in S_{i,j}} lambda_s* s.(This is the same extended formulation explained in the pre-recorded Wednesday lecture, 2020-12-09-a.)Using the same objective function and slice, set up an LP that is the extended formulation Q_{i,j} of theslice. Solve it using AMPL or Pyomo. Compare the optimal solution to the one obtained in c) and d).Discuss the result.