Solving ENGN3211 with Minizinc

It is compulsory for engineering students at the university I attend to complete an introductory course in economics and accounting (ENGN3211). With exams in full-swing, I’ve been going through the course material for ENGN3211, revising for the exam. After labouriously going through each of the ENGN3211 assignments yesterday, something quite self-evident became apparent: economic type problems are particularly well suited to constraint programming. Having become increasingly interested in constraint programming lately through Jess’ posts on Minizinc, I decided to see how easy it would be to ’solve’ problems from the ENGN3211 assignments by describing them in Minizinc. Having noted that the problems encountered in the course are particularly well suited to Minizinc, there were some more qualitative problems that have been omitted from the Minizinc treatment here.

We begin with a look at problem 1 from assignment 3:

The market for tickets to the symphony can be described by the following demand and supply curves:
D = 20000 – 90P
S = 10000 + 110P

1. What are the equilibrium price and quantity in the ticket market?
2. Lovers of classical music persuade the government to impose a price ceiling of $40 per ticket. How many tickets are now sold in the market?

This problem maps fairly directly to Minizinc code, we pretty much just write out the equations already given to us:

%Include standard definitions:
include "globals.mzn";

%From variables described in problem statement:
var int: P;
var int: D = 20000 - 90*P;
var int: S = 10000 + 110*P;

%To solve for equilibrium supply and demand, simply remove this constraint.
%The government imposes a $40 ceiling:
constraint P  < = 40;

%Solve for as close to equilibrium supply and demand as possible:
solve minimize abs(D-S);

%Print our solution:
output["The price is $", show(P), " per ticket and the quantity sold is ",
    show(min(S,D)), " tickets.\n"];

with the output for respective cases being:

The price is $50 per ticket and the quantity sold is 15500 tickets.
The price is $40 per ticket and the quantity sold is 14400 tickets.

This problem was very straight-forward to solve in Minizinc, emphasizing just how great this language is for the typical supply-demand problems you come across in an introductory economics textbook. However, I feel that by using Minizinc to solve a problem as simple as this, we do not achieve much of a productivity gain compared to the traditional approach of solving through algebraic manipulations.

Furthermore, there does not seem to be any way to solve for two or more subtly different cases of the same problem, one after the other. One solution to this short-coming is to rely on the user to conditionally comment-out some constraints for different cases and run the program multiple times. This is not ideal. There may be some feature of Minizinc (that I am not aware of) that simplifies this situation but as one of the design goals is to create a minimal language, this is unlikely. Keeping the rationale behind Minizinc in mind, not being able to solve for different cases in the same program is hardly something to feel sore about.

Moving along, we want to solve assignment 3, problem 2:

Suppose the demand curve for pizza can be represented by the equation D = 20 – 2P, where D is the quantity demanded and P is the price. The supply curve for pizza can be represented by the equation S=P-1, where S is the quantity supplied.
Suppose the government imposes a $3 tax per pizza. How much more will consumers now pay for a pizza?

which can be mapped to Minizinc as:

%Include standard definitions:
include "globals.mzn";

%From variables described in problem statement:
var int: PD;
var int: PS;
var int: D = 20 - 2*PD;
var int: S = PS - 1;

%Without a tax:
%constraint PD = PS;
%With a $3 tax:
constraint PD = PS + 3;

%Market is at equilibrium:
constraint D = S;

%Solve for equilibrium supply and demand:
solve satisfy;

%Print our solution:
output["Consumers will pay $", show(PD), " per pizza.\n"];

with the output for the respective cases being:

Consumers will pay $7 per pizza.
Consumers will pay $8 per pizza.

Again, the process of mapping the problem to Minizinc code is fairly straight-forward. Unlike the previous problem, this problem was actually easier for me and quicker to solve with Minizinc than doing algebra. Especially since I had a bit of a template to go off by using the code I wrote for the previous problem. Yet again, we rely on the user to conditionally comment certain constraints but this is fairly trivial for a savvy user.

Now, on to assignment 4, question 1:

The Pristine River has two polluting firms on its banks. Acme Industrial and Creative Chemicals each dump 100 tonnes of glop into the river each year. The cost of reducing glop emissions per tonne equals $10 for Acme and $100 for Creative. The local government wants to reduce overall pollution from 200 tonnes to 50 tonnes.

1. If the government knew the cost of reduction for each firm, what reductions would it impose in order to reach its overall goal? What would be the cost to each firm and the total cost to the firms together?
2. In a more typical situation, the government would not know the cost of pollution reduction at each firm. If the government decided to reach its overall goal by imposing uniform reductions on the firms, calculate the reduction made by each firm, and the total cost to the firms together.

Which we write in Minizinc as:

include "globals.mzn";

%Adapted from all_different
predicate all_same(array[int] of var int: x) =
	forall(i,j in index_set(x) where i  j) ( x[i] = x[j]);

%Set the number of companies involved:
int : n = 2;
set of int: companies = 1..n;

