LThe mathematical model is therefore the basis of all engineering work. A mathematical model is characterized by three concepts:
- The presence of choices, to be made among a finite set (notion that can be compared to the theory of probabilities)
- A principle of constraints defining the finite set of choices
- A principle of evaluation of the available choices
Modeling a problem
The four steps in modeling an industrial problem are:
- What are the data of the problem? to collect the problem data, to understand the problem;
- How to model the problem? the three points of the decision support
- What decisions should be made? to select/place objects, to define an order or quantity, to choose an event, to perform a particular operation;
- What are the constraints of the problem? to respect abilities or precedence constraints;
- What is the objective? to maximize profit, to minimize costs or quantity;
- What is the complexity of this problem? polynomial, Np, Np-hard;
- How to solve the problem ? to design algorithms (exact vs. approximate) giving feasible / optimal solutions, to develop alternative or hybrid methods
Depending on the mathematical modeling, the model can also be used as simulation. It is then possible to see the impact of certain decisions in a context different from the one studied (like the study of sensitivity of the simplex).
Decision making involves three major phases followed by the validation phase:
- Information gathering: To examine and to identify the problem (variables, functions, values, etc.).
- Problem identification: Identification of organized goals and objectives related to an issue. To determine whether a problem exists, identify its symptoms, determine its magnitude, and explicitly define it. Some issues may arise during data collection and estimation like lack of data, inoccurate or inprecise data, bad estimation, information overload, only simulated data, etc.
- Problem classification: Problem classification is the placement of a problem in a definable category. This leads to a standard solution approach.
- Problem decomposition: Many complex problems can be divided into sub-problems. Some unstructured problems may have some highly structured sub-problems.
- Design: To construct a model that represents the system.
- To understand the problem: Modelling involves abstracting the problem to quantitative and/or qualitative forms.
- A model is constructed, tested, and validated: For a mathematical model, the variables are identified and the relationships among them are established. All models are made up of three basic components: decision variables, uncontrollable variables, and result variables. Mathamtical relationships link these components together. In a non-quantitative model, the relationships are symbolic or qualitative.
- Choice: To select a solution to the model.
- Recommendation of a solution: When the problem is solved, a solution is chosen based on the model. This one is recommended over the set of solutions.
- Evaluation of a solution: Evaluation is possible if the result variables give a quantitative solution. A preference relation over the set of solution give an order: f(a)⪯ f(b) means that f(b) is better or equal to f(a) where a, b are variables and f(.) is a mathematical function based on result variables. b is the best solution iff: f(x)⪯f(b) for any x in the set of solution.
- Implementation: To implemente a software to solve any instance of the model.
- Classic, iterative implementation: Iterative algorithms use repetitive constructs like loops and sometimes additional data structures like stacks to solve the given problems.
- Recursion: A recursive algorithm is one that makes reference to itself repeatedly until a termination condition matches.
- Logical: A logical algorithm is composed by logic component and control component.
- Deterministic or non-deterministic: Deterministic algorithms solve the problem with exact decision at every step of the algorithm whereas non-deterministic algorithms solve problems via guessing. A deterministic algorithm is an algorithm which, given a particular input, will always produce the same output.
- Exact or approximate: While many algorithms reach an exact solution, approximation algorithms seek an approximation that is close to the true solution. When it is not possible to find a best solution in human time, one can seek for an approximate solution by less complex algorithms.
- Serial, parallel or distributed: Those implementations depend of computer architectures, i.e. number of processors that can work on a problem at the same time, and how to decompose the whole process into independent processes.
- Paradigm: Brute-force; Divide and conquer; Dynamic programming; Search; Randomized; Reduction. Then we need to check the termination, correctness and completeness of the algorithm.
- Validation: To validate the software if it shows reasonable computing time and good solution.
- Best-case complexity: This is the complexity of solving the problem for the best input of size n.
- Worst-case complexity: This is the complexity of solving the problem for the worst input of size n.
- Average-case complexity: This is the complexity of solving the problem on an average. This complexity is only defined with respect to a probability distribution over the inputs. For instance, if all inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined with respect to the uniform distribution over all inputs of size n.