Problem 1: Planning a professor’s move

Problem 1: Planning a professor’s move
After years of tiring commutes from a metropolitan area to the college campus, a professor plans to
move to an apartment in the college town. For the benefit of the campus community, help him plan his
move.
The professor has a lot of furniture. The spreadsheet furniture.csv describes the dimensions of the
furniture 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 current
place, 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 be
placed directly next to a wall. (There is a trick to simplify this requirement by making all items and all
rooms 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 items
that will fit into the new apartment.
(a) The most basic model of “packing problems” like this is the so-called knapsack problem. We ignore
the 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 to
deciding for each item whether it should be used; this is subject to the capacity constraint; and we wish
to optimize the sum of the practical and the emotional value of all items that are used. Note that the
furniture 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 or
Pyomo.
(Ideally your model would be able to read the given .csv files; but you are allowed to preprocess or
transform them by hand.)
(b) The professor is concerned that he cannot fit all of his furniture items. The apartment complex offers
several identical apartment units, so the professor considers renting several units at the same time, so
that he can fit all of his furniture. He wants to know how many units he needs.
12/8/2020 Graded homework set 6 (last)
https://canvas.ucdavis.edu/courses/497959/assignments/591159 2/3
Following part (a), we ignore the geometric nature of the packing problems and only want to pack items
of 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 or
Pyomo.
Problem 2: Our personal polytopes – continued from
homework set 5
We 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 the
slice S_{i,j}, for all {i,j}. (For computing the rank of a matrix or other linear algebra tasks in this
problem, 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) that
is 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 of
the 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} such
that maximizing this objective function over the fractional no-good polytope F_{i,j} gives a fractional
optimal solution (i.e., not all coordinates are 0 or 1). (This is an LP, not a MIP!) Use AMPL or Pyomo for
demonstrating this optimal solution.
d. Change your variables x_i from real to binary. Solve the IP using the solver. Compare the optimal
solution 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 the
    slice. Solve it using AMPL or Pyomo. Compare the optimal solution to the one obtained in c) and d).
    Discuss the result.
find the cost of your paper

When Kuwait put pressure on the foreign oil companies in the late 1970s, what affect it had on the Global Oil market and politics?

Case Study instructions 1. When Kuwait put pressure on the foreign oil companies in the late 1970s, what affect it had on the Global Oil market and politics? 2. Who….

The Smartphone Industry

The module for this assignment is Applied Strategy, this assignment is about the industry analysis of the smartphone industry. You should include in an A2 poster the industry’s competitive characteristics….

Event management within the tourism industry

1/Introduction2/Discussion of Relevant Literature3/MethodologySent by 10th of November 4/Results5/InterpretationSent by the 30th of November 6/Conclusion7/References8/AppendixSent by the 15th of December