%Arrays for data on each firm:
array[companies] of int : reductionCostPerTonnes = [10, 100];
array[companies] of int : pollutionTonnes = [100,100];
array[companies] of var int : reductionTonnes;
array[companies] of var int : reductionCost =
   ([ reductionTonnes[c] * reductionCostPerTonnes[c] | c in companies]);

%The sum of the differences in reductionCost between
%one firm and the consecutive firm in the array for each firm:
var int : reductionCostDelta = sum
   ([ abs(reductionCost[c] - reductionCost[c+1]) | c in 1..(n-1)]);

%The sum of each firms reductionTonnes:
var int : totalReduction = sum ([reductionTonnes[c] | c in companies]);

%The sum of each firms reductionCost:
var int : totalCost = sum ([reductionCost[c] | c in companies]);

%We want to reduce our current pollution down to 50 tonnes.
int : pollutionGoal = 50;
var int : reductionGoal = (sum
   ([pollutionTonnes[c] | c in companies])) - pollutionGoal;

%Cannot reduce pollutionTonnes beyond pollutionTonnes we are currently producing.
constraint forall ([ reductionTonnes[c]  < = pollutionTonnes [c] | c in companies]);
%PollutionTonnes must not be reduced by a negative amount, this does not make sense.
constraint forall ([ reductionTonnes[c] >= 0 | c in companies]);
%The total reduction in pollutionTonnes must meet our reductionGoal
constraint totalReduction = reductionGoal;

%If we know how much reducing pollution costs each firm,
%we minimize the difference in pollution reduction costs between firms.
solve minimize reductionCostDelta;
%If we do not know how much reducing pollution costs each firm,
%we simply get them to reduce pollution by the same amount regardless of cost.
%constraint all_same(reductionTonnes);
%solve satisfy;

%Print our solution:
output ["reductionGoal = ", show(reductionGoal), "\n",
	"reductionTonnes = ", show(reductionTonnes), "\n",
	"reductionCostPerTonnes = ", show(reductionCostPerTonnes), "\n",
	"reductionCost = ", show(reductionCost), "\n",
	"totalCost = ", show(totalCost), "\n"];

with the output:

reductionGoal = 150
reductionTonnes = [100, 50]
reductionCostPerTonnes = [10, 100]
reductionCost = [1000, 5000]
totalCost = 6000
reductionGoal = 150
reductionTonnes = [75, 75]
reductionCostPerTonnes = [10, 100]
reductionCost = [750, 7500]
totalCost = 8250

This problem was actually the hardest for me to write in Minizinc. It certainly demonstrates that Minizinc can be used for solving less trivial problems but more effort is needed. I really like that array comprehensions are possible in Minizinc and have used them way more than what is really advisable.

And finally, assignment 4, question 2:

Suppose that 10 people live on the street and that each of them is willing to pay $2 for each extra streetlight, regardless of the number of streetlights provided. The cost of providing L streetlights is given by c(L)=L*L. What is the most efficient number of streetlights to provide from the point of view of a central planner?

which we solve with:

%Include standard definitions:
include "globals.mzn";

%From the problem statement:
int: numberOfResidents = 10;
int: contributionPerLight = 2;

%The 0..10000 is to stop integer overflows resulting from the solver,
%this is not a limit given to us in the problem statement.
%The number of streetlights on the street:
var 0..10000 : numberOfLights;

%The cost for a particular number of streetlights:
var int: cost = numberOfLights * numberOfLights;
%The contribution from a single resident:
var int: contribution = contributionPerLight * numberOfLights;
%The aggregate contribution from the whole street:
var int: aggregateContribution = contribution * numberOfResidents;

%Adding 0 extra streetlights could be a solution, but not the one we are after.
constraint numberOfLights > 0;

%Maximize the central planner's profit realized by providing extra streetlights:
solve maximize aggregateContribution - cost;

%Print our solution:
output["Most efficient number of streetlights is ", show(numberOfLights), "\n",
   "As cost is ", show(cost), "\n",
   "And contributions is ", show(aggregateContribution), "\n"];

with the output:

Most efficient number of streetlights is 10
As cost is 100
And contributions is 200

In this example, we have run into another problem: certain constraints or definitions can result in overflow when the program is executed. Luckily, the compiler can detect these situations, giving the programmer sufficient notice that the code needs to be altered. Whilst this is commendable in a compiler, in my opinion, a ’smarter’ solver would be able to avoid overflow for the problem above. Admittedly, solvers are hard enough to implement, especially given performance, soundness and other concerns, without trying to make them ’smarter’.

For this example, we have managed to get around integer overflow by restricting the domain for numberOfLights. This could probably be done automatically but even then, it would still be prudent to alert the user that the domain of variables in the problem and thus, their potential solutions have been restricted.

In conclusion, Minizinc is a fantastic language to use for constraint type problems and is true to its minimalist design goal. At times, this minimalism can be trying; especially if you simply want to piece together a quick solution to a given problem. However, this minimalism also makes a thorough analysis of the language much easier. Many types of problems would be unsuited to constraint programming and Minizinc, and therefore quite difficult to solve with Minizinc code. As always, it is important to identify which tool is the right one for the task at hand.

~ by sargegoodweather on 25th June, 2009.