1 Introduction

We use programming languages to formulate problems in order to deal with them by computers. At the same time, we want these languages to be readable for human beings. In fact, the emergence of computers has created a systematic way in which problems are formulated as computations. We now frequently make use of this mould even if computers are not involved. Problem formulation as a computation has a long tradition. The ancient Babylonians (19th–6th century B.C.), who had the most advanced mathematics in the Middle East, formulated all their mathematical problems as computations. They easily handled quadratic and even some cubic equations. They knew many primitive Pythagorean triples. They mastered the calculation of the volume of the truncated pyramid and many more impressive computations [10, 13]. Arithmetics was highly developed to ensure their calculations for architectural and astronomical purposes. On the other hand, we cannot find a single instance of what we nowadays call a proof using symbolic variables and constraints. Only the process of the calculation – today we may say the procedure or the algorithm – was described. In this sense, the Babylonian mathematicians were in fact computer scientists. To illustrate how they did mathematics, one can consult the examples in [6]. This is in contrast with the Greek mathematicians who were interested in why things are true and less how things are calculated. The Babylonian and Greek approaches of acquiring and writing down knowledge are two fundamental different paradigms of knowledge: algorithmic knowledge and mathematical knowledge. This is the subject of this paper and how to represent the knowledge in programming or modeling languages.

2 Algorithmic Knowledge

As already mentioned, algorithmic knowledge has been used already by the Babylonians presented as written texts. We use algorithmic knowledge in our daily life in many situations, for instance, when we are preparing a recipe to cook spaghetti :

  function CookSpaghetti() { 
 
    Peel_Onions() 
 
    ...   // various other tasks 
 
    while (not Spaghetti_are_aldende) do Continue_cooking() 
 
    ... 
 
    // finally 
 
    repeat 
 
      Serve_a_plate() 
 
    until all_plates_have_been_served 
 
  }

In computer science we use programming languages to implement algorithmic knowledge in order to be executed by a computer. Various language paradigms have been developed since the first computer appeared: imperative, functional, and logic programming.

The imperative programming paradigm is closely related to the physical way of how (the von Neumann) computer works: Given a set of memory locations, a program is a sequence of well defined instructions on retrieving, storing and transforming the content of these locations. At each moment, the state of the computation can be represented by the momentary content of the memory locations (its memory-variables), instruction pointer and other register contents. At each step of the computation this state changes until the desired result (the goal state) is obtained, where the computation stops. The explicit notation of a sequential execution, the use of memory-variables (symbolic names) representing memory locations, and the use of assignment to change the values of variables are the characteristic building block of each imperative language. The imperative programming approach itself can be split into various sub-paradigms: (1) “spaghetti coding”, (2) structured-procedural, and (3) object oriented programming.

(1) ”spaghetti coding” consists of a linear list of instructions (eventually containing goto’s (jumps) and if’s, for branching). The recipe above is a typical example. The code is not structured. Programming languages like Assembler or Basic favoured such an approach. In large software project today this approach is difficult to maintain. Assembler may be used still within other languages when a code must run efficiently, but in the light of better compilers this approach is becoming marginal. Higher level languages, like Basic, have almost completely vanished.

(2) Structured and procedural programming emphasizes the need that for larger projects one should break down the whole code into several more or less independent units, modules, packages, records, procedures and functions. This makes the code more maintainable and secure. The languages C and Pascal are prominent advocates of this approach. These languages also introduced the concept of type: Each variable is (implicitly or explicitly) attached to a type which is a defined data-structure template in memory. A type like “int” in C, for instance, consists of a given memory state and size (typically 4-bytes) together with a set of operations on its data (addition, subtraction, etc.). Additional data-structures can be declared by the programmer using records or struct and loosely coupled functions are implemented to manipulate these structures.

(3) Object-oriented programming, extends the concept of type: The user (programmer) can add new “types” called “classes” which consists of fields and tightly coupled methods (functions). Like in types, the fields are the memory state and the methods are the operations. The classes can be instantiated as objects, the correspondents to variables. Classes have many interesting features: Encapsulation structure and methods (hide them from outside), polymorphism and overriding (use the same procedure name for different types), hierarchy of classes, etc. Important representatives are languages Java, C++, Object Pascal.

