Building a Castle with Linear Programming

On the day you planned to actually build the castle, you and your friends have to log on and off at different times (perhaps it’s a weekend or a holiday break and you have some other commitments).

• You (friend A) can’t start until 11:00 due to a late morning study session.
• Friend B has to leave after 1:00 for class and then work-study.
• Friend C has nothing scheduled today.

We want to figure out a schedule where the castle gets completed, no one gets in trouble, and we finish the castle as quickly as possible. This is a perfect job for linear programming.

Recall that in a linear program, we define decision variables which are to be determined by the solver, constraints which may not be violated, and an optimality criterion which we want to minimize or maximize.

Take a moment to reflect on and write out answers to these questions (in a file like linprog_castle.txt) before moving on—it will make the programming portion much easier. These reflections will also be graded, so doing them is strongly recommended!

1. What are the decision variables in this problem?
2. Assuming that we are starting at 10:00, and using the constants \(W\) and \(T\) from the introduction, what are the constraints on feasible solutions? Use a formal notation, i.e. a list of mathematical inequalities. Remember that we need to enforce that no one works more time than they are allowed to work and that the castle is finished by the end of the schedule.
3. In plain language, what are we trying to optimize? Are we minimizing or maximizing this quantity? This can get somewhat subtle, so be careful!

Now that we have formulated our problem, we can translate it into Python code; create a new file linprog_castle.py and follow along (it’s better if you don’t copy and paste, but type things out and read as you go). First we import our solver API, PuLP, and begin defining a function. Leave the name and arguments of this function exactly as written here. The automatic tests for this module are in test_linprog_castle.py. You can run them with python test_linprog_castle.py. Feel free to modify this file as you like to add tests, try out new examples, and so on.

import pulp

def solve_castle_1(W,T):

Now we can set up the problem:

problem = pulp.LpProblem("Castle Construction",pulp.LpMinimize)

And start defining our decision variables. PuLP uses the LpVariable constructor for decision variables, which you can call like so:

# Example
v1 = pulp.LpVariable("v1", lower_bound, upper_bound)

Note that lower_bound and upper_bound are optional, and that every decision variable in a problem needs a unique name given as the first argument to the constructor. Add declarations of decision variables (you’ll need at least “a”, “b”, and “c”) to the function you’re defining, then continue by adding your constraints. Constraints in PuLP are added onto a particular problem:

# Example
problem += v1 - v2 >= 0
problem += v1 + v2 < 100

And you can set an optimization criterion by adding some expression which is not an inequality:

# Example
problem += v2 # optimize v2
# OR:
problem += v1 + v3 # optimize sum of v1 and v3

Finish your definition of solve_castle_1; after giving all the constraints and the optimization criterion, call problem.solve() and check its result:

problem.solve()
print("Status:", pulp.LpStatus[problem.status])
print("Total duration:", problem.objective.value())
model = {}
for v in problem.variables():
    print(v.name, "=", v.varValue)
    model[v.name] = v.varValue
return problem.objective.value(), model

Finally, call your function at the end of the file; for example, assuming placing one block takes 5 seconds and we have 7,256 blocks to place:

# Example
solve_castle_1(5, 7256)

For these parameters, it should take slightly over four hours to complete the castle if everyone works together optimally. And the solver should figure that out in well under a second!

It’s good to know how long the construction job will take, but now we need to figure out how to get the glass, the wood planks, and the cobble. For this task, everyone has set aside their whole day and no one has any time conflicts. Recall that we need \(X\) cobble, \(Y\) glass panes, and \(Z\) wood planks. Also remember that friends have different tools, so we can’t treat our friends’ labor as interchangeable: you can chop trees the fastest, friend B can dig for cobble the fastest, and so on. Finally, keep in mind that glass panes and wood planks have to be processed from raw materials (and glass panes have two steps of processing: sand to glass blocks, and glass blocks to glass panes).

If you aren’t super familiar with Minecraft, this chart might come in handy. The times will be different from crafting.json, which has abstracted away some details about, for example, moving to a particular spot; please don’t worry about such inconsistencies right now.

