Mathematical modelling and problem solving

Discrete models

This module is about two related issues:


    Give examples of problems or data that can be modelled in terms of each of the following basic mathematical concepts:

    • Set: unordered collection of items.
    • Sequence: sequentially ordered collection of items.
    • Tree: branching structure with a root.
    • Graph: Structure with vertices and edges
    • Directed graph: graph where links are directed (usually represented with arrows)
    • Weighted graph: graph with a single number for each edge (can be undirected or directed)


    Consider a project with many people involved, and many tasks to do. For each task T, we know:

    • the duration: how long the task T will take; and
    • its dependencies: which tasks must be finished before T can be started.
    Several tasks can be done in parallel, but all of a task's dependencies must be finished before that task can start.

    In this problem we will consider how a directed network can be used for planning and management of such projects.

    Hint: For this problem, make up a simple example and check that your solutions give the correct answer when applied to your example.

    1. Explain how a directed weighted graph can be used to model the tasks in the project.
    2. An important question is the minimum possible time to complete the project. If I gave you a program that solves the shortest path problem, how could you use it to find the minimum time for a project?
    3. Can you also model the problem as a linear programming problem? That is, can you use a linear programming solver to find the minimum time?
    4. In practice, it may be the case that the exact duration of the tasks is not known. How can we change the model to handle this?

    I am going to attend a big conference, with many talks, all with different start times, end times and durations. At any time, there are usually several talks happening simultaneously. I have decided I want to attend as many talks as possible.

    I have the timetable for all the talks. You may assume that, if I attend a talk, then I will stay for its entire duration.

    Investigate if this problem can be modelled as any of the following standard problems:

    • shortest path
    • minimum spanning tree
    • knapsack problem
    • travelling salesman problem
    • graph coloring
    • set packing

    Description of some standard problems

    You may search for these standard problems on the web if you think it is helpful.


    Consider the following two problems:

    • SUBSET-SUM: given n integers a1, ..., an and an integer S, determine if there is a subset of {a1, ..., an} whose sum is S.
    • PARTITION: Given m integers b1, ..., bm, determine if you can divide them in two subsets with equal sum.

    These are both NP-complete problems, which are important in computer science. We know that any two NP-complete problems can be modelled as each other (or "reduced to" each other).

    1. Explain how to model the PARTITION problem as a SUBSET-SUM problem (i.e. if you have a SUBSET-SUM solver, how can you use it to solve a PARTITION problem?).
    2. (OPTIONAL) Explain how to model the SUBSET-SUM problem as a PARTITION problem. (This part is much harder!)


Do not submit an incomplete module! We are available to help you, and you can receive a short extension if you contact us.