Functional programming is in a sense opposite to imperative programming, where no states exist. The computation in functional programming is based on the evaluation of functions. Every program (i.e. computation) can be viewed as a function which translates an input into a unique output. Hence, a program can be represented by the function I f -→O, I being the domain of input, O being the domain of output, and f being the computation. A distinction is made between function definition, which describes how a function is to be computed, and function application, which is a call to a defined function. Since every value can be expressed as a function, there is no need to use explicitly variables, i.e. symbolic names for memory locations, nor do we need the assignment operation. Loops in the imperative programming languages are replaced by (tail) recursion. Furthermore, functions are first-class values, that is, they must be viewed as values themselves, which can be computed by other functions. The computational model of functional programming is based on the λ–calculus invented by Church A. (1936) as a mathematical formalism for expressing the concept of a computation; this was at the same time as Turing invented the Turing machine for the same purpose. One can show that the two formalism are equivalent in the strict sense that both can compute the same set of functions – called the computable functions. We call a programming language Turing complete, if it can compute all computable functions. With respect to functional programming we have the important result that: “A programming language is Turing complete if it has integer values, arithmetic functions on these values, and if it has a mechanism for defining new functions using existing functions, selection, and recursion.” [15, p. 12].

Logic programming emerged in the 1960s, when programs were written that construct proofs of mathematical theorems using the axioms of logic. This led to the insight that a proof can be seen as a kind of computation. But it was realised soon that also the reverse is true: computation can also be viewed as a kind of proof. This inspired the development of the programming language Prolog. In Prolog, a program consists of a set of (Horn)-rules together with at least one goal. Using the backtracking algorithm which consists of resolution and unification, the goal is derived from the rules. A logic programming language can be defined as a “notational system for writing logical statements together with specified algorithms for implementing inference rules.” [15, p. 426]. The unification-resolution algorithm is quite limited and has been replaced by various constraint solving mechanisms in the constraint logic programming, a modern extension of the logic programming class [14].

The functional and logic programming classes are sometimes called declarative in computer science. There are problem classes for which a declarative representation can be used directly to compute a solution, if interpreted in a certain way. A famous example is the algorithm of Euclid to find the greatest common divisor (gcd) of two integers. One can easily show that :

This is clearly a declarative way, since it defines the gcd. However, the formulation can directly be used to implement a functional (recursive) program of finding the gcd, when the logical equivalence ≡ is interpreted as "can be substituted by". The underlying mechanism in a functional programming language is: "substitute the head of a function by its body recursively and simplify". The interpretation is essential, because it alone allows the underlying algorithm to be applied to the definition. Coded in a functional language (here Scheme) the algorithmic formulation of Euclid’s algorithm is as following:

  (define (gcd a b)
    (if (= b 0) a
      (gcd b (remainder a b))))

This paradigm of recursion is extremely powerful for designing algorithms. Hoare [11] wrote that he had no easy way to explain his Quicksort before he was aware of the recursion in Algol 60.

All problems, for which the instances can be reduced to smaller instances until finding a trivial (non-reducible) instance, can be treated in this way. This class of problem is surprisingly large and sometimes even more efficient algorithms can be discovered using this method. There are textbooks in algorithmic entirely based on this paradigm, an example is [21].

The case is similar in logic programming, which also is called declarative. In mathematics, the square function can be defined (declaratively) as:

In Prolog the rule can be implemented as :

   Sqr(X,Y) :- Y = X*X.

The query

   ? :- Sqr(X,7).
                                                                                       
                                                                                       

will eventually return the answer {X = 49}, since it is easy to multiply Y *Y (7 * 7) and to bind X to 49. If however the query

   ? :- Sqr(49,Y).

is made then the interpreter may not return a result, because it does not know what the inverse operation of squaring is. In a constraint logic language, the interpreter may or may not return a result, depending on whether the square root is implemented as an inverse of the square operation. This is but a simple example, but it shows an essential point: the logic program is declarative only in one direction, but not in the other, except when implementing explicitly the inverse into the system. This situation is similar in functional programming. The function (in Scheme)

   (define (Sqr y)
      (* y y))

solves the problem: “given y find (Sqry)”. The inverse problem, however, which is implicitly also part of the mathematical definition, would be: “given the body (*yy), which evaluates to a single value, find the value of y”. This second problem cannot be solved using the functional definition. To find the square root, one needs an entirely different algorithm, e.g. Newton’s approximation formula:

In an algebraic modeling language (see below), such as LPL one can write:

   variable x; y; constraint R: y*y = x; y=7;

or

   variable x; y; constraint R: y*y = x; x=49;

The problem specification is valid in both directions and does not change, regardless of what are known and what are unknown quantities. By the way, a clever modeling language (which is not the case for LP L ) would reduce the first model immediately to {y = 7,x = 49} using only local propagation; the second model would be fed to a non-linear solver which eventually applies a gradient search method, for which Newton’s approximation is a special case.