We can assume that all the friends are proficient players and can complete any crafting operation in one second. For reference, 1 wood log can be crafted into 4 wood planks, and 6 glass blocks can be crafted into 16 glass panes.

Finally, smelting sand into glass takes ten seconds per unit of sand, and each unit of sand produces one unit of glass. The friends have a furnace already; assume a limitless supply of fuel thanks to, for example, buckets of lava. It is extremely important to note that while sand is being smelted into glass, everyone can perform other actions; in other words no one needs to stand around and wait for the furnace to finish (in fact, more sand can be gathered and piled in while some sand is being smelted). Similarly, one person can be crafting wood planks while another is harvesting wood.

At this point, let’s reflect on the problem’s structure (you can do this in a file like linprog_castle.txt). In the previous problem we had to optimize the allocation of work-seconds among three interchangeable people, and only one type of task was being performed. Now, we need to decide how much time each person spends doing each task, still minimize how long the longest-working person works. To model this problem we will need a few tricks, and this reflection should guide us through:

4. What are the decision variables in this problem? Think about how many people are working and how many distinct types of tasks we need them to do.
5. Does any part of our production process impose a lower bound on how long the construction job will take, regardless of how we allocate people? If so, what part of the job is it and what is that bound?
6. Often in modeling linear programming problems, we need to introduce auxiliary variables for things like constraints or optimization criteria. Let’s imagine we have an auxiliary variable duration; what does (2) tell us about duration? What inequalities hold between duration and the net work-time of each of our three friends? Hint: give one inequality per friend.
7. How do we measure the team’s progress towards completion for a specific task, in terms of the amount of time each person spends on each task? For each task whose completion depends upon a time allocation from (1), give a mathematical expression (a linear combination) describing how far along that task is in terms of the time assignments from (1), the table above, and \(X\), \(Y\), and \(Z\).
   • Another way to think about this question is to ask how we know we have gathered enough cobble or made enough planks—and how much sand and wood do we need for Y and Z panes and planks?
   • Feel free to introduce new constants or variables—for example, how many planks do we need? How many planks do we get per unit wood? How much sand can friend B shovel per unit time?).

There are two nice programming tricks that can help with this problem. The first is creating lists of LpVariables—and perhaps parallel lists of coefficients—and the second is the use of lpSum to add them up (lpSum is not necessary to solve this problem but it can help a little bit).

# Example
names = ["q", "r", "s", "t"]
variables = [pulp.LpVariable("v_"+varname,0) for varname in names]
# Allocate 50 units among q, r, s, t
problem += pulp.lpSum(variables) <= 50

Just like before, we’ll work in linprog_castle.py. Again, feel free to modify the test file as you like to add tests, try out new examples, and so on.

def solve_castle_2(Xcobble,Ypanes,Zplanks):
    problem = pulp.LpProblem("Get materials",pulp.LpMinimize)
    # You can define auxiliary variables and derived constants here
    # Then your decision variables (you'll need, more or less, "a", "b", "c", plus "X_task" for each X in [a,b,c] and each task in [dig, pane, plank, sand, wood]).  One called "duration" may help too!  Extra variables are also fine.
    # And your constraints
    # And finally your optimization criterion
    # Then:
    problem.solve()
    print("Status:", pulp.LpStatus[problem.status])
    print("Total duration:", problem.objective.value())
    for v in sorted(list(problem.variables()),key=lambda v:v.name):
        print(v.name, "=", v.varValue)

Again, to test it out:

# Example
solve_castle_2(4000,256,3000)

Surprisingly, this can be completed in a little under seventeen minutes; this shows how unrealistic the assumption of ignoring travel time can be! In future assignments, these assumptions will be tightened up.

8. Briefly describe three qualitatively different situations around the allocation of workers to tasks according to your encoding.
9. If you wanted to model travel times with resources in different locations, how would you need to modify your encoding?

Commit your python files and text files and proceed to intprog_planning.