Table Data for the transportation problem shows customer demand volumes, shipping costs from each factory to each customer, and production capacity at each factory. More precisely, \(d_i\) is the demand of customer \(i\) , where \(i =\) 1 to 5. Each plant \(j\) can supply its customers with goods but their production capacities are limited by \(M_j\) , where \(j =\) 1 to 3. Transportation cost for shipping goods from plant \(i\) to customer \(j\) is given in the table by \(c_{ij}\) .
Let us formulate the above problem as a linear optimization model. Suppose that the number of customers is \(n\) and the number of factories is \(m\) . Each customer is represented by \(i = 1, 2, \ldots, n\) , and each factory by \(j = 1, 2, \ldots, m\) . Also, let the set of customers be \(I = {1, 2, \ldots, n}\) and the set of factories \(J = {1, 2, \ldots, m}\) . Suppose that the demand amount of customer \(i\) is \(d_i\) , the transportation cost for shipping one unit of demand from plant \(i\) to customer \(j\) is \(c_{ij}\) , and that each plant \(j\) can supply its customers with goods, but their production capacities are limited by \(M_j\)
We use continuous variables as defined below.
Using the above symbols and variables, the transport problem can be formulated as the following linear optimization problem.
The objective function is the minimization of the sum of transportation costs. The first constraint requires that the demand is satisfied, and the second constraint ensures that factory capacities are not exceeded.
Let us solve this with Python/SCIP. First, we prepare the data needed for describing an instance [5] . In the transportation problem, it is necessary to prepare data defining demand amount \(d_i\) , transportation costs \(c_{ij}\) , capacities \(M_j\) . In the following program, we will use the same symbol used in the formulation for holding a Python’s dictionary. A dictionary is composed of a key and a value as its mapping, and is generated by arranging pais of keys and values in brackets, separated by commas: {key1:value1, key2:value2, ...} . (For details on dictionaries see appendix A.2.5 ).
The demand amount \(d_i\) is stored in a dictionary d with the customer’s number as the key and the demand amount as the value, and the capacity \(M_j\) is stored in the dictionary M with the factory number as the key and the capacity as the value.
In addition, a list I of customers’ numbers and a list J of factory numbers can be prepared as follows.
Actually, the dictionaries and lists above can be created at once by using the multidict function available in Python/SCIP, as follows.
When the dictionary is entered as an argument, the multidict function returns a pair of values; the first is the list of keys, and the second value is the dictionary sent as argument. Later, we will see that this function is very useful when we want to associate more than one value to each key. (For a more detailed usage of multidict , see appendix B.4 .)
Shipping cost \(c_{ij}\) has two subscripts. This is represented in Python by a dictionary c with a tuple of subscripts (customer and factory) as keys, and the corresponding costs as values. A tuple is a sequence, like a list; however, unlike a list, its contents can not be changed: a tuple is immutable . Tuples are created using parentheses and, due to the fact that they are immutable, can be used as keys of a dictionary (see appendix A.2.4 for details on tuples).
With this dictionary c , the transportation cost from factory \(j\) to customer \(i\) can be accessed with c[(i,j)] or c[i,j] (in a tuple, we can omit parenthesis).
As a programming habit, it is preferable not to use a one-letter variables such as d, M, c above. We have done it so that the same symbols are used in the formulation and in the program. However, in larger programs it is recommended to use meaningful variables names, such as demand, capacity, cost .
Let us write a program to solve the instance specified above.
model = Model("transportation") x = {} for i in I: for j in J: x[i,j] = model.addVar(vtype="C", name="x(%s,%s)" % (i,j)) |
First, we define a Python variable x , which initially contains an empty dictionary (line 2). We then use dictionary x to store variable’s objects, each of them corresponding to an \(x_{ij}\) of our model (lines 3 to 5). As I is a list of customers’ indices, the for cycle of line 3 iterates over all customers \(i\) . Likewise, since J is a list of factory indices, the for cycle of line 4 iterates over the quantity transported from factory \(j\) to customer \(i\) (see appendix A.4.2 for more information about iteration). In the rightmost part of line 5 the variable is named x(i,j) ; this uses Python’s string format operation % , where %s represents substitution into a character string.
Next we add constraints. First, we add the constraint
which imposes that the demand is satisfied. Since this is a constraint for all customers \(i\) , a constraint \(\sum_{j=1}^m x_{ij} = d_i\) is added by the addCons method (line 2) at each iteration of the for cycle of line 1.
for i in I: model.addCons(quicksum(x[i,j] for j in J if (i,j) in x) == d[i], name="Demand(%s)" % i) |
Notice that here we also give a name, Demand(i) , to constraints. Although, as for variables, the name of a constraint may be omitted, it is desirable to add an appropriate name for later reference (an example of this will be seen in Duality ). The quicksum function on the second line is an enhanced version of the sum function available in Python, used in Python/SCIP to do the computation of linear expressions more efficiently. It is possible to provide quicksum explicitly with a list, or with a list generated by iteration with a for statement, as we did here; these generator work in the same way as in list comprehensions in Python (see appendix A.4.2 ). In the above example, we calculate a linear expression by summing variables \(x_{ij}\) for element \(j \in J\) by means of quicksum(x[i,j] for j in J) . (For a more detailed explanation of quicksum , see appendix B.4 .)
Similarly, we add the factory capacity constraint
to the model as follows:
for j in J: model.addCons(quicksum(x[i,j] for i in I if (i,j) in x) <= M[j], name="Capacity(%s)" % j) |
Again, we give a name Capacity(j) to each constraint. In the following, to simplify the description, names of constraints are often omitted; but in fact it is safer to give an appropriate name.
The objective function
is set using the setObjective method, as follows.
model.setObjective(quicksum(c[i,j]*x[i,j] for (i,j) in x), "minimize") |
Finally, we can optimize the model and display the result.
model.optimize() print("Optimal value:", model.getObjVal()) EPS = 1.e-6 for (i,j) in x: if model.getVal(x[i,j]) > EPS: print("sending quantity %10s from factory %3s to customer %3s" % (model.getVal(x[i,j]),j,i)) |
In this code, for (i,j) in x in line 4 is an iteration over dictionary x , holding our model’s variable. This iteration goes through all the tuples \((i,j)\) of customers and factories which are keys of the dictionary. Line 5 is a conditional statement for outputting only non-zero variables. Line 6 uses Python’s string formatting operator % , where %10s is converted into a 10-digit character string and %3s is converted into a 3-digit character string.
When the above program is executed, the following result is obtained. The results are shown in Table Optimal solution for the transportation problem and Figure Transportation problem .
[solver progress output omitted] SCIP Status : problem is solved [optimal solution found] Solving Time (sec) : 0.00 Solving Nodes : 1 Primal Bound : +3.35000000000000e+03 (1 solutions) Dual Bound : +3.35000000000000e+03 Gap : 0.00 % Optimal value: 3350.0 sending quantity 230.0 from factory 2 to customer 3 sending quantity 20.0 from factory 3 to customer 3 sending quantity 160.0 from factory 3 to customer 4 sending quantity 270.0 from factory 2 to customer 2 sending quantity 80.0 from factory 1 to customer 1 sending quantity 180.0 from factory 3 to customer 5 |
Customer \(i\) | 1 | 2 | 3 | 4 | 5 | ||
---|---|---|---|---|---|---|---|
Amount demanded | 80 | 270 | 250 | 160 | 180 | ||
Plant \(j\) | Optimum volume transported | total | capacity | ||||
1 | 80 | 80 | 500 | ||||
2 | 270 | 230 | 500 | 500 | |||
3 | 20 | 160 | 180 | 360 | 500 |
Consider the following scenario.
In order to solve this problem smartly, the concept of dual problem is useful. Here, the dual problem is a linear optimization problem associated to the original problem (which in this context is called the primal problem). The derivation method and meaning of the dual problem are given in Margin seminar 2 ; here, we will explain how to use information from the dual of the transportation problem with Python/SCIP.
In order to investigate whether or not a factory can be expanded, let us first focus on the capacity constraint
For such an inequality constraint, a variable representing the difference between the right and the left hand sides, \(M_j - \sum_{i \in I} x_{ij}\) , is called a slack variable . Of course, one can easily calculate slack variables from the optimal solution, but in Python/SCIP we can look at the getSlack attribute for constraint objects. Also, the optimal dual variable for a constraint can be obtained with the getDualsolLinear attribute. This represents the amount of reduction on costs when increasing the capacity constraint by one unit (see Margin seminar 2 ).
In order to estimate the cost of additional orders from customers, we focus on the demand satisfaction constraint
Since this is an equality constraint, all slack variables are 0. The optimal value of the dual variable associated with this constraint represents the increase in costs as demand increases by one unit.
Margin seminar 2
Duality in linear programming provides a unifying theory that develops the relationships between a given linear program and another related linear program, stated in terms of variables with this shadow-price interpretation. The importance of duality is twofold. First, fully understanding the shadow-price interpretation of the optimal simplex multipliers can prove very useful in understanding the implications of a particular linear-programming model. Second, it is often possible to solve the related linear program with the shadow prices as the variables in place of, or in conjunction with, the original linear program, thereby taking advantage of some computational efficiencies. The importance of duality for computational procedures will become more apparent in later chapters on network-flow problems and large-scale systems.
Let us re-visit the wine production problem considered earlier to discuss some important concepts in linear-optimization models that play vital role in sensitivity analysis . Sensitivity analysis is important for finding out how optimal solution and optimal value may change when there is any change to the data used in the model. Since data may not always be considered as totally accurate, such analysis can be very helpful to the decision makers.
Let us assume that an entrepreneur is interested in the wine making company and would like to buy its resources. The entrepreneur then needs to find out how much to pay for each unit of each of the resources, the pure-grape wines of 2010 A, B and C. This can be done by solving the dual version of the model that we will discuss next.
Let \(y_1 , y_2\) and \(y_3\) be the price paid, per barrel of Alfrocheiro, Baga, and Castelão, respectively. Then, the total price that should be paid is the quantities of each of the wines in inventory times their prices, i.e., \(60y_1 + 60y_2 + 30y_3\) . Since the entrepreneur would like the purchasing cost to be minimum, this is the objective function for minimization. Now, for each of the resources, constraints in the model must ensure that prices are high enough for the company to sell to the entrepreneur. For instance, with two barrels of A and one barrel of B, the company can prepare blend \(D\) worth 15; hence, it must be offered \(2y_1 + y_2 \ge 15\) . Similarly we obtain \(y_1 + 2y_2 \ge 18\) and \(y_1 + y_2 + y_3 \ge 30\) for the blends M and S, respectively. Thus we can formulate a dual model, stated as follows (for a more sound derivation, using Lagrange multipliers, see lagrange ).
The variables used in the linear-optimization model of the production problem are called primal variables and their solution values directly solve the optimization problem. The linear-optimization model in this setting is called the primal model .
As seen above, associated with every primal model, there is a dual model. The relationships between primal and dual problems can provide significant information regarding the quality of solutions found and sensitivity of the coefficients used. Moreover, they also provide vital economic interpretations. For example, \(y_1\) , the price paid for one unit of Alfrocheiro pure-grape wine is called the shadow price of that resource, because it is the amount by which the optimal value of the primal model will change for a unit increase in its availability — or, equivalently, the price the company would be willing to pay for an additional unit of that resource.
Gurobi allows us to access the shadow prices (i.e., the optimal values of the dual variables associated with each constraint) by means of the .Pi attribute of the constraint class; e.g., in the model for the wine production company of program wblending we are printing these values in line 31.
Another concept important in duality is the reduced cost , which is associated with each decision variable. It is defined as the change in objective function value if one unit of some product that is normally not produced is forced into production; it can also be seen as the amount that the coefficient in the objective has to improve, for a variable that is zero in the optimal solution to become non-zero. Therefore, reduced cost is also appropriately called opportunity cost . Shadow prices and reduced costs allow sensitivity analysis in linear-optimization and help determine how sensitive the solutions are to small changes in the data. Such analysis can tell us how the solution will change if the objective function coefficients change or if the resource availability changes. It can also tell us how the solution may change if a new constraint is brought into the model. Gurobi allows us accessing the reduced costs through the .RC attribute of the variable class; e.g., x.RC is the reduced cost of variable x in the optimal solution.
As we will see later, primal and dual models can be effectively used not only to gain insights into the solution but also to find a bound for the linear-optimization relaxation of an integer-optimization model; linear-optimization relaxation is obtained by having the integrality constraints relaxed to non-integer solution values. Typically, an integer-optimization model is much harder to solve than its linear-optimization relaxation. Specialized algorithms have been designed around the relaxation versions of primal as well as dual optimization models for finding optimal solution more efficiently. Optimal solution of a relaxation model gives a bound for the optimal solution value of the underlying integer-optimization model, and that can be exploited in a branch-and-bound scheme for solving the integer optimization model.
In the previous transportation problem, we considered only one kind of goods produced at the production plants. In the real-world, however, that is a very restrictive scenario: A producer typically produces many different kinds of products and the customers typically demand different sets of the products available from the producers. Moreover, some producers may be specialized into producing only certain kinds of products while some others may only supply to certain customers. Therefore, a general instance of the transportation problem needs to be less restrictive and account for many such possibilities.
Multicommodity transportation
A more general version of the transportation problem is typically studied as a multi-commodity transportation model. A linear-optimization model can be built using decision variables \(x_{ijk}\) where \(i\) denotes the customer, \(j\) denotes the production plant and \(k\) denotes the product type. Customer demand is indexed by \(i\) and \(k\) to denote the customer and product type. Then the model can be stated as follows.
Note that the objective function addresses the minimum total cost for all possible cost combinations involving customers, production plants and product types. The first set of constraints ensure that all demands of the product types from the customers are met exactly while the second set of constraints ensure that capacity at each production plant is not exceeded by taking into account all product types and all customers.
A model for this in Python/Gurobi can be written as follows:
def mctransp(I, J, K, c, d, M): model = Model("multi-commodity transportation") x = {} for i,j,k in c: x[i,j,k] = model.addVar(vtype="C", name="x[%s,%s,%s]" % (i, j, k)) model.update() for i in I: for k in K: model.addConstr(quicksum(x[i,j,k] for j in J if (i,j,k) in x) == d[i,k], "Demand[%s,%s]" % (i,k)) for j in J: model.addConstr(quicksum(x[i,j,k] for (i,j2,k) in x if j2 == j) <= M[j], "Capacity[%s]" % j) model.setObjective(quicksum(c[i,j,k]*x[i,j,k] for i,j,k in x), GRB.MINIMIZE) model.update() model.__data = x return model |
Variables are created in line 5. In lines 9 and 10 we create a list the variables that appear in each demand-satisfaction constraint, and the corresponding coefficients; these are then used for creating a linear expression, which is used as the left-hand side of a constraint in line 11. Capacity constraints are created in a similar way, in lines 13 to 15. For an example, consider now the same three production plants and five customers as before. Plant 1 produces two products, football and volleyball; it can supply football only to Customer 1 and volleyball to all five customers. Plant 2 produces football and basketball; it can supply football to Customers 2 and 3, basketball to Customers 1, 2 and 3. Plant 3 produces football, basketball and rugby ball; it can supply football and basketball to Customers 4 and 5, rugby ball to all five customers.
Let us specify the data for this problem in a Python program. First of all, we must state what products each of the plants can manufacture; on dictionary produce the key is the plant, to which we are associating a list of compatible products. We also create a dictionary M with the capacity of each plant (3000 units, in this instance).
The demand for each of the customers can be written as a double dictionary: for each customer, we associate a dictionary of products and quantities demanded.
For determining the transportation cost, we may specify the unit weight for each product and the transportation cost per unit of weight; then, we calculate \(c_{ijk}\) as their product:
We are now ready to construct a model using this data, and solving it:
If we execute this Python program, the output is the following:
Optimize a model with 18 rows, 40 columns and 70 nonzeros Presolve removed 18 rows and 40 columns Presolve time: 0.00s Presolve: All rows and columns removed Iteration Objective Primal Inf. Dual Inf. Time 0 1.7400000e+04 0.000000e+00 0.000000e+00 0s Solved in 0 iterations and 0.00 seconds Optimal objective 1.740000000e+04 Optimal value: 17400.0 sending 100.0 units of 2 from plant 3 to customer 4 sending 210.0 units of 3 from plant 3 to customer 3 sending 40.0 units of 3 from plant 2 to customer 3 sending 40.0 units of 1 from plant 2 to customer 1 sending 10.0 units of 3 from plant 2 to customer 1 sending 100.0 units of 2 from plant 1 to customer 2 sending 100.0 units of 3 from plant 2 to customer 2 sending 70.0 units of 1 from plant 2 to customer 2 sending 60.0 units of 1 from plant 2 to customer 4 sending 30.0 units of 2 from plant 1 to customer 1 sending 180.0 units of 1 from plant 2 to customer 5 |
Readers may have noticed by now that for these two transportation problems, even though we have used linear-optimization models to solve them, the optimal solutions are integer-valued — as if we have solved integer-optimization models instead. This is because of the special structures of the constraints in the transportation problems that allow this property, commonly referred to as unimodularity . This property has enormous significance because, for many integer-optimization problems that can be modeled as transportation problems, we only need to solve their linear-optimization relaxations.
Fraction optimization problem ¶, multi-constrained knapsack problem ¶.
Knapsack problems are specially structured optimization problems. The general notion of the knapsack problem is to fill up a knapsack of certain capacity with items from a given set such that the collection has maximum value with respect to some special attribute of the items. For instance, given a knapsack of certain volume and several items of different weights, the problem can be that of taking the heaviest collection of the items in the knapsack. Based on weights, the knapsack can then be appropriately filled by a collection that is optimal in the context of weight as the special attribute.
Suppose we have a knapsack of volume 10,000 cubic-cm that can carry up to 7 Kg weight. We have four items having weights 2, 3, 4 and 5, respectively, and volume 3000, 3500, 5100 and 7200, respectively. Associated with each of the items is its value of 16, 19, 23 and 28, respectively. We would like to fill the knapsack with items such that the total value is maximum.
Knapsack instance
An integer-optimization model of this problem can be found by defining the decision variables \(x_j=\) 1 if item \(j\) is taken, and \(x_j = 0\) otherwise, where \(j =\) 1 to 4. For constraints, we need to make sure that total weight does not exceed 7 kg and total volume does not exceed 10,000 cubic-cm. Thus, we have an integer-optimization model:
The standard version of the knapsack problem concerns the maximization of the profit subject to a constraint limiting the weight allowed in the knapsack to a constant \(W\) ; the objective is to \(\mbox{maximize } \sum_j {v_j x_j}\) subject to \(\sum_j {w_j x_j \leq W}\) , with \(x_j \in \{0,1\}\) , where \(v_j\) is the value of item \(j\) and \(w_j\) is its weight. A more general problem includes constraints in more than one dimension, say, \(m\) dimensions (as in the example above); this is called the multi-constrained knapsack problem, or \(m\) -dimensional knapsack problem. If we denote the “weight” of an object \(j\) in dimension \(i\) by \(a_{ij}\) and the capacity of the knapsack in this dimension by \(b_i\) , an integer-optimization model of this problem has the following structure:
A Python/Gurobi model for the multi-constrained knapsack problem is:
def mkp(I, J, v, a, b): model = Model("mkp") x = {} for j in J: x[j] = model.addVar(vtype="B", name="x[%d]"%j) model.update() for i in I: model.addConstr(quicksum(a[i,j]*x[j] for j in J) <= b[i], "Dimension[%d]"%i) model.setObjective(quicksum(v[j]*x[j] for j in J), GRB.MAXIMIZE) model.update() return model |
This model can be used to solve the example above in the following way:
J,v = multidict({1:16, 2:19, 3:23, 4:28}) a = {(1,1):2, (1,2):3, (1,3):4, (1,4):5, (2,1):3000, (2,2):3500, (2,3):5100, (2,4):7200, } I,b = multidict({1:7, 2:10000}) model = mkp(I, J, v, a, b) model.ModelSense = -1 model.optimize() print "Optimal value=", model.ObjVal EPS = 1.e-6 for v in model.getVars(): if v.X > EPS: print v.VarName,v.X |
The solution of this example is found by Gurobi: \(x_2=x_3=1, x_1=x_4=0\) . We will next briefly sketch how this solution is found.
Many optimization problems, such as knapsack problems, require the solutions to have integer values. In particular, variables in the knapsack problem require values of either 1 or 0 for making decision on whether to include an item in the knapsack or not. Simplex method cannot be used directly to solve for such solution values because it cannot be used to capture the integer requirements on the variables. We can write the constraints \(0 \le x_j \le 1\) for all \(j\) for the binary requirements on the variables, but the simplex method may give fractional values for the solution. Therefore, in general, solving integer-optimization models is much harder. However, we can use a systematic approach called branch-and-bound for solving an integer-optimization model, using the simplex method for solving linear-optimization relaxation model obtained by “relaxing” any integer requirement on the variables to non-negatives only. The process begins with the linear-optimization relaxation of the integer-optimization model and solves several related linear-optimization models by simplex method for ultimately finding an optimal solution of the integer-optimization model.
Let us use the previous knapsack example to illustrate this procedure. We can transform this integer-optimization model of the knapsack problem to its linear-optimization relaxation by replacing the binary requirements by the constraints \(0 \le x_j \le 1\) for all \(j\) . All feasible solutions of the integer-optimization model are also feasible for this linear-optimization relaxation; i.e., the polyhedron of the integer-optimization model is now contained within the polyhedron of its linear-optimization relaxation.
This linear-optimization relaxation can be solved easily by the simplex method. If the optimal solution found is feasible to the integer-optimization model also — i.e., it satisfies the binary constraints also, then we have found the optimal solution to the integer-optimization model. Otherwise, for this maximization problem, we can use the value of the optimal solution of the linear-optimization relaxation as the upper bound on the maximum value any solution of the integer-optimization model can possibly attain. Thus, optimal solution value of the linear-optimization relaxation provides an upper bound for the optimal solution value of the underlying integer-optimization model; this information can be suitably used for solving integer-optimization model via solving several related linear-optimization models.
The general notion of branch-and-bound scheme is to use bound on the optimal solution value in a tree search, as shown in Figure Branch-and-bound . Each leaf of the tree represents some linear-optimization relaxation of the original integer-optimization model. We start at the root of the search tree with the linear-optimization relaxation of the original integer-optimization model. Simplex method, gives the optimal solution \(x = (1,1,0.5,0)\) and objective function value 46.5. Since \(x_3 = 0.5\) is not integer and for the original integer-optimization model we need the variables to be either 0 or 1, we create two different subproblem children of the root by forcing \(x_3 =1\) and \(x_3 = 0\) , say \(P1\) and \(P2\) , respectively. Their optimal solutions are \(x= ( 1,1,0,0.4)\) with objective value 46.2 and \(x= (1, 0.333,1,0)\) with objective value 45.333, respectively. Now these two subproblems can be expanded again by branching on their fractional values just as before. The process will yield a binary search tree because \(x_j\) can only take values of 0 and 1.
Branch-and-bound
Consider the two children of \(P1\) , \(P3\) and \(P4\) . As found, the optimal solutions for \(P3\) and \(P4\) are \(x = (0,1,1,0)\) with objective function value 42 and \(x = (1,0,1,0.2)\) with objective function value 44.6, respectively. Since \(P3\) gives us a feasible solution for the integer-optimization model, we have an incumbent solution \(x = (0,1,1,0)\) with value 42. If no other feasible solution to the integer-optimization model from the tree search produces objective value larger than 42, then the incumbent is the optimal solution.
As can be seen from this small example, exploring the whole solution space can lead to a very large number of computations, as the number of nodes may potentially duplicate from one level to the other. Gurobi uses branch-and-bound in connection to other advanced techniques, such as the cutting plane approach, in order to achieve a very good performance on this process. As we will see later (e.g., in Chapter Graph problems ), there are some limitations to the size of the problems that can be tackled by Gurobi; however, a very large number of interesting, real-world problems can be solved successfully. In other situations, even if Gurobi cannot find the optimal solution, it will find a solution close to the optimum within reasonable time; in many applications, this is enough for practical implementation.
In this section we consider a mathematical model for maximizing diversity of diet intakes, subject to nutritional requirements and calorie restrictions. Let \(\mathcal{F}\) be a set of distinct foods and \(\mathcal{N}\) be a set of nutrients. Let \(d_{ij}\) be the amount of nutrient \(i\) in food \(j\) . The minimum and maximum intake of each nutrient \(i\) is given by \(a_i\) and \(b_i\) , respectively. An upper bound for the quantity of each food is given by \(M\) . Let \(x_j\) be the number of dishes to be used for each food \(j\) , and let \(y_j=1\) indicate if food \(j\) is chosen, \(y_j=0\) if not. Let the cost of the diet be \(v\) and the amount of intake of each nutrient be given by \(z_i\) . The problem is to minimize the number of distinct foods.
The first set of constraints ( Nutr in the program below) calculate the amount of each nutrient by summing over the selection of foods. Together with the last set of constraints (which is entered as bounds on \(z\) , line 8 in the program below), they ensure that nutrient levels \(z_i\) are maintained within the maximum and minimum amounts, \(a_i\) and \(b_i\) , as required. The second set of constraints ( Eat in the program below) impose that a dish variety \(y_j\) will be allowed into the objective (i.e., be non-zero) only if at least one unit of that dish \(x_j\) is selected. The third constraint ( Cost , line 16 in the program) calculates cost \(v\) of selecting a diet, while the other two constraints impose non-negativity and binary requirements on the variables \(x_j\) and \(y_j\) defined earlier.
In Python/Gurobi, this model can be specified as follows.
def diet(F, N, a, b, c, d): model = Model("modern diet") x, y, z = {}, {}, {} for j in F: x[j] = model.addVar(lb=0, vtype="I", name="x[%s]" % j) y[j] = model.addVar(vtype="B", name="y[%s]" % j) for i in N: z[i] = model.addVar(lb=a[i], ub=b[i], name="z[%s]" % j) v = model.addVar(name="v") model.update() for i in N: model.addConstr(quicksum(d[j][i]*x[j] for j in F) == z[i], "Nutr[%s]" % i) model.addConstr(quicksum(c[j]*x[j] for j in F) == v, "Cost") for j in F: model.addConstr(y[j] <= x[j], "Eat[%s]" % j) model.setObjective(quicksum(y[j] for j in F), GRB.MAXIMIZE) model.__data = x, y, z, v return model |
We may use the data provided in http://www.ampl.com/EXAMPLES/MCDONALDS/diet2.dat for applying this model to a concrete instance:
inf = GRB.INFINITY N, a, b = multidict({ "Cal" : [ 2000, inf ], "Carbo" : [ 350, 375 ], "Protein" : [ 55, inf ], "VitA" : [ 100, inf ], "VitC" : [ 100, inf ], "Calc" : [ 100, inf ], "Iron" : [ 100, inf ], }) F, c, d = multidict({ "QPounder":[1.84, {"Cal":510, "Carbo":34, "Protein":28, "VitA":15, "VitC": 6, "Calc":30, "Iron":20}], "McLean" :[2.19, {"Cal":370, "Carbo":35, "Protein":24, "VitA":15, "VitC": 10, "Calc":20, "Iron":20}], "Big Mac" :[1.84, {"Cal":500, "Carbo":42, "Protein":25, "VitA": 6, "VitC": 2, "Calc":25, "Iron":20}], "FFilet" :[1.44, {"Cal":370, "Carbo":38, "Protein":14, "VitA": 2, "VitC": 0, "Calc":15, "Iron":10}], "Chicken" :[2.29, {"Cal":400, "Carbo":42, "Protein":31, "VitA": 8, "VitC": 15, "Calc":15, "Iron": 8}], "Fries" :[ .77, {"Cal":220, "Carbo":26, "Protein": 3, "VitA": 0, "VitC": 15, "Calc": 0, "Iron": 2}], "McMuffin":[1.29, {"Cal":345, "Carbo":27, "Protein":15, "VitA": 4, "VitC": 0, "Calc":20, "Iron":15}], "1%LFMilk":[ .60, {"Cal":110, "Carbo":12, "Protein": 9, "VitA":10, "VitC": 4, "Calc":30, "Iron": 0}], "OrgJuice":[ .72, {"Cal": 80, "Carbo":20, "Protein": 1, "VitA": 2, "VitC":120, "Calc": 2, "Iron": 2}], }) |
In this specification of data we have used a new feature of the multidict function: for the same key (e.g., nutrients), we may specify more than one value, and assign it to several Python variables; for example, in line 3 we are specifying both the minimum and the maximum intake amount concerning calories; respectively, a and b . We are now ready to solve the diet optimization model; let us do it for several possibilities concerning the maximum calorie intake b["Cal"] :
The data is specified in lines 1 through 43. In lines 45 to 58, we solve this problem for different values of the maximum calorie intake, from infinity (i.e., no upper bound on calories) down to 2500. We encourage the reader to use Python/Gurobi to solve this problem, and check that the variety of dishes allowed decreases when the calorie intake is reduced. Interestingly, the amount spent does not vary monotonously: among those values of the calorie intake, the minimum price is for a maximum of calories of 3500 (see also Appendix dietinput ).
As said before, until recently these were called problems, which had been abbreviated as ; complying to the new nomenclature, the abbreviation we will use is , for problems. |
A class of problems which, even though no one proved it, are believed to be difficult to solve; i.e., solving these problems requires resources that grow exponentially with the size of the input. |
Of course “anything” is an exaggeration. In a Python lecture found at the Massachusetts Institute of Technology home page there is a reference to an antigravity module. Please try it with antigravity. |
Sometimes it is called a barrier method. |
A problem with all the parameters substituted by numerical values is called ; this meaning is different of “objects generated from a class”, used in object-oriented programming, which are also called “instances” of the class. |
People tend to use the terms “problems” and “exercises” interchangeably. But there’s a difference—and it matters.
Professor Paul Zeitz makes the distinction.
Take 5 × 5. That’s easy, and that’s an exercise. So is 5,490,900 × 496. It’s a bit harder and will take you more time to solve, but you know what to do. That’s the key point.
“An exercise is a mathematical question that you immediately know how to answer,” explains Zeitz in a lecture series on problem-solving . “You may not answer it correctly, in fact you may never answer it correctly...but there’s no doubt about how to proceed.”
Not so with problems. A problem, according to Zeitz, “is a mathematical question that you do not know how to answer, at least initially.”
He defines problems and exercises through the lens of mathematical problem-solving, but they’re applicable to programming as well.
Each day we put our problem-solving skills to work as programmers: debugging code, learning a new topic, or even solving a problem. Exercises have their place, but as a programmer there’s no replacement for solving problems.
There are two ways you can benefit from exercises. First, they’re helpful when learning a new topic.
I’m learning JavaScript right now and using a mix of exercises and problems to do so. The exercises help me see patterns and get comfortable with concepts and syntax.
Here’s an example of an exercise from a project that asked me to write a function, which took an array of cars.
I had to sort the array of objects by the car_model key, in ascending order.
It’s not to say this exercise was a breeze—it wasn’t. It took me time and I got my fair share of error messages.
However, it qualifies as an exercise because I knew what I needed to do from the start.
I’d recently learned about arrays in JavaScript. I was familiar with sorting data from my experience with Python, though I had to research how to do this in JavaScript. The explicit directions helped, too.
But the concepts were still new. I needed practice putting them together, which is why this exercise was valuable. Repetition breeds familiarity, and the concepts began to solidify in my mind.
Exercises also help keep learned information fresh.
As I learn JavaScript, I don’t want to forget everything I’ve learned about the first language I learned, Python. So I use Anki, a flashcard program, multiple times per day.
In this context, exercises help you keep a mountain of material straight, remind you of important concepts, and get more comfortable using a particular data structure or approach. It’s maintenance work on the body of knowledge you’ve gained so far.
I have over 1,000 cards that are filled with material I’ve seen many times before. Some cards have questions about syntax. Others ask me to write SQL queries or command-line or Git commands. Many others are filled with exercises, like “rotate a list of numbers to the right by one place value.”
It’s important to note that this exercise was once a problem for me. If you do a problem enough, it can become an exercise. At the same time, you can make an exercise a problem by adding a constraint .
Exercises are a slippery slope. On the one hand, they’re useful for learning purposes. On the other, it’s easy to get comfortable by sticking with exercises exclusively.
That’s the downside: staying in your comfort zone.
Programming is about problem-solving. And solving problems will take you outside of your comfort zone. This is a good thing.
For me, problems have two distinctive qualities. The first is ambiguity. Problem-solving is largely about how to effectively deal with ambiguity.
These examples all involve ambiguity. And all of them require solving problems , whether that’s finding and trouble-shooting a bug, solving an actual problem, or learning a new topic.
To make progress, you research, experiment, pull out the facts, create a plan, and apply a variety of problem-solving tactics. In short, you learn to figure it out. The more time you spend with a problem and the different perspectives you gain , the more layers it reveals and the closer you get to the “aha” moment.
The other difference with problems is the struggle. It’s real.
Problem-solving will test your mental stamina and patience. Progress can be slow, and the process tedious. I’ve toiled away at problems for hours, days, and even weeks.
It’s not to say that exercises won’t challenge you. They can. It’s one thing when you know that you need to use a particular method; you just need to get it to work properly. That’s a challenge, which can sometimes be downright frustrating.
But it’s something else entirely when you have no idea what to do from the start, which may happen multiple times when solving a problem. To me, problems are a struggle.
The best solution is to endure it and get yourself unstuck . In my experience, the struggle means I’m learning a lot and the breakthrough is usually around the corner.
As you push through the mental discomfort, you’ll find yourself thinking creatively and devising solutions you never thought of before. (You surprise and impress yourself—you know more than you think!) You’re becoming a stronger programmer.
You’ll even find yourself having fun. Problem-solving is challenging, to be sure, and even frustrating at times. But it’s also incredibly rewarding.
It’s like crossing the finish line of a half-marathon. No doubt the past 13.1 miles were grueling, but crossing the finish line was worth it and I’d do it again. Solving a problem feels the same way.
When you crack open your laptop, are you going to solve problems or complete exercises?
Exercises have benefits, and it’s fine to incorporate them into your programming sessions. I use exercises as a warm-up prior to a programming session. I’ll flip through an Anki flashcard deck for ten or fifteen minutes and work through some exercises. If I’m learning something new, like JavaScript, I may have an entire programming session devoted to exercises.
However, I devote time each day to solving problems —no matter what else I’m learning or building. Even on the days when I allocate a large chunk of time to exercises, I allocate plenty of time to solving problems, too.
So when you’re about to start a programming session, be aware what you’re setting out to do: exercises or problems. And no matter what, make time for solving problems.
Problem-solving is a skill that takes a lot of practice and time to develop. The only way to get better is to work at it each day. It’s that important, and for good reason.
We solve problems each day as programmers, and in a variety of ways. Making time to problem-solve is a no-brainer; our work as programmers depends on it.
I write about learning to program, and the best ways to go about it ( amymhaddad.com ).
Programmer and writer | howtolearneffectively.com | dailyskillplanner.com
If you read this far, thank the author to show them you care. Say Thanks
Learn to code for free. freeCodeCamp's open source curriculum has helped more than 40,000 people get jobs as developers. Get started
Mathematical programming is an extremely powerful technology that enables companies to make better use of available resources. Mathematical programming technologies like linear programming (LP) and mixed-integer programming (MIP) have been applied in a variety of business areas, often resulting in tens or even hundreds of millions of dollars in cost savings. To give a quick sampling of the breadth of applications for LP and MIP techniques:
While the process of building a mathematical programming model will probably look like magic to a non-expert, the intent of this page is to provide a bit of insight into what goes on behind the magic, and hopefully give an indication of how you might wield some of this magic for yourself. Math programming practitioners typically have mathematical training and significant practical experience, but understanding a few simple concepts can help you get a sense of the overall process. This page provides a quick, high-level overview of mathematical programming, as well as a few useful links to additional information, including case studies and example models.
We’ll start our discussion at the point where you’ve identified a part of your business that could potentially benefit from optimization (note that we’ll use the terms “mathematical programming”, “math programming”, “mathematical optimization”, and “optimization” interchangeably here). Such opportunities are generally found wherever critical resources are being underutilized because multiple different business processes compete for resources. The goal of a mathematical programming model is to
If this description seems a bit non-specific, that’s actually due to the flexibility of math programming. LP and MIP are highly mathematical technologies that don’t make any assumptions about the type of problem you are trying to solve or your goal in solving it. The person building the optimization model can specify what it means to maximize efficiency – maximizing profit, minimizing cost, minimizing delays, etc. Similarly, your resources can be anything – money, raw materials, machines, workers, etc. It’s up to the mathematical modeler to translate the often very tangible items that are part of the business process into the very mathematical objects that are used represent them in the optimization model.
If you have a sense that optimization could be the right tool for your business problem, you have a few options for scoping the opportunity. The simplest is probably to speak with an expert. Gurobi has a number of experts on staff, plus a network of consulting partners, that can help you size up an opportunity. The initial assessment typically only takes a few hours. We also have many customers with no background in optimization who have managed to teach themselves the relevant mathematical modeling concepts and have succeeded in building and deploying sophisticated optimization models.
Once you’ve identified a business process that could benefit from optimization, the next step is to create an optimization model to exploit the opportunity. There are three main steps to this process:
Let’s talk about each of these in more detail…
As we’ve noted, the first step in using optimization is to create a mathematical model of your business problem. An LP or MIP model consists of three primary ingredients:
The challenge here is to map the business problem, which may involve tangible entities like machines or products or people, into the form described above, which involves linear constraints on decision variables. At first glance, LP and MIP may appear to be a strange choice for solving business problems. As we noted above, LP and MIP allow you to state a set of linear constraints on decision variables (e.g., ‘2x + 3y + 5z <= 5’) and a linear objective on these same variables (e.g., ‘maximize x + y + z’). MIP also allows you to specify that certain variables must take integer values. These tools then compute values for your decision variables that maximize the objective function while respecting all stated linear constraints. That’s all that LP and MIP can do. While the merits of being able to optimize over a set of linear constraints might be clear if you are solving geometry problems, the suitability for production scheduling or electricity distribution problems probably isn’t so obvious.
For now, you’ll have to take our word for it that it is possible to map a wide variety of problems to LP/MIP form. Let’s spend a minute talking about why you would want to…
When faced with the task of solving a difficult problem, the first step is often to assemble a set of tools that might help to solve that problem. While you may not be able to find a tool that solves your exact problem, you can often find one that is effective at solving a related problem. While a custom tool may be able to exploit some special property of the specific problem you are solving, a general purpose tool has the advantage that it has probably been tuned and refined over a long period of time and a variety of users and uses.
This is particularly true for LP and MIP. If you can express your model as a set of linear constraints with a linear objective, over a set of continuous or integer decision variables, then you can reap the benefit of using a technology that has undergone a process of extensive refinement and improvement over the last 50+ years. The improvements in the technology have been quite spectacular , often transforming problems that were entirely intractable a decade ago into problems that are routinely solved today. What’s more, by building an LP or MIP model for your problem, you are then able to obtain the benefits of future improvements in the technology with no additional effort on your part.
To say that the benefits of expressing your problem as an LP or MIP are due to decades of effort focused on solving the problem doesn’t fully capture the virtues of LP and MIP, though. LP and MIP sit at a juncture between rich mathematical theory, elegant computational implementations, and richness of modeling and expressiveness that is quite rare and quite special. You could set the best and brightest minds at work for 50 years on many other problem types, and you would probably not wind up with technologies that are as powerful or as elegant as LP and MIP.
Hopefully we’ve convinced you that there are substantial benefits to formulating your problem as an LP or MIP model. If so, then the next step is to talk a bit about how that is done. The fundamental building block for a MIP model is the binary decision variable. It typically capture a yes/no decision, where a value of 1 means yes and a value of 0 means no. You can use a binary variable to represent any number of business decisions (“should I build this product?”, “should I buy this raw material?”, etc.). Constraints between binary variables represent competition for resources. Constraints between binary variables and continuous variables often capture the more detailed implications of these decisions.
Let’s consider a few simple examples. If you can choose at most one from among a set of conflicting activities, that would be captured as a linear constraint on binary decision variables:
b 1 + b 2 + b 3 <= 1
If these are all binary variables, then at most one variable in the list can take value 1, and that one would correspond to the chosen activity. Similarly, changing the inequality to an equality:
b 1 + b 2 + b 3 = 1
…would force you to always choose one of the three possible activities.
Given a decision that is reflected in the value of a binary variable, you can use additional variables and constraints to capture the consequences of that decision. For example, if you need to transport items from one city to another, then a decision about whether to send a truck between those cities determines the maximum number of items that can be sent. By introducing a variable items[ij] to represent the number of items sent from city i to city j, then the following linear constraint would capture the relationship between the number of items sent and a decision about whether to send a truck with a capacity of 10 items:
items ij <= 10 * truck ij
If binary variable truck[ij] is 1, then you can send up to 10 items. If it is 0, then you can’t send any items.
These are just a few examples chosen from among a large set of idioms that are useful when building a mathematical model. A typical optimization model will consist of a mix of many straightforward linear constraints (e.g., the sum of these cost variables must respect the overall budget), along with a few more idiomatic constraints. Furthermore, a typical model will consist of thousands or even millions of constraints, but the overall size is typically the result of replicating the same set of constraints over multiple pieces of input data. One of the best ways to learn these idioms is to study example models. You’ll find examples from a variety of industries that you can browse and learn from here .
If you ask an architect to design a house for you, his first thought is not going to be about how to pour concrete for the foundation. He’s going to try to identify important characteristics of the desired house (size, style, bedrooms, etc.), and then modify a house design with similar characteristics to meet your specific needs. Similarly, while understanding the low-level process of building an optimization model can be quite useful, the reality is that the mathematical modeling process is often mostly about recognizing common structure in your problem and customizing well-established models to capture the specifics of your problem.
Mathematical modeling has a number of commonly occurring model patterns that appear in many different applications. Examples include fixed-charge network flow, set partitioning, production planning, facility location, job shop scheduling, portfolio optimization, etc. It is well worth your time to familiarize yourself with common model types. Our website provides a number of example models that capture common model types. To reiterate, the model you need for your problem may not match any of these patterns exactly, but you are often better off approaching your problem by identifying a similar pattern and then thinking about how it could to customized to capture your problem, rather than trying to solve your problem from scratch.
While we’ve only mentioned LP and MIP so far, there are a number of interesting extensions that can also be solved efficiently. If your problem has a quadratic objective, involving products of decision variables rather than just linear terms, then you can solve your model as a Quadratic Program (QP) or a Mixed-Integer Quadratic Program (MIQP). If your model has quadratic constraints as well, you can solve your model as a Quadratically Constrained Program (QCP), or a Mixed-Integer Quadratically Constrained Program (MIQCP). These variants place a few restrictions on the form of the quadratic objective or constraint, but many important types of models can be cast in this form.
Another common class of models is non-linear programming (NLP) problems. While general NLP is an extremely difficult problem, such problems can often be solved using a very common and powerful approach called piecewise-linear approximation. By approximating the non-linear function using a series of linear functions, you can often transform what is typically an exceedingly difficult optimization problem into one that can be easily handled by an LP or MIP solver. Optimization solvers typically include modeling tools that make it straightforward to express a piecewise-linear function.
Once you have an idea of how to build a math programming model that would solve your problem, the next step is to write a computer program that implements your model. Gurobi provides interfaces for most of the commonly used programming languages: C, C++, Java, .NET, Python, R, and MATLAB. When people ask us which language is best for math programming, our answer is that people should use the language they are most comfortable in. All of our interfaces are thin layers that sit on top of the same optimization algorithms (implemented in C). There are difference in our various language API’s, but ultimately those differences will have a smaller impact on your productivity than working in an unfamiliar language would. Another point to consider is that mathematical models rarely live in isolation. They typically consume data from some data source, and they produce results that are consumed by some downstream process. The languages and formats of these dependent processes will influence your choice of language.
Having said that, if you don’t have a reason to prefer one language over another, we recommend you use our Python API . We’ve found that this API increases modeling productivity substantially. It includes a number of higher-level modeling constructs that reduce the gap between the mathematical model itself and the implementation of that model, which makes it a lot easier to build and maintain optimization models.
The mechanics of building the optimization model are generally quite straightforward, once you have assembled the necessary input data. Our Getting Started with the Gurobi API Tutorials work through simple examples in each of our supported languages. This example touches on the basics of our API’s, including the process of creating a model, adding decision variables, adding constraints, setting the objective function, etc. We also include a number of functional examples that cover the use of more advanced features in our product.
A large part of the power of LP and MIP is that they provide a declarative approach to solving a problem. It is your job to state, or declare , your problem (the decision variables, constraints, and objective), and it is our job to find an optimal solution. The solver employs a number of very sophisticated algorithms for both LP and MIP problem types (and a number of parameters that optionally give you control over the behavior of these algorithms), but you generally don’t need to understand how these algorithms works to obtain a solution to your problem.
Your next step in building an optimization model will depend on how hands-on you’d like to be. As we noted above, if you are interested in further details about different aspects of math programming, you can refer to our Python basics discussion for more information on building a model, or our LP basics and MIP basics pages for more information on the underlying solution algorithms. You also browse our examples or our case studies .
If you are a commercial user who would like to discuss your problem with an expert, you can contact Gurobi directly . As Gurobi is free for qualified academic users, we provide direct support for installation and licensing questions and a monitored Gurobi Community Discussion Forum for other questions.
We also have a list of consulting firms who can help you to scope your problem and build a solution.
Of course, the best next step is to try Gurobi for yourself:
30 day free trial for commercial users, always free for academics.
GUROBI NEWSLETTER
Latest news and releases
Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.
Academic license, cloud trial.
Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.
Looking for documentation?
Case studies, privacy overview.
Cookie | Duration | Description |
---|---|---|
_biz_flagsA | 1 year | A Cloudflare cookie set to record users’ settings as well as for authentication and analytics. |
_biz_pendingA | 1 year | A Cloudflare cookie set to record users’ settings as well as for authentication and analytics. |
_biz_sid | 30 minutes | This cookie is set by Bizible, to store the user's session id. |
ARRAffinity | session | ARRAffinity cookie is set by Azure app service, and allows the service to choose the right instance established by a user to deliver subsequent requests made by that user. |
ARRAffinitySameSite | session | This cookie is set by Windows Azure cloud, and is used for load balancing to make sure the visitor page requests are routed to the same server in any browsing session. |
BIGipServersj02web-nginx-app_https | session | NGINX cookie |
cookielawinfo-checkbox-advertisement | 1 year | Set by the GDPR Cookie Consent plugin, this cookie is used to record the user consent for the cookies in the "Advertisement" category . |
cookielawinfo-checkbox-analytics | 11 months | This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics". |
cookielawinfo-checkbox-functional | 11 months | The cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional". |
cookielawinfo-checkbox-necessary | 11 months | This cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary". |
cookielawinfo-checkbox-others | 11 months | This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other. |
cookielawinfo-checkbox-performance | 11 months | This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance". |
CookieLawInfoConsent | 1 year | Records the default button state of the corresponding category & the status of CCPA. It works only in coordination with the primary cookie. |
elementor | never | This cookie is used by the website's WordPress theme. It allows the website owner to implement or change the website's content in real-time. |
JSESSIONID | session | New Relic uses this cookie to store a session identifier so that New Relic can monitor session counts for an application. |
viewed_cookie_policy | 11 months | The cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data. |
Cookie | Duration | Description |
---|---|---|
__cf_bm | 30 minutes | This cookie, set by Cloudflare, is used to support Cloudflare Bot Management. |
_biz_nA | 1 year | Bizible sets this cookie to remember users’ settings as well as for authentication and analytics. |
_biz_uid | 1 year | This cookie is set by Bizible, to store user id on the current domain. |
_hjAbsoluteSessionInProgress | 30 minutes | Hotjar sets this cookie to detect a user's first pageview session, which is a True/False flag set by the cookie. |
_mkto_trk | 2 years | This cookie is set by Marketo. This allows a website to track visitor behavior on the sites on which the cookie is installed and to link a visitor to the recipient of an email marketing campaign, to measure campaign effectiveness. Tracking is performed anonymously until a user self-identifies by submitting a form. |
bcookie | 1 year | LinkedIn sets this cookie from LinkedIn share buttons and ad tags to recognize browser ID. |
bscookie | 1 year | LinkedIn sets this cookie to store performed actions on the website. |
doc_langsBB | 1 year | Documentation system cookie |
doc_version | 1 year | Documentation system cookie |
lang | session | LinkedIn sets this cookie to remember a user's language setting. |
lidc | 1 day | LinkedIn sets the lidc cookie to facilitate data center selection. |
UserMatchHistory | 1 month | LinkedIn sets this cookie for LinkedIn Ads ID syncing. |
whova_client_id | 10 years | Event agenda system cookie |
Cookie | Duration | Description |
---|---|---|
_gat_UA-5909815-1 | 1 minute | A variation of the _gat cookie set by Google Analytics and Google Tag Manager to allow website owners to track visitor behaviour and measure site performance. The pattern element in the name contains the unique identity number of the account or website it relates to. |
Cookie | Duration | Description |
---|---|---|
_an_uid | 7 days | 6Sense Cookie |
_BUID | 1 year | This cookie, set by Bizible, is a universal user id to identify the same user across multiple clients’ domains. |
_ga | 2 years | The _ga cookie, installed by Google Analytics, calculates visitor, session and campaign data and also keeps track of site usage for the site's analytics report. The cookie stores information anonymously and assigns a randomly generated number to recognize unique visitors. |
_ga_* | 1 year 1 month 4 days | Google Analytics sets this cookie to store and count page views. |
_gat_UA-* | 1 minute | Google Analytics sets this cookie for user behaviour tracking. |
_gcl_au | 3 months | Provided by Google Tag Manager to experiment advertisement efficiency of websites using their services. |
_gd_session | 4 hours | This cookie is used for collecting information on users visit to the website. It collects data such as total number of visits, average time spent on the website and the pages loaded. |
_gd_visitor | 2 years | This cookie is used for collecting information on the users visit such as number of visits, average time spent on the website and the pages loaded for displaying targeted ads. |
_gid | 1 day | Installed by Google Analytics, _gid cookie stores information on how visitors use a website, while also creating an analytics report of the website's performance. Some of the data that are collected include the number of visitors, their source, and the pages they visit anonymously. |
_hjFirstSeen | 30 minutes | Hotjar sets this cookie to identify a new user’s first session. It stores the true/false value, indicating whether it was the first time Hotjar saw this user. |
_hjIncludedInSessionSample_* | 2 minutes | Hotjar cookie that is set to determine if a user is included in the data sampling defined by a site's daily session limit. |
_hjRecordingEnabled | never | Hotjar sets this cookie when a Recording starts and is read when the recording module is initialized, to see if the user is already in a recording in a particular session. |
_hjRecordingLastActivity | never | Hotjar sets this cookie when a user recording starts and when data is sent through the WebSocket. |
_hjSession_* | 30 minutes | Hotjar cookie that is set when a user first lands on a page with the Hotjar script. It is used to persist the Hotjar User ID, unique to that site on the browser. This ensures that behavior in subsequent visits to the same site will be attributed to the same user ID. |
_hjSessionUser_* | 1 year | Hotjar cookie that is set when a user first lands on a page with the Hotjar script. It is used to persist the Hotjar User ID, unique to that site on the browser. This ensures that behavior in subsequent visits to the same site will be attributed to the same user ID. |
_hjTLDTest | session | To determine the most generic cookie path that has to be used instead of the page hostname, Hotjar sets the _hjTLDTest cookie to store different URL substring alternatives until it fails. |
6suuid | 2 years | 6Sense Cookie |
AnalyticsSyncHistory | 1 month | LinkedIn cookie |
BE_CLA3 | 1 year 1 month 4 days | BrightEdge sets this cookie to enable data aggregation, analysis and report creation to assess marketing effectiveness and provide solutions for SEO, SEM and website performance. |
CONSENT | 2 years | YouTube sets this cookie via embedded youtube-videos and registers anonymous statistical data. |
dj | 10 years | DemandJump cookie |
djaimid.a28e | 2 years | DemandJump cookiean |
djaimses.a28e | 30 minutes | DemandJump cookie |
li_gc | 5 months 27 days | LinkedIn Cookie |
ln_or | 1 day | LinkedIn Cookie |
vuid | 2 years | Vimeo installs this cookie to collect tracking information by setting a unique ID to embed videos to the website. |
Cookie | Duration | Description |
---|---|---|
__adroll | 1 year 1 month | This cookie is set by AdRoll to identify users across visits and devices. It is used by real-time bidding for advertisers to display relevant advertisements. |
__adroll_fpc | 1 year | AdRoll sets this cookie to target users with advertisements based on their browsing behaviour. |
__adroll_shared | 1 year 1 month | Adroll sets this cookie to collect information on users across different websites for relevant advertising. |
__ar_v4 | 1 year | This cookie is set under the domain DoubleClick, to place ads that point to the website in Google search results and to track conversion rates for these ads. |
_fbp | 3 months | This cookie is set by Facebook to display advertisements when either on Facebook or on a digital platform powered by Facebook advertising, after visiting the website. |
_te_ | session | Adroll cookie |
fr | 3 months | Facebook sets this cookie to show relevant advertisements to users by tracking user behaviour across the web, on sites that have Facebook pixel or Facebook social plugin. |
IDE | 1 year 24 days | Google DoubleClick IDE cookies are used to store information about how the user uses the website to present them with relevant ads and according to the user profile. |
li_sugr | 3 months | LinkedIn sets this cookie to collect user behaviour data to optimise the website and make advertisements on the website more relevant. |
test_cookie | 15 minutes | The test_cookie is set by doubleclick.net and is used to determine if the user's browser supports cookies. |
VISITOR_INFO1_LIVE | 5 months 27 days | A cookie set by YouTube to measure bandwidth that determines whether the user gets the new or old player interface. |
YSC | session | YSC cookie is set by Youtube and is used to track the views of embedded videos on Youtube pages. |
yt-remote-connected-devices | never | YouTube sets this cookie to store the video preferences of the user using embedded YouTube video. |
yt-remote-device-id | never | YouTube sets this cookie to store the video preferences of the user using embedded YouTube video. |
yt.innertube::nextId | never | This cookie, set by YouTube, registers a unique ID to store data on what videos from YouTube the user has seen. |
yt.innertube::requests | never | This cookie, set by YouTube, registers a unique ID to store data on what videos from YouTube the user has seen. |
Find the point easy problem solving (basic) max score: 5 success rate: 88.49%, maximum draws easy problem solving (basic) max score: 5 success rate: 95.75%, handshake easy problem solving (basic) max score: 10 success rate: 93.90%, minimum height triangle easy problem solving (basic) max score: 10 success rate: 92.22%, army game easy problem solving (basic) max score: 10 success rate: 84.87%, leonardo's prime factors easy problem solving (basic) max score: 10 success rate: 77.21%, connecting towns easy problem solving (basic) max score: 10 success rate: 87.52%, cutting paper squares easy problem solving (basic) max score: 15 success rate: 87.97%, summing the n series medium problem solving (basic) max score: 20 success rate: 75.14%, sherlock and moving tiles easy problem solving (basic) max score: 20 success rate: 76.49%, cookie support is required to access hackerrank.
Seems like cookies are disabled on this browser, please enable them to open this website
Advertisement
3118 Accesses
32 Citations
Explore all metrics
This paper reports on a design-based study within the context of a 3-day digital making (DM) summer camp attended by a group of students (aged 11–13) in grades 5 and 6. During the camp, students were presented with a set of mathematical problems to solve in a block-based programming environment, which was connected to various physical input sensors and output devices (e.g., push buttons, LED lights, number displays, etc.). Students’ code files, and screen captures of their computer work, were analyzed in terms of their developed computational problem-solving practices and any computational concepts that emerged during the problem-based DM. The results suggested that the designed tasks consistently supported the students’ modeling and algorithmic thinking, while also occasioning their testing and debugging practices; moreover, the students utilized computational abstractions in the form of variables, and employed different approaches, to formulate mathematical models in a programming context. This study contributes to the ‘big picture’ of how using computers might fundamentally change mathematics learning, with an emphasis on mathematical problem-solving. It also provides empirically grounded evidence to enhance the potential of computational thinking as a new literacy, and problem-solving as a global competence, in formal school settings.
This is a preview of subscription content, log in via an institution to check access.
Subscribe and save.
Price includes VAT (Russian Federation)
Instant access to the full article PDF.
Rent this article via DeepDyve
Institutional subscriptions
Explore related subjects.
Arzarello, F., Ferrara, F., & Robutti, O. (2012). Mathematical modeling with technology: The role of dynamic representations. Teaching Mathematics and Its Applications, 31 (1), 20–30.
Article Google Scholar
Baldwin, D., Walker, H. M., & Henderson, P. B. (2013). The roles of mathematics in computer science. ACM Inroads, 4 (4), 74–80. https://doi.org/10.1145/2537753.2537777 .
Barab, S., & Squire, K. (2004). Design-based research: Putting a stake in the ground. Journal of the Learning Sciences, 13 (1), 1–14.
Benton, L., Hoyles, C., Kalas, I., & Noss, R. (2017). Bridging primary programming and mathematics: Some findings of design research in England. Digital Experiences in Mathematics Education, 3 (2), 115–138. https://doi.org/10.1007/s40751-017-0028-x
Benton, L., Saunders, P., Kalas, I., Hoyles, C., & Noss, R. (2018). Designing for learning mathematics through programming: A case study of pupils engaging with place value. International Journal of Child-Computer Interaction, 16, 68–76.
Blum, W., & Leiß, D. (2007). How do students and teachers deal with modeling problems? In C. Haines, W. Blum, P. Galbraith, & S. Khan (Eds.), Mathematical modeling (ICTMA 12): Education, engineering and economics (pp. 222–231). Chichester: Horwood.
Google Scholar
Brennan, K., Resnick, M. (2012). New frameworks for studying and assessing the development of computational thinking . Paper Presented at the Conference of American Education Researcher Association, Vancouver.
Cai, J., Lew, H. C., Morris, A., Moyer, J. C., Ng, S. F., & Schmittau, J. (2005). The development of students’ algebraic thinking in earlier grades. ZDM Mathematics Education, 37 (1), 5–15. https://doi.org/10.1007/bf02655892 .
Carreira, S., & Jacinto, H. (2019). A model of mathematical problem solving with technology: The case of Marco solving-and-expressing two geometry problems. In P. Liljedahl & M. Santos-Trigo (Eds.), Mathematical problem solving (pp. 41–62). Cham: Springer.
Chapter Google Scholar
Cetin, I. (2015). Students’ understanding of loops and nested loops in computer programming: An APOS theory perspective. Canadian Journal of Science, Mathematics and Technology Education, 15 (2), 155–170.
Chu, S., Quek, F., Saenz, M., Bhangaonkar, S., & Okundaye, O. (2015). Enabling instrumental interaction through electronics making: Effects on children’s storytelling. In H. Schoenau-Fog, L. Bruni, S. Louchart, & S. Baceviciute (Eds.), Interactive storytelling. ICIDS 2015. Lecture notes in computer science (pp. 329–337). Cham: Springer.
Feurzeig, W., Papert, S. A., & Lawler, B. (2011). Programming-languages as a conceptual framework for teaching mathematics. Interactive Learning Environments, 19 (5), 487–501.
Gadanidis, G., Hughes, J. M., Minniti, L., & White, B. J. G. (2017). Computational thinking, grade 1 students and the binomial theorem. Digital Experiences in Mathematics Education, 3 (2), 77–96. https://doi.org/10.1007/s40751-016-0019-3
Greefrath, G., Hertleif, C., & Siller, H. S. (2018). Mathematical modeling with digital tools—A quantitative study on mathematising with dynamic geometry software. ZDM Mathematics Education, 50 (1–2), 233–244.
Greefrath, G., & Siller, H. S. (2017). Modeling and simulation with the help of digital tools. In G. A. Stillman, W. Blum, & G. Kaiser (Eds.), Mathematical modeling and applications (pp. 529–539). Cham: Springer.
Grover, S., & Pea, R. (2013). Computational thinking in K–12: A review of the state of the field. Educational Researcher, 42 (1), 38–43.
Hughes, J., Gadanidis, G., & Yiu, C. (2017). Digital making in elementary mathematics education. Digital Experiences in Mathematics Education, 3 (2), 139–153. https://doi.org/10.1007/s40751-016-0020-x
Kong, S. (2019). Components and methods of evaluating computational thinking for fostering creative problem-solvers in senior primary school education. In S. Kong & H. Abelson (Eds.), Computational thinking education . Singapore: Springer. https://doi.org/10.1007/978-981-13-6528-7 .
Liljedahl, P. (2016). Building thinking classrooms: Conditions for problem-solving. In P. Felmer, E. Pehkonen, & J. Kilpatrick (Eds.), Posing and solving mathematical problems (pp. 361–386). Cham: Springer.
Namukasa, I. K., Kotsopoulos, D., Floyd, L., Weber, J., Kafai, Y. B., Khan, S., et al. (2016). From computational thinking to computational participation: Towards achieving excellence through coding in elementary schools. In G. Gadanidis (Ed.), Math + coding symposium . London: Western University.
Ng, O., & Chan, T. (2019). Learning as making: Using 3D computer-aided design to enhance the learning of shapes and space in STEM-integrated ways. British Journal of Educational Technology, 50 (1), 294–308. https://doi.org/10.1111/bjet.12643
Ng, O., & Ferrara, F. (2019). Towards a materialist vision of ‘learning as making’: The case of 3D printing pens in school mathematics. International Journal of Science and Mathematics Education . https://doi.org/10.1007/s10763-019-10000-9
Niemelä, P., Partanen, T., Harsu, M., Leppänen, L., & Ihantola, P. (2017). Computational thinking as an emergent learning trajectory of mathematics. Proceedings of the 17th Koli Calling Conference on Computing Education Research—Koli Calling 17 . https://doi.org/10.1145/3141880.3141885
Organisation for Economic Co-operation and Development (OECD). (2004). The PISA 2003 assessment framework: Mathematics, reading, science and problem solving knowledge and skills . Paris: OECD Publishing. https://doi.org/10.1787/9789264101739-en
Book Google Scholar
Papert, S. (1980). Mindstorms: Children, computers, and powerful ideas . New York: Basic Books.
Papert, S., & Harel, I. (1991). Situating constructionism. Constructionism, 36 (2), 1–11.
Pólya, G. (1945). How to solve it . Princeton: Princeton University Press.
Pei, C. Y., Weintrop, D., & Wilensky, U. (2018). Cultivating computational thinking practices and mathematical habits of mind in lattice land. Mathematical Thinking and Learning, 20 (1), 75–89. https://doi.org/10.1080/10986065.2018.1403543
Resnick, M., Maloney, J., Monroy-Hernández, A., Rusk, N., Eastmond, E., Brennan, K., & Kafai, Y. B. (2009). Scratch: Programming for all. Communications of the ACM, 52 (11), 60–67.
Rodríguez-Martínez, J., González-Calero, J., & Sáez-López, J. (2019). Computational thinking and mathematics using scratch: An experiment with sixth-grade students. Interactive Learning Environments, 28 (3), 316–327.
Roschelle, J., Pea, R., Hoadley, C., Gordin, D., & Means, B. (2000). Future of children. Children and Computer Technology, 10 (2), 76–101.
Roschelle, J., Noss, R., Blikstein, P., & Jackiw, N. (2017). Technology for learning mathematics. In J. Cai (Ed.), Compendium for research in mathematics education (pp. 853–876). Reston: National Council of Teachers of Mathematics.
Santos-Trigo, M. (2019). Mathematical problem solving and the use of digital technologies. In P. Liljedahl & M. Santos-Trigo (Eds.), Mathematical problem solving (pp. 63–89). Cham: Springer.
Strauss, A. L., & Corbin, J. (2008). Basics of qualitative research . Los Angeles: SAGE Publications.
Van de Walle, J., Karp, K., & Bay-Williams, J. (2015). Elementary and middle school mathematics—Teaching developmentally (9th ed.). New York: Pearson.
Weintrop, D., Beheshti, E., Horn, M., Orton, K., Jona, K., Trouille, L., & Wilensky, U. (2016). Defining computational thinking for mathematics and science classrooms. Journal of Science Education and Technology, 25 (1), 127–147. https://doi.org/10.1007/s10956-015-9581-5
Wilkerson-Jerde, M. H. (2014). Construction, categorization, and consensus: Student generated computational artifacts as a context for disciplinary reflection. Educational Technology Research and Development, 62 (1), 99–121.
Wing, J. M. (2006). Computational thinking. Communications of the ACM, 49 (3), 33–35.
Yadav, A., Mayfield, C., Zhou, N., Hambrusch, S., & Korb, J. T. (2014). Computational thinking in elementary and secondary teacher education. ACM Transactions on Computing Education, 14 (1), 1–16.
Download references
This study was supported by the Chinese University of Hong Kong Faculty of Education Direct Grant (Ref. No. 4058081). The authors would like to thank the anonymous students who participated so enthusiastically in the study.
Authors and affiliations.
The Chinese University of Hong Kong, Shatin, Hong Kong SAR
Oi-Lam Ng & Zhihao Cui
You can also search for this author in PubMed Google Scholar
Correspondence to Oi-Lam Ng .
Publisher's note.
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Reprints and permissions
Ng, OL., Cui, Z. Examining primary students’ mathematical problem-solving in a programming context: towards computationally enhanced mathematics education. ZDM Mathematics Education 53 , 847–860 (2021). https://doi.org/10.1007/s11858-020-01200-7
Download citation
Accepted : 23 October 2020
Published : 04 November 2020
Issue Date : August 2021
DOI : https://doi.org/10.1007/s11858-020-01200-7
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
IMAGES
COMMENTS
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems. The motivation for starting Project ...
Mathematical Programming in Practice5In management science, as in most sciences, there is a natura. interplay between theory andpractice. Theory provides tools for applied work and suggests viable approaches to problem solving, whereas practice adds focus to the theory by suggesting areas for theoretical development in its continual.
Our platform offers a range of essential problems for practice, as well as the latest questions being asked by top-tier companies. Explore; Problems; ... Interview. Store. problemset_primary. Study Plan. See all. Array 1722. String 717. Hash Table 621. Dynamic Programming 525. Math 513. Sorting 410. Greedy 375. Depth-First Search 295. Database ...
Guided interactive problem solving that's effective and fun. Master concepts in 15 minutes a day. Get started. Math. Data Analysis. Computer Science. Programming & AI. Science & Engineering. Join over 10 million people learning on Brilliant. Master concepts in 15 minutes a day.
This course is an introduction to linear optimization and its extensions emphasizing the underlying mathematical structures, geometrical ideas, algorithms and solutions of practical problems. The topics covered include: formulations, the geometry of linear optimization, duality theory, the simplex method, sensitivity analysis, robust optimization, large scale optimization network flows ...
Linear programming is a set of techniques used in mathematical programming, sometimes called mathematical optimization, ... The basic method for solving linear programming problems is called the simplex method, which has several variants. Another popular approach is the interior-point method.
To address this research gap, this study analyses the participants' thinking processes in solving programming-based mathematical problems from a flexibility perspective, focusing on the interplay between computational and mathematical thinking, that is, how CT and MT work together to influence and determine the problem-solver's choice of ...
Mathematical programming is a problem-solving approach that uses mathematical models and algorithms to optimize decision-making processes. Computer programming, on the other hand, is about writing code to create software or systems that computers can execute. While they both involve the word "programming," they have different focuses and ...
Mathematical programming refers to mathematical models used to solve problems such as decision problems. (Bruno Tisseyre et al., 2020) It involves a separation between the representation of the problem through a mathematical model and its solving. (Bruno Tisseyre et al., 2020) The solving may be done through general methods, such as branching methods, using the mathematical model designed to ...
Linear programming is a mathematical technique to solve problems involving finding maximums or minimums where a linear function is limited by various constraints. ... There are four steps that need to be completed when solving a problem using linear programming. They are as follows: Step 1: Compose an objective function to be minimized or ...
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at ...
Linear optimization problems with conditions requiring variables to be integers are called integer optimization problems. For the puzzle we are solving, thus, the correct model is: minimize y + z subject to: x + y + z = 32 2x + 4y + 8z = 80 x, y, z ≥ 0, integer. Below is a simple Python/SCIP program for solving it.
How Edabit Works. This is an introduction to how challenges on Edabit work. In the Code tab above you'll see a starter function that looks like this: function hello () { } All you have to do is type return "hello edabit.com" between the curly braces { } and then click the Check button. If you did this correctly, the button will turn red and ...
He defines problems and exercises through the lens of mathematical problem-solving, but they're applicable to programming as well. Each day we put our problem-solving skills to work as programmers: debugging code, learning a new topic, or even solving a problem. Exercises have their place, but as a programmer there's no replacement for ...
There are three main steps to this process: Create the conceptual mathematical model that captures the important resources and constraints in the business problem. Translate the conceptual mathematical model into a computer program that builds that model. Solve the mathematical model using a math programming solver.
Mathematical optimization (alternatively spelled optimisation) or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. [ 1 ] [ 2 ] It is generally divided into two subfields: discrete optimization and continuous optimization .
Dep. Informatics Engineering. 3030-290 Coimbra - Port ugal. +351 239 790000. [email protected]. ABSTRACT. Programming is hard to learn to most novice students. Several. reasons can be pointed out to ...
Join over 23 million developers in solving code challenges on HackerRank, one of the best ways to prepare for programming interviews.
The optimization techniques used to solve the problems are primarily linear, mixed-integer linear, nonlinear, and mixed integer nonlinear programming. The book also covers important considerations for solving real-world optimization problems, such as dealing with valid inequalities and symmetry during the modeling phase, but also data ...
Fundamental concepts of mathematical modeling Modeling is one of the most effective, commonly used tools in engineering and the applied sciences. In this book, the authors deal with mathematical programming models both linear and nonlinear and across a wide range of practical applications. Whereas other books concentrate on standard methods of analysis, the authors focus on the power of ...
In summary, here are 10 of our most popular problem solving courses. Effective Problem-Solving and Decision-Making: University of California, Irvine. Creative Thinking: Techniques and Tools for Success: Imperial College London. Solving Complex Problems: Macquarie University. Solving Problems with Creative and Critical Thinking: IBM.
This paper reports on a design-based study within the context of a 3-day digital making (DM) summer camp attended by a group of students (aged 11-13) in grades 5 and 6. During the camp, students were presented with a set of mathematical problems to solve in a block-based programming environment, which was connected to various physical input sensors and output devices (e.g., push buttons, LED ...
5.1: Problem Solving An introduction to problem-solving is the process of identifying a challenge or obstacle and finding an effective solution through a systematic approach. It involves critical thinking, analyzing the problem, devising a plan, implementing it, and reflecting on the outcome to ensure the problem is resolved.
amining primar students' mathematical problem-solving in a programming context: towards… 849 1 3 Examples of common software-hardware combinations with DM capabilities include Micro:bit and Arduino, the latter of which was used in this study. Despite widespread recognition that making is benecial
Works with the team to mine data using modern tools and programming languages. Develops algorithms, performs small scale experimentation, builds data driven applications to translate data into intelligence, and develops solutions for solving business problems. Incorporates predictive modeling, statistics and other analysis techniques for collecting, exploring, interpreting and extracting ...