The main point here is, that an algorithmic formulation of a problem assumes an (explicit or implicit) underlying mechanism (algorithm) for solving the problem, while a mathematical formulation (see below) does not assumes such a mechanism. In this sense, problems formulated in either a functional or a logic programming language represent the problem in an algorithmic way, while algebraic modeling language only formulate the problem in a mathematical way, without indicating how to solve it.

This last example discloses a whole other class of problems that can also be formulated in a declarative way: the mathematical models. A more complete example is a linear program, which can be represented declaratively in the following way:

From this formulation – in contrast to the recursive declarative definitions above – nothing can be deduced that would be useful in solving the problem. However, there exists well-known methods, e.g. the Simplex method, which solves almost all instances in a very efficient way. Hence, to make the declarative formulation of a linear program useful for solving it, one needs to translate it into a form the Simplex algorithm accepts as input. A commercial standard formulation is the MPSX format [12] (see also Wikipedia. The translation from the declarative formulation {min  cx∣Ax ≥b} to the MPSX-form can be automated and is an essential task of the algebraic languages (see below).

All three programming paradigms (imperative, functional, and logic programming) concentrate on problem representation as a computation. Modern programming languages, like Python, JavaScript, etc., are typically multi-paradigmatic. The computation on how to solve the problem is the representation. We may call a notational system, that represent a problem by writing down its computation to find a solution, an algorithmic language. In this sense, all (three) presented programming classes consist of algorithmic languages.

Definition: An algorithmic language describes (explicitly or implicitly) the process (the computation) of solving a problem, that is, how a problem can be processed using a machine. The computation consists of a sequence of instructions which can be executed in a finite time by a Turing machine. The information of a problem which is captured by an algorithmic language is called algorithmic knowledge of the problem.

Algorithmic knowledge to describe a problem is so common in our everyday life that one may ask whether the human brain is “predisposed” to preferably look at a problem in describing its solution recipe (computation). Are we in fact predominantly using “algorithmic thinking”? (see also [7]).

3 Mathematical Knowledge

Formulating a problem by writing down its computation for solving the problem is one way of representing it and many problem are preferably formulated this way – we’ll see later why. It is the algorithmic knowledge of the problem solution that is described, it is the Babylonian way of problem representation. There exists another way to capture knowledge about a problem – it was already mentioned (example Linear Programming, above); it is the way to define what the problem is, rather than saying how to solve it. How can we say what the problem is? By defining the properties of the problem. Mathematically, the properties can be described as a feasible space which is a subset of a well-defined state space. Let X be a continuous or discrete (or mixed) state space (IR^m ∪ INⁿ) and let x be an arbitrary element within X (x ∈X), then a mapping R : X →{false,true} defines a subset Y of X. This is often written as Y = {x ∈X∣R(x)}. Mathematical and logical formula can be used to specify the mapping R. These formula are called constraints. The unknown quantities x in {x∣R(x)} are called variables. The expression Y = {x ∈X∣R(x)} is also called a mathematical model for the problem at hand. A notational system that represents a problem by writing down its properties using a state space is called a mathematical language.

Definition: A mathematical language describes the problem as a set of properties that can be expressed as a subset of a given state space. This space can be finite or infinite, countable or non-countable. The information of a problem which is captured by a mathematical language is called mathematical knowledge of the problem.

A mathematical representation of a problem is extremely powerful and applicable for a very wide range of problems. A constraint expression can be built of all kind of mathematical and logical operations and functions to cover linear, non-linear, discrete or Boolean expressions. One can extend this notation to include special constraints (SOS), global constraints (a concept from constraint programming) (for example Alldiffenent), or special variables (for example permutation variables, see my paper on permutation problems [19]). A complex problem can often be formulated in a very concise and readable way. Concise writings favours the insight to a problem: we can look at the formulation and grasp the essential “at a glance”. The following statement

for example, gives us a concise definition of what the Bernoulli number B_n are [9, p. 285], namely the coefficients of this power series, in a way that we almost can “see” them, without knowing their actual values.

Nevertheless, a mathematical model has a big downside: it does not give any indication on how to solve it with the exception of fully enumerate the whole space and checking for each x whether R(x) is true or false, but enumerating the space X is out of question for any realistic problem. There does not exist a unique method (algorithm) to solve all mathematical models. Even worse: Seemingly harmless problem can be arbitrarily difficult to solve. The problem of finding the smallest x and y such that {x,y ∈ IN∣x² = 991y² + 1}, is a hard problem, because the smallest numbers contain 30 and 29 digits and apparently no other procedure than enumeration is known to find them. There are even problems that can be represented in a mathematical way, but cannot be computed. The problem of enumerate all even integers {x ∈ IN∣2x ∈ IN}, for example, cannot be computed, because the computation would take an infinite time. The problem of printing all real number within a unit circle {x,y ∈ IR∣x² + y² ≤ 1} is even not enumerable. It is well-known, to give a nontrivial example, that the set of theorems in first-order logic, a restricted subset of classical logic, is undecidable (not computable). This can be shown by reducing the halting problem to the problem of deciding which logical statements are theorems [8, p. 520]. These examples simply have the shattering consequence: Given an arbitrary mathematical formulation of a problem, we can even not say in the general case whether the problem has a solution or not. The algorithmic way, on contrast, is a precise sequence of instructions (a recipe) of finding the solution to a given problem. For well designed algorithms, the sequence will terminate and we can even – for most algorithms – calculate an upper bound of its execution time – which is called its complexity.

So, why would we like to represent a problem mathematically, since we must solve it anyway and, hence, represent it finally as an algorithm? The reasons are documentation – besides conciseness and insight. In many scientific papers which deal with a mathematical problem and its solution, the problem is stated in a mathematical way for documental purposes. However, documentation is by no means limited to human beings. We can imagine an mathematical language implemented on a computer which is parsed and interpreted by a compiler. In this way, an interpretative system can analyse the structure of a mathematical program, can pretty-print it on a printer or a screen, can classify it, or symbolically transform it in order to view it as a diagram or in another textual form. There is a whole bunch of tasks we can execute using the computer for mathematical knowledge, besides solving the problem (see [18] for more details).

Of course, the burning question is, of whether the mathematical way of representing a problem could be of any help in solving the problem. The answer is yes and no. Clearly, the mathematical representation {x ∈X∣R(x)}, in its general form, does not give the slightest hint on how to find such a x. Problems represented in this way can be arbitrary complex to solve as seen before.

In practice, however, we are not so badly off. There exists problem classes, even with an infinite state space, which can be solved using general methods. An example is linear programming (as seen) and other classes of non-linear models. Great progress has been made in the last decades of discrete problems, more about them later on.

4 Historical Notes

Declarative and demonstrative mathematics originated in Greece during the Hellenic Age (as late as ca. 800–336 B.C.). The three centuries from about 600 (Thales) to 300 B.C. (Elements of Euclid) constitute a period of extraordinary achievement. In an economical context where free farmers and merchants traded and met in the most important marketplace of the time – the Agora in Athens – to exchange their products and ideas, it became increasingly natural to ask why some reasoning must hold and not just how to process knowledge. The reasons for this are simple enough: When free people interact and disagree on some subjects, then one asks the question of how to decide who is right. The answers must be justified on some grounds. This laid the foundations for a mathematical knowledge based on axioms and deductions. Despite this amazing triumph of Greek mathematics, it is not often realised that much of the symbolism of our elementary algebra is less than 400 years old [10, p. 179]. The concepts of the mathematical model as a declarative representation of a problem, are historically even more recent. According to Tarski, “the invention of variables constitutes a turning point in the history of mathematics.” Greek mathematicians used them rarely and in a very ad hoc way. Vieta (1540–1603) was the first who made use of variables on a systematic way. He introduced vowels to represent variables and consonants to represent known quantities (parameters) [10, p. 278]. “Only at the end of the 19th century, however, when the notion of a quantifier had become firmly established, was the role of variables in scientific language and especially in the formulation of mathematical theorems fully recognized” [4, p. 12].

It is interesting to note that this long history of mathematics with respect to algorithmic and mathematical representation of knowledge is mirrored in the short history of computer science and the development of programming languages. The very first attempt to devise an algorithmic language was undertaken in 1948 by K. Zuse [17]. Soon, FORTRAN became standard, and many algorithmic languages have been implemented since then.

The first step towards a declarative language was done by LISP. LISP is a declarative but not a mathematical language, since a function I f -→O can only be executed in one direction of calculation, from I to O. However, an important characteristic of a mathematical language is the symmetry of input and output. Prolog was one of the first attempts to make use of certain mathematical concepts, since a Prolog program is a set of rules. Unfortunately, besides of other limitations, the order in which the rules are written is essential for their processing, showing that Prolog is not a mathematical language either. But Prolog had an invaluable influence on the recent development of constraint logic programming (CLP). Unfortunately, a constraint language normally come with its own solution methods based on constraint propagation and various consistency techniques and the modeling part and solution process are so closely intermingled that it is difficult to “plug in” different solvers into a CLP language. However, this is exactly what is needed. Since a general and efficient algorithm for all mathematical problems is unlikely, it is extremely important of being able to link a given mathematically stated problem to different solver procedure. The solution and formulation process should be separated as much as possible.

In logic programming, the underlying search mechanism (its computation) is behind the scene and the computation is intrinsically coupled with the language. This could be a strength because the programmer does not have to be aware of how the computation is taking place, one only writes the rules in a descriptive way and triggers the computation by a request. In reality, however, it is an important drawback, because, for most nontrivial problem, the programmer must be aware on how the computation is taking place. To guide the computation, the program is interspersed with additional rules (cut a.o.) which have nothing to do with the description of the original problem. This leads to programs that are difficult to survey and hard to debug and to maintain. This problem is somewhat relieved by the constraint logic programming paradigm, where specialized algorithms for different problem classes are directly implemented in the underlying search mechanism. However, this makes the language dependent of the implemented algorithms and problems that are not solvable by one of these algorithm cannot easily be stated in the language.

In the 80’s and 90’s of the last century, a new kind of mathematical languages, namely algebraic modeling languages, emerged in the community of operations research. The fact that a single method (for instance the Simplex method) can solve almost all linear programs, led to the development of these algebraic languages (such as GAMS, AMPL, LINGO, LPL a.o.), which have been becoming increasingly popular in the community of operations research. Algebraic modeling languages represent the problem in a purely mathematical way, although the different languages include also some computational facilities to manipulate the data. The mathematical notation itself of a model give no hint on how to solve the problem, it is stated in purely declarative way. Therefore, all algebraic modeling language must be linked to “solvers”, that is, mathematical libraries or programs that can solve the problem, for example, Gurobi, Cplex, XPress, HIGHS, etc. Many of these algebraic languages can also formulate non-linear problems, or some elements of constraint programming. They also include some methods to generate derivatives in order to link the model to non-linear solvers, like Knitro, IPOPT, etc. Typically, an algebraic modeling language has an interface to many different (free and commercial) solvers.

One of their strength is the complete separation of the problem formulation as a mathematical model from the solution process. This allows the modelers not only to separate the two main tasks of model formulation and model solution, but also to switch easily between different solvers. This is an invaluable benefit for many difficult problems, since it is not uncommon that a model instance can be solved using one solver, and another instance is solvable only using another solver. Another advantage of some of these languages is to separate clearly between the mathematical model structure, which only contains parameters (place-holder for data) but no data, and the model instance, in which the parameters are replaced by a specific data set. This leads to a natural separation between model formulation and data gathering stored in databases and other data sources. Hence, the main features of these algebraic languages are:

1. Mathematical representation of the problem,

2. Clear separation between formulation and solution,

3. Clear separation between model structure and model data.

Algebraic modeling languages are limited in the sense that by definition no algorithm can be written using their notation. This is an important disadvantage and has led in the recent years to the advent of various packages in modern multi-paradigm programming languages. Especially in the Python community, several (mostly free) packages that allow to formulate mathematical models are increasingly popular at least in an academic context (for instance GurobiPy, Pyomo, PuLP, Python-MIP, APMonitor, a.o.). Also commercial companies are more and more switching to this approach of optimization problems. In some of these packages one can even switch easily between various solvers. The programming language Julia has a more unified approach with the package JuMP. Often the solver libraries offer themselves an interface to various programming languages (Python, C++, R, MatLab), to formulate the mathematical model (Gurobi, OR-tools, MiniZinc, CVXOPT, Knitro, etc.).

Indeed some commercial companies have developed their own mathematical modeling languages (AIMMS, MOSEL, HEXALY) that include some algorithmic features, but most of them are attached to their own exclusive solvers.

Let’s recap the different programming language paradigms: Algorithmic knowledge can be implemented in various flavours and many programming languages have been created, they can be imperative or declarative. Most modern languages are multi-paradigmatic: In Python or JavaScript, for instance, one can program in a functional or in an object-oriented style.

Table 1 give an overview of the different programming paradigms.

5 Combine mathematical and algorithmic knowledge

Most problems can be formulated in several ways. Especially, a problem can be formulated using either algorithmic or declarative knowledge alone, or a combination of both. The question is of which is the most appropriate way. This depends on many criteria, such as efficiency, modifiability, extendability, readability, modularity, portability and others. It turns out that these criteria are exactly what in software engineering [2, 3, 1] is called software quality criteria. The main thesis of this paper is:

Thesis: With respect to these criteria, some problems are best formulated in a mathematical way, others in an algorithmic way, still others as a combination of both.

This thesis is now corroborated by some examples.

5.1 The Sorting Problem

Sorting an array of data is an important task in many contexts of data manipulation. Mathematically, the problem could be formulated as a permutation problem (see [19]). Let Π be the set of all permutations of some length n and let π be any permutation in Π. Let also π_i the i-th element within the permutation π, then the problem of (descending) sorting an array a_i could be formulated as an optimization problem (find a permutation π ∈ Π such that ∑ _iⁿ ia _πi is minimal):

This is a very elegant and short way to formulate the sorting problem, but is it a useful or efficient way? Not really, this formulation is in the same category as the TSP (traveling salesman problem) which can also be formulated as a permutation problem and which is NP-complete (find a round trip of minimal distances defined in a distance matrix c_i,j) :

The question then is, how to find such a permutation. This is not an easy task. One could apply a general meta-heuristic, such as Tabu-search with a 2- or 3-opt neighbourhood to find nearly optimal permutations. However, this technique is only applicable for small instances and does not necessarily deliver an optimal solution. But why using this approach for sorting? We know that sorting is an “easy” problem: There exists efficient algorithms (Heapsort, Mergesort) that have a complexity of O(n log n). Even simple approaches such as Bubblesort can be implemented in a few lines of code in any programming language. So, while the mathematical approach seems elegant, it is neither practical nor efficient. The sorting problem is definitely better formulated as an algorithm.

5.2 The 0-1 Knapsack Problem

A 0-1 Knapsack problem is explained in a knapsack model. Let i ∈I = {1,…,n} be a set of items. Each item i has a value w_i. We want to find a subset of items such the sum of values of its items is exactly K.

This problem can be formulated as a recursive function (dynamic programming!) as follows :

Using memoizing, this recursive function can be implemented with complexity of O(nK).

The previous algorithmic approach is a perfect acceptable way to formulate the Knapsack problem. Probably a wider used approach is to formulate this problem as an integer linear mathematical model and using mixed-integer solvers (like Gurobi) to solve it. The formulation as a minimization problem is as follows :

This mathematical formulation is straightforward: the variable x_i is 1 if the item i is in the subset, otherwise it is 0 and it is not in the subset. The constraint sums the values of all items in the subset and this must be K as required. In many contexts, the Knapsack problem contains additional constraints, therefore it is advantageous to formulate it as a mathematical model.

5.3 The Two-Persons Zero-Sum Game

The 2-persons zero-sum game is a classical problem from the game theory. There are two players, each with an associated set of strategies i ∈I = {1,…,m} and j ∈J = {1,…,n}. While one player aims to maximize his payoff, the other player attempts to take an action to minimize this payoff. In fact, the gain of a player is the loss of another. Let p_i,j be the payoff for the first player after his played strategy i and the second player responded with strategy j, and let x_i be the frequency in percent at which player one should apply strategy i, then these frequencies can be calculated by the following mathematical linear model (explanation are given in a concrete example in Hofstadter’s Game.

This is an efficient way to formulated the problem, because it could be transformed easily into an LP (linear program). It would be much more involving to formulate this problem in an algorithmic way.

5.4 The Cutting Stock Problem

The cutting stock problem is another classical problem from the operations research. It is the problem of cutting standard-sized pieces of stock material, such as paper rolls or sheet metal, into smaller pieces of specified sizes while minimizing material wasted. The problem is explained in cutstock. The column generation version implemented in LPL is found in cutstock2. Technical details and a theory for these kind of problems can be found in the text book [22, Chap. 13]. To understand the main points that I want to make here, the technical details of the problem are not important.

My main point is the following: The cutting stock problem is preferably formulated partly in a mathematical way, partly in an algorithmic way:

For the mathematical part, three models must be implemented: (1) A small instance of the cutting stock problem with only a few patterns as a relaxed linear model (we call it rCS) (details and the notation is found in the link above) :

(2) An integer cutting stock (iCS) problem as follows :

(3) Finally, a Knapsack problem (fP) to find new improving pattern is also used :

For the algorithmic part, a procedure (in pseudo-code) is implemented to solve these mathematical models several times :

  function ColumnGenertion() { 
 
    InitializePatterns()          //add a few patterns to Cutstock 
 
    solve Cutstock                //returns duals 
 
    Inject_duals_into_Knapsack() 
 
    solve Knapsack                //to find a new improving pattern 
 
    while (found_an_improved_pattern) do { 
 
      Add_the_pattern_to Cutstock() 
 
      solve Cutstock              //returns duals 
 
      Inject_duals_into_Knapsack() 
 
      solve Knapsack             //to find a new improving pattern 
 
    } 
 
    solve IntegerCutstock 
 
  }

5.5 The Traveling Salesman Problem (TSP)

There are many different model formulations of the TSP. One concise mathematical formulation is the so-called Cutset formulation (see tsp-5). It is as follows:

The binary variables x_i,j is 1 if the circuit contains the arc (i,j) in the graph, otherwise it is 0. The constraints A and B make sure that a location is visited only once, and the constraint G excludes all subtours (further explications is given in tsp-5. Unfortunately, G contains an exponential number of constraints, for each sub-tour one. Hence, it is not possible to generate all if them at once. What is possible, however, is to solve an problem only with the constraints A and B then check which subtours constraints are violated and add then to the model, and proceed this way until no subtours is violated. The (algorithmic) procedure is then to begin with an empty list S and repeatedly add subtours to S :

  function AddSubtours() { 
 
    S = {} 
 
    cNr1 = 2            // initialize cNr1 (number of components found) 
 
    while (cNr1 > 1) do 
 
      solve Tsp 
 
      cNr1 = Nr_Components_Of_Graph() //get the components of the graph 
 
      Add_the_Components_to_S 
 
    } 
 
  }

6 Requirements

Combining mathematical and algorithmic knowledge in a single language is a great advantage for formulating such problems and the combination should be in a way that the different components can be clearly separated from each other. We shall call a modular language that combines mathematical and algorithmic knowledge, modeling language.

Definition: A modeling language is a notational system which allows us to combine in a modular way mathematical and algorithmic knowledge in the same framework. The content captured by such a notation is called model.

Algebraic modeling languages capture only mathematical knowledge, programming language capture only algorithmic knowledge. In my opinion, we are still missing a well designed modeling language. My own attempt is the language LPL. In LPL, one can implement models in a modular way, the language is close to the mathematical notation for mathematical models, it is also Turing complete. It is great and efficient to formulate large MIP models. However, it lacks classes and other advanced data structures, it lacks real (recursive) stack-based functions, and the algorithmic part is interpreted and might be slow. Although the basic language is simple and straightforward, some language constructs are difficult to understand, because they have grown over time.

Well, one could argue that modern programming languages, such as Python and Julia, contain already all elements that we need to implement (algorithmic+mathematical) models. Several packages have been implemented – as also mentioned – and new packages are implemented all the time to formulate mathematical models, like JuMP (Julia), GurobiPy, Pyomo, PuLP, Python-MIP, pyOPT (Python). Most solver libraries have an interface to Python or other programming languages. This approach is actually very trendy. In a concrete context, this approach may be the appropriate way, but in general, I think, this is a short-term thinking.

It is said that this approach has some advantages: One must learn only one language; a language like Python contains thousands of packages for all kinds of tasks: manipulating, reading/writing data, generating graphics and others; implementing efficient algorithms. So then, if one wants to use a “master language” like Python for modeling, why not using an algebraic language as an additional package (library), instead of using complicated syntax to define mathematical variables and constraints within the programming language?

As a small example, let’s look at the following simple non-linear model (see gurobiNLP) :

Why should one use the following GurobiPy (Python) code to implement this model

 import gurobipy as gp 
 
 from gurobipy import GRB 
 
 
 
 m = gp.Model() 
 
 x = m.addVar(lb=-1, ub=4, vtype=GRB.INTEGER, name="x") 
 
 twox = m.addVar(lb=-2, ub=8, name="2x") 
 
 sinx = m.addVar(lb=-1, ub=1, name="sinx") 
 
 cos2x = m.addVar(lb=-1, ub=1, name="cos2x") 
 
 expx = m.addVar(name="expx") 
 
 m.setObjective(sinx + cos2x + 1, GRB.MINIMIZE) 
 
 lc1 = m.addConstr(0.25 * expx - x <= 0) 
 
 lc2 = m.addConstr(2.0 * x - twox == 0) 
 
 gc1 = m.addGenConstrSin(x, sinx, "gc1") 
 
 gc2 = m.addGenConstrCos(twox, cos2x, "gc2") 
 
 gc3 = m.addGenConstrExp(x, expx, "gc3") 
 
 
 
 m.params.FuncNonlinear = 0    ## using Piecewise linear approx 
 
 # m.params.FuncNonlinear = 1  ## using MINLP solver 
 
 # m_presolve = m.presolve() 
 
 m.optimize()

if one can implement this model as follows (in LPL):

 model gurobiNLP; 
 
   SetSolver(gurobiLSol); 
 
   variable x [-1..4]; 
 
   constraint A: 0.25*Exp(x) - x <= 0; 
 
   minimize   M: Sin(x) + Cos(2*x) + 1; 
 
 end

It should be the modeling language’s task to decompose complicated non-linear terms to feed them to Gurobi (that’s what LPL does automatically). A further big advantage of the LPL formulation is that the model can easily be sent to another solver like Knitro (or any other solver that has an interface to LPL) just by replacing the first instruction to

  SetSolver(knitroLSol);

In this case, LPL does not need to decompose the non-linear expressions, but it eventually generate derivatives instead.

Anyway in my opinion, mathematical modeling should not be just an “addon” package within a common programming language, this would always be somewhat artificial. The mathematical structure is hidden within the programming code and the mathematical notation must be bent into shape of the particular programming language. Modeling is too important to be a supplement or an annex of an (existing) programming language. We need a proper (sub-)language for the mathematical part. The modeling language that I have in mind (which has not been implemented by now in my opinion) is also a complete programming language with all its interfaces to libraries, other software and own extensions with packages.

In the following, I list my personal preferences in the light of the following criteria for a – what I think is a “good” – mathematical modeling system. A modeling system should fulfill the following requirements:

1. A modeling system should be based in a formal language. Like a programming language, which is based on a written text and a formal grammar, a modeling system should be based on an executable language.

2. The modeling language should be a complete algorithmic and mathematical language, that is, rich enough to implement any algorithm (Turing complete), and it should contain features of a modern programming language, such as functions as a first class entity, classes, etc. It should also contain explicit syntax to formulate mathematical models.

3. In the language, it should be possible to modularize an model into sub-modules, in order to encapsulate entities and objects, similar to a modern programming language that contains classes (objects), modules, procedures, functions, units, etc.

4. The mathematical part of the modeling language syntax should be as close as possible to a common mathematical notation used to specify a model.

5. An important part of the syntax should be its (sparse) index capability in order to be able to formulate large models in a concise way.

6. It should be possible to formulate within the language all kinds of model paradigms: linear, non-linear, permutations, containing logical constraints, constraint programming (CP), differential systems, etc.

7. Reformulation and transformation of a mathematical model should be integrated. Depending on the solver used, a model must eventually be reformulated: Using a MIP solver, for instance, needs all constraints to be linear and a Boolean expression must be translated into mathematical expressions. Non-linear expressions must be possibly decomposed (as see before). Global constraints in CP are to be translated into mathematical constructs. etc.

8. The model formulation should be independent of a solution method (solver). From the structure of the model, it should be possible to infer automatically what solver is apt to solve the mathematical model. The modeler can overrule the assignment by various methods.

9. The mathematical model structure should be independent from the data instances. A model structure should be executable without data. The data could be part of the code, but it is not necessary and normally would be separated from the model structure. Data are best stored in databases or other external files.

10. On the base of the language, visual representations, like A-C graphs or others, and “visual” editors to build, manipulate and to modify the model could be built, as alternatives to editing and viewing the textual code – a modeling framework, as we know it from many programming framework (for example RAD Studio from Embarcadero).

11. Likewise programming languages, documenting a model is an important part in modeling – I guess it is even more important in modeling to understand its semantic.

7 Conclusion

In this paper, a new type of modeling language has been presented which is a superset of a programming language, since it can not only represent algorithmic, but also mathematical knowledge. It was shown by examples that some problems are best formulated in a mathematical way, others in an algorithmic way, still others in a combination of both. Consequently, we need languages which can code both kinds of knowledge in a unified framework.

Many researchers, especially in operations research, think that a modeling language is a specialized (programming) language. The concept of modeling language is often identified with that of an algebraic language and extending it with some algorithmic concepts is enough. I have tried to convince the reader that a modeling language should be more – no less – than a programming language. In fact, the activity of modeling is more general than that of programming. Programming is just a particular activity of modeling. Thus, a program can be viewed as a special kind of a model. Consequently, a modeling language must subsume a programming language, and must be more general.

Modeling, that is, the skill to translate a problem into a mathematical and algorithmic formalism (or some coding), should no longer be an “ad hoc science” where “everything goes”. It should be – like programming, the skill to write algorithms – an art to write good models. Furthermore, modeling should follow certain criteria of quality in the same way as software engineering teaches it for writing algorithmic programs.

The main criteria are: reliability and transparency. Reliability can be achieved by a unique notation to code models, and by various checking mechanisms (type checking, unit checking, data integrity checking and others). Transparency can be obtained by flexible decomposition techniques, like modular structure as well as access and protection mechanisms. Hence, what is true for programming languages is even more true for modeling languages. The cutting stock problem show clearly, that we need languages, which follow these criteria.

In the paper [5] the authors argues that the 5-th generation of programming languages will be modelware, i.e. programming will be replaced by modeling. We shall see.

References