modelling

Mathematical modelling and problem solving

Modelling Languages and Other Problems

NOTE Several of these problems refer back to problems in module 1. If you have not yet completed module 1 for any reason, we suggest you devote this week to completing module 1, and then complete this module later.

  1. (AMPL MODELLING LANGUAGE)

    The purpose of this problem is to introduce some advantages of using a modelling language by taking a look at AMPL, which is a modelling language for linear programming (LP), including integer linear programming. With this language we can descibe an optimization problem in a convenient way. The basic elements are still the same: variables, objective function and constraints, but a richer syntax is offered to make it easy to describe and modify also large problems. When you have descibed your optimization problem in AMPL, the AMPL system can translate your description into a raw linear programming format suitable for input to standard optimization solvers. That is all it does.

    1. Look at the following two source files which AMPL takes as input:

      Give a brief description of the meaning of each of the expressions given in the model file diet2.mod. Discuss any thoughts of your own that come up.

    2. How many variables and constraints does the LP problem being defined in these two files have?

    3. AMPL can give its output in several different formats. Here is the output produced by the above source files in MPS and LP formats, two standard formats for represeting LP problems:

      These files can then be used as input to an LP solver.

      Discuss and compare these alternatives:

      • writing an optimization problem directly in one of these standard formats;
      • producing a file in one of these formats usin AMPL;
      • using Mathematica to solve an LP problem;
      • writing a program to solve it using a standard programming language (e.g. Java, Python).

    Here are some links for detailed information and documentation about the systems and formats referred to in this question:

    You may also use Google to help you answer this problem.

  2. (CLIPS EXPERT SYSTEM SHELL)

    A much studied area in artificial intelligence has been knowledge representation, i.e. how to conveniently model facts, rules and procedures that are more complicated than what can be stored in an ordinary database, and which are maybe not so trivial to program from scratch. In this problem we will look at some small examples of rule based expert systems written for the CLIPS expert system tool.

    The purpose of this problem is to show how knowledge can be encoded in a rule based expert system, where the basic idea is to encode knowledge as a set of IF.. THEN..  production rules.

    1. Look at this example source file for CLIPS. Try to understand as much you can of the file, and summarize your findings. How did the makers of CLIPS solve this problem: How do you model knowledge (facts and rules) in a form that can be processed by computer?

      When thinking about this problem, consider the following questions in order of importance:

      1. What information is represented, and in general terms how? (the model)
      2. How can it be used? (algorithms)
      3. other details such as syntax of the language itself (least important)
      Avoid getting involved in unnecessary detail!

      Here is a sample transcript (input and output) of a session with CLIPS using this source file: 

        CLIPS> (run)


  The Engine Diagnosis Expert System

  Does the engine start (yes/no)? yes
  Does the engine run normally (yes/no)? no
  Is the engine sluggish (yes/no)? yes


  Suggested Repair:

   Clean the fuel line.

    2. (Optional, but please think about the question even if you decide not to write anything.) The CLIPS system models facts as being either true or false. How would a system work that instead tries to assign probabilities to facts? Would you expect the model used by this system to be simpler or more complicated?

    Here are some links for more information about CLIPS:

    You may also use Google to help you answer this problem.

  3. (LIFE EXPECTANCY PROBLEM)

    This problem goes into more depth with the issues discussed in the Bicycle Braking Problem in module 1, in particular part (a) of that problem.

    Assume that we wish to model life expectancy based on a database of 1000 randomly selected deceased people. For each individual 50 different attributes have been collected such as certain diseases, diseases of ancestors, weight, length, living habits, education, type of work, living location etc. The question is about finding a function predicting the life expectancy of an arbitrary person.

    1. First consider a multidimensional linear model, i.e. f(x1,x2,…, x50) = c + a1 x1 + a2 x2 + … + a50 x50. Would the data be sufficient to fit such a model? Can the least squares method be used? How good do you think the model would be? Motivate your answers. Hint: be sure you a clear what a multidimensional linear function is before you try to answer these questions. If you need, ask!
    2. What about a quadratic model? (i.e. a quadratic polynomial)
    3. Can you propose some other way(s) to find good and useful models? Any particular difficulties you come to think of?
    4. (Optional) What about using a machine learning algorithm or neural network? Would you expect it to work better than other more standard approaches? Any other methods you could think of? (No long answer is expected for this question. If you do not know much about machine learning, feel free to use your intuition and write down what your expectations would be.)

  4. (EXPECTED INFORMATION PROBLEM)

    This problem sheds a little more light on the purpose of the "surprise" function from the first module. Recall the formula for the amount of information we receive when we learn that something with probability p has happened. (If you do not recall this formula, please ask a supervisor.)

    We are reading a binary file, one bit at a time. Suppose that, each time, the probability that the next bit is a one is p1, and the probability that it is a zero is p0 = 1-p1. Let I(p1) be the expected (average) amount of information carried by a bit in the file.

    Find a formula for I(p1). What is the value of this function for p1 = 0.0, 0.1, 0.5, 0.9, 1.0? Plot the function.

  5. (RESTAURANT PROBLEM)

    Person A wants to avoid person B, who insists on meeting A at lunchtime. At the university there are two restaurants, a regular one (dining time 20 min), and a fancy one (dining time 50 min). For simplicity, we assume that, at 12.00 each day, A and B each choose a restaurant and go to lunch; they never choose not to eat, and they do not change their choice of restaurant that day.

    What strategy should A use to choose a restaurant in order to minimize the time spent with B? What strategy should B use to maximize the amount of time spent with A? If they both choose the optimal strategy, how much time do they spend together per day on average?

    Hint: Spend some time thinking about the problem intuitively before you start trying to solve it mathematically.

SELF-CHECK