March, 2009

Posts
  • Nathan Brixius

    Simple matrix, vector, permutation utilities

    • 1 Comments

    Thanks for visiting! I have moved my blog. An updated version of this post can be found here.

  • Nathan Brixius

    Branch-and-bound algorithms for QAP

    • 3 Comments

    Thanks for visiting! I have moved my blog. An updated version of this post can be found here.

  • Nathan Brixius

    Project Scheduling and Solver Foundation: links and constraints

    • 2 Comments

    Yesterday I introduced a simple OML model for computing project schedules.  The model has the following sections:

    • Parameters: input data that comes from Excel.
    • Decisions: the values that I want to solve for.
    • Constraints: the relationships that decisions and parameters need to satisfy.
    • Goals: the objective - what I want to optimize.

    The exciting cliffhanger from my previous post was to model precedence links.  Let's think about how I could specify the links in Excel.  One way to do it is to have a table that simply lists the "predecessor" and "successor" tasks.  For example:

    Pred Succ
    0 1
    1 2

    The first row says that task 0 is the predecessor of task 1, i.e. task 1 should start after task 0 finishes.  If we want to bind this data to our model, we should introduce a Set and a Parameter, just like we did for Tasks:

      Parameters[Sets, Links],
      Parameters[Integers, Pred[Links], Succ[Links]],
    

    The domain for Pred and Succ is Integers because the table stores indexes for the tasks.  Now I need to change the model to enforce the links.  That's a constraint, which is expressed straightforwardly using a Foreach:

        Foreach[{l, Links}, Start[Succ[l]] >=Finish[Pred[l]] ]
    

    If I setup the data binding for Links and re-solve, then I will see that the links are honored.  If you compare to Project's schedule, you may spot a problem: some of the tasks (for example t3) are scheduled later than they are in Project.  This is totally valid according to our model - t3 has "slack" and can move around without affecting the project schedule.  Think about how you could fix up the model to match Project, so that all tasks are scheduled "as soon as possible".

    On to the "extra credit" problem: how to model "start no earlier than" (SNET) constraints.  This is actually not too hard if we just consider the SNET date to be another parameter just like Duration.  The constraint is straightforward:

      Parameters[Reals, SNET[Tasks]],
      Constraints[ Foreach[{t, Tasks}, Start[t] >= SNET[t] ]]
    

    In my Excel spreadsheet, I added a SNET column with the date for the constraint for each task.  If a task does not have a SNET constraint, I just fill in a dummy date (e.g. 1/1/2009).  But I need a number, not a date, so in the adjacent column I add the formula "=C2-TODAY()" to give me the number of days since the project start date.  That's what I want to bind to.

    For reference, here is the data in my spreadsheet:

    Excel data 

    And here are the data bindings I created using the "Binding" button in the Solver Foundation ribbon:

    OML data binding 

    If you've been working with the spreadsheet, you may have been annoyed by a couple of things:

    • If I add new tasks, I need to change the data binding to include the new cells.
    • The conversion between dates and numbers is kind of bothersome.
    • This is getting complicated.  For example, Project has eight different constraint types.  If I wanted to model them all the same way I modeled SNET, I would need to add a whole bunch of spreadsheet columns. 

    Maybe it's time to turn this OML model into a C# program that directly calls Solver Foundation Services to model and solve project schedules.  Next time we will do just that.

  • Nathan Brixius

    Project Scheduling using Solver Foundation

    • 4 Comments

    I'd like to work through a few examples of how to model real problems using Solver Foundation.  If you download the Solver Foundation Express Edition, you can follow along: start Excel, click the Solver Foundation tab, then click on the Model button to get a blank modeling pane.

    I spent my first five years at Microsoft on the Project team, writing the project scheduling engine for Project Server.  Project is a great team and an awesome product, and I still have a soft spot for project scheduling.  My intent is not to reinvent Project - just to make a connection with a familiar problem so I can show off the Solver Foundation platform while introducing some key concepts. For those who don't know Project, the goal is to come up with a schedule for a list of tasks in a project.  Here are a few of the basics:

    • Tasks have a start, finish, and duration.
    • No task starts before a given project start date.
    • The finish date is computed as start + duration.
    • A pair of tasks can be linked by precedence relationships.  When there is a link from a task A to a task B, the B's start must occur on or after A's finish date.
    • The project finish date is defined as the latest finish date of any task in the project.

    Given these requirements, we would like to compute the start and finish dates for all of the tasks in the project, and we want to find a schedule ends as soon as possible.  Let's use the Solver Foundation to create a model in OML (Solver Foundation's declarative language) and compute some schedules.  I always find it helpful to work out an example before I try and model a problem.  Here's a simple schedule in Project with five tasks, and two links that connect t0, t1, t2.  To compute the schedule by hand I could use a simple critical path scheduling algorithm.

    A simple project 

    Right away you can spot a few issues:

    • I haven't taken calendars into account - normally I don't want to schedule work on Saturdays and Sundays.
    • I haven't taken resources into account - in real life, people (or machines, or rooms) are assigned to work on tasks, and their availability may affect my schedule.
    • There are lots of cool Project features that I haven't taken into account - e.g. task constraints, summary tasks, etc.
    • I haven't taken uncertainty into account - in real life, durations aren't known precisely.

    I will revisit some of these points in future posts - these are all things that I can address with Solver Foundation.  For now, I am going to stick with a simple version of the problem.  I'd rather get a correct model on a simplified version of the problem than an incorrect model on a more complex one!  In this sense, modeling is no different from writing an essay or designing software.

    There are a few questions to ask yourself when building an OML model:

    • What are the key objects or entities that I will be working with? (tasks, links)
    • What do I want the solver to compute? (start and finish dates for tasks)
    • What do I know?  (the durations on the tasks)
    • What are my restrictions? (links enforce an ordering on tasks, start + duration = finish)
    • What do I want to optimize? (the finish date on the project)

    If you have good answers to these questions, and start simple, you can usually come up with an OML model that describes the problem.  Let's start by modeling the start and finish dates of the tasks, since that is ultimately what we want to find out.  Each task has a start and a finish - these are dates.  Solver Foundation does not directly support date values, so let's say that start and finish are real numbers, representing the number of days since the project start date.  To express the idea that each start and finish is associated with a task, we define a "set" Parameter.  The start and finish dates are the values that we want the solver to figure out, so these are Decisions:

    Model[
     Parameters[Sets, Tasks],  
     
     Decisions[
         Reals[0, Infinity], Start[Tasks], Finish[Tasks]
      ],
    

    Notice the syntax for Decisions: the first argument indicates the possible values (domain) for the decisions.  We could have used Integers[0, Infinity] for the first argument, but then we would not be able to model fractional days. Loosely speaking, the start and finish dates are the "output".  What's input?  The durations.  Let's suppose that the durations are entered into our spreadsheet like this:

    Task Dur
    t0 1
    t1 2
    t2 3
    t3 2
    t4 4

    We will define Duration as a Parameter so that we can use data binding to determine the values.  Just like Start and Finish, Duration is indexed by Task. 

    Parameters[Reals, Duration[Tasks]],

    After entering the duration data into Excel I can use the Binding button to add a binding from the range B2:B6 to Duration.  When I solve the model, Solver Foundation will use whatever values are entered in the spreadsheet.  But let's not get ahead of ourselves...next let's express the relation between Start, Finish, and Duration.  Relationships that need to be enforced are described using Constraints.  OML provides a bunch of operators and expressions for describing constraints.  In this case, we have one constraint per task.  This is easy to express using Foreach:

     Constraints[
        Foreach[{t, Tasks}, Start[t] + Duration[t] == Finish[t] ]
     ] 
    

    We almost have a working model - the last thing we need to express is our Goal: that we want the project to finish as soon as possible.  So let's introduce ProjectFinish as another decision:

     Decisions[
         Reals[0, Infinity], Start[Tasks], Finish[Tasks], ProjectFinish
      ]
    

    The ProjectFinish is the maximum finish date of any task in the model.  In other words, it is at least as big as the Finish date of each task, so we add this constraint.

      Foreach[{t, Tasks}, ProjectFinish >= Finish[t] ]
    

    Now we can express our goal: minimize the project finish:

      Goals[ Minimize[finish -> ProjectFinish ] ]
    

    The "->" syntax simply gives a label to our goal, it's optional.  Here's the complete model:

    Model[
      Parameters[Sets, Tasks],  
      Parameters[Reals, Duration[Tasks]],
    
      Decisions[
         Reals[0, Infinity], Start[Tasks], Finish[Tasks], ProjectFinish
      ],
    
      Constraints[
        Foreach[{t, Tasks}, Start[t] + Duration[t] == Finish[t] ],
        Foreach[{t, Tasks}, ProjectFinish >= Finish[t] ],
      ],
     
      Goals[ Minimize[ finish -> ProjectFinish ]  ]
    ]
    

    If you have entered this into the modeling pane, and used the Binding button to define the data binding between the spreadsheet data and Duration, you can hit Solve and observe the Start and Finish dates.  You will see something like this:

    Solver Foundation Results 

    If you want to turn the starts and finishes into dates, you can enter a formula like "=now() + C5" in the adjacent column.  Actually I put this formula in a column next to my duration values, so I can see the durations, starts, and finishes all in one place.

    You should be thoroughly unimpressed by this model (as I am ;)), because it doesn't do all that much.  All I'm doing is letting Solver Foundation compute finish = start + duration, which I could have done very easily in Excel.  I need to model "links": a link causes the start date of the successor task to be later than the finish of the predecessor task.  If you've made it this far, you have all the building blocks you need to model this in OML.  Feel free to post your solution here, or just wait until tomorrow for my solution.

    Extra credit: if you use Project, you know that you can define "constraints" on tasks.  For example, I can double click on a task and say that a task must "Start No Earlier Than March 30, 2009".  These constraints need to be honored, in addition to links.  How can I model SNET constraints using OML?

     

Page 1 of 1 (4 items)