Mathematical modelling and problem solving

Discrete models

This module is about two related issues:

• How discrete mathematical concepts are used as basic model types.

• How problems can be modelled as standard problems. We use the terminology "model a problem (of type) A as a problem (of type) B" to mean the following. Given a problem A, we do not try to solve it directly. Instead, we construct a problem B in such a way that the solution to B will tell us the solution to A.

  We can imagine that we are given a "black box" that solves problem type B. We are not allowed to open it up to see how it works; all we can do is feed it a problem of type B, and get the solution. But by modelling problem A as problem B, we can use the black box to solve A, even though it was not designed to do this!

  You met this idea in the last module, when we asked you to solve (e.g.) the network flow problem as a linear programming problem. We considered Mathematica as a "black box" that solves LP problems, and used it to solve the network flow problem.

1. (USING BASIC DISCRETE STRUCTURES)

   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)

2. (PROJECT PLANNING PROBLEM)

   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?

3. (CONFERENCE PROBLEM)

   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.

4. (SUBSET_SUM AND PARTITION PROBLEM)

   Consider the following two problems:

   • SUBSET-SUM: given n integers a₁, ..., a_n and an integer S, determine if there is a subset of {a₁, ..., a_n} whose sum is S.
   • PARTITION: Given m integers b₁, ..., b_m, 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!)

SELF-CHECK

• Have you answered all questions to the best of your ability?
• Is all the required information on the front page, is the file name correct etc.? (See here)
• Anything else you can easily check? (details, terminology, arguments, clearly stated answers etc.?)

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