Linear programming and LINDO FAQ
Linear programming and LINDO FAQ
IPDME format is due to Gerald Brown. See his excellent articles, “How to Write About Operations Research,” and “Top Ten Secrets to Success with Optimization”, as well as Rick Rosenthal's related presentation, “Eleven Keys to Success in Optimization Modeling”.
When you write an LP formulation, especially with algebraic notation, your reader will be helped if you explain the details. Use “IPDME” format: Write the Indices, Parameters, Decision variables, Model, and Explanation. For simple LPs, with no named parameters, and all the variables written out explicitly, you can generally leave off the indices and parameters sections, but please do not get in the bad habit of leaving these off when they are needed.
The indices are the subscripts on variables and parameters. For example, with the variable xi, i=1,...,5, the letter i is a subscript. You should generally use the same letters for a given meaning. For example, if i is used in one place to mean “city,” try to avoid using it elsewhere for “time.”
Select indices with care. In operations research, we usually use the letters i, j and k as indices, not as parameters or variables. Time is usually indexed with t.
Of course, if you write out every variable, and if you use values instead of parameters, then there is no need to explain indices.
Parameters are data, the constant numbers that are needed as inputs. In a large model, or when we write a model algebraically, we often do not know the actual value, so we name it. For example, our model requires the demand for royal gala apples for each city, i=1,...5. We might name this parameter di.
Name parameters with care. If you have many different parameters, list them in alphabetical order. In operations research, parameters are usually named with the letters from the beginning of the alphabet. (A couple grad students, working on a big model, named a parameter “Variable,” because it was the “variable profit contribution per unit product.”) It is helpful to distinguish parameters from decision variables by case of the letter. If you do this, I would prefer that you make parameters upper case.
I prefer one-letter parameter names. The math model is then much more concise and the overall structure is more readily apparent, compared to using words (or even phrases) for parameters.
After you name a parameter, you need to explain what that name means and the units of measure.
For a small model, you may use actual numbers in your model, instead of using letters. In this case, you do not need to define each parameter. Define letters for data when you do not use actual values. For beginning LP assignments, you probably do not need an Indices or a Parameters section, because those are explicit in the model.
Some authors suggest that parameters and variables be distinguished by case, e.g. put all variables in upper case and all parameters in lower case (or vice versa).
Demand is usually d, time is usually t, inventory is usually I
Decision variables are the values that we don't know, but if we knew them, we would have the answer. If you have many decision variables, list them in alphabetical order. Name variables with care. In operations research, we usually use the letters at the end of the alphabet for variables. Sometimes we use Greek letters, such as l (lambda) and p (pi), especially for the dual variables of a math program. It is helpful to distinguish parameters from decision variables by case of the letter. If you do this, make variables lower case.
In naming your variables, be very specific. What are the units of measure? What is the action?
I prefer one-letter variable names. The math model is more concise and the structure is more apparent, compared to using words or phrases for variables.
The model is the algebraic formulation of the math program. Number the formulas, with the objective function as the first. Name the model, as well.
I do not like the symbol
,
which means “for all.”
It requires an equation object, is hard to read, and is not widely known.
Use the text “for all” instead.
The explanation describes the model, one formula at a time.
Here is an example:
Indices
i = plant, i = Chch, Auckland.
j = wholesaler, j = 1,…, 5.
Parameters
Cij = cost to send a box from plant i to wholesaler j.
Ki = production capacity of plant i.
Dj = boxes of demand at wholesaler j.
Decision variables
xi,j = boxes to send from plant i to wholesaler j.
Model FruitTraNZ
1) minimise å 2 i =1 å5j=1 Cij xi,j subject to
2) å 5j=1 xi,j £ Ki for i = Chch, Auckland.
3) å 2i=1 xi,j = Dj for j = 1, 2, …, 5.
4) xi,j ³ 0.
Explanation
1) Objective is to minimise total transportation cost.
2) Cannot make more than capacity at the plant.
3) Satisfy demand for each wholesaler.
4) Cannot send boxes from a wholesaler to a plant.
Make the model understandable, in a reasonable way. Spell out parameters when they are represented by letters, algebraically. There is no need to explain "5". There is a need to explain "pijt". For problem 3.1-10, there is no need to spell out all the parameters, because the actual values will be used in the model. "IPDME" most definitely and fully applies when you are writing a model without any values in it, all algebraically. What you don't what to have is someone asking "What's that mean?"
The optimal solution is not always the point where the lines cross in the middle of the graph! However, the optimal solution of an LP will always be at one of the extreme points (one of the corners) of the feasible region. For a small problem, the easiest way to find this optimal solution is to find the values of the variables at each corner point, and then find the objective value of each corner point. The point with the highest objective value is the optimal solution.
What is the dual price on the constraint? If you are not sure, plug this into LINDO and find out. Then find out why the dual price is what it is.
Nothing. They are all the same.
What is the shadow price? The shadow price is the amount you would pay for another unit of resource. It needs measuring units, such as “biscuits per additional gram of flour,” or “dollars per additional kilowatt of electricity.”
Example: Cooking. Suppose you can sell every biscuit you make for $1. You want to make all the biscuits you can. You will make biscuits with whatever is in your kitchen right now. Each biscuit needs a certain amount of each ingredient.
Eventually, you will run out of some ingredients, so you cannot make any more biscuits. Let us suppose you run out of flour, and have to stop. However, you still have eggs.
How many more biscuits can you make if someone gives you more eggs? Answer: Zero, because you already have leftover eggs. The shadow price for eggs is zero.
How many more biscuits can you make if someone gives you more flour? Now this is worthwhile. Reasonably, it is about 1 biscuit/20 grams. Since you ran out of flour, you should be willing to pay up to $1 for 20 grams of flour (or $0.05 for 1 gram of flour).
The shadow price of a resource is the additional amount of happiness you would get with a 1-unit increase in that resource.
If you already have lots of the resource, and you do not expect to use it up, the shadow price must be zero.
If you would be happier with more of the resource, you can probably calculate exactly how much happier you would be.
What is its calculation? Many times, we can calculate the shadow price by hand, as in the biscuit example here. In a real world problem, the shadow price is complicated by having many resources go tight at once, by having many ingredients with different costs, etc. So the computer will do the calculation for us. Generally, you will not need to calculate it by hand.
What is its application? If you know accurately the shadow price of a resource, it tells you how hard to work to get more of it. The shadow price tells in dollars the value of every resource.
Every 6 minutes, a math model determines shadow prices for electricity throughout New Zealand. It calculates how much consumers are willing to pay for another unit of electricity, based on current supply and demand, and other information. These shadow prices (and the word "shadow" is getting in the way here) tell producers how much they will earn if they make another unit of electricity.
You practice. I have a PhD student who did Honours in Management Science. Both of us together are having a bad time trying to formulate the algebraic equations for a cutting stock model that he is studying.
To continue the biscuit example, suppose you only have eggs and flour in your biscuits. 0.1 eggs/biscuit and 20 grams flour/biscuit, straight from the recipe.
You look in the cupboard and see that you have 200 grams of flour and 12 eggs. How many biscuits can you make?
At this point, let's use a symbol to stand for the number of biscuits we want to make. This is the idea of a "decision variable": a symbol that refers to a number that we do not know yet, but that we aim to find out.
How about if we use the symbol B to be the number of biscuits. We do not know what that is yet, but if we did enough algebra, where we ended up with “B=11” or “B=149” or something like that, then we would have the Answer. We would know what decision to do. We would know precisely, in advance, how many biscuits to make.
What we want to do is:
Maximise B
where
0.1*B <= 12, the limit on eggs,
and
20*B <= 200, the limit on flour.
We can make 10 biscuits, B=10, since that is all the flour we have. We will have 11 eggs left over.
We will not usually solve these by hand. The computer can do it much better than we can.
What is the shadow price on eggs? That is, how many more biscuits can we make with 1 more egg?
Answer: Zero. We already have eggs leftover.
What is the shadow price on flour? That is, how many more biscuits can we make with 1 more gram of flour?
Answer: We could make 1/20 of a biscuit. The shadow price on flour is 0.05 biscuits per gram of flour.
How do you formulate other problems? It helps to see many of them to figure out how other people have done it.
max x1 + 15 x2 + 4000
subject to
x1 > 260 - x2
end
You have a constant 4000 in the objective function. Remove that. Also, you have a variable x2 on the right hand side of the constraint. Put x2 on the left:
max x1 + 15 x2
subject to
x1 + x2 > 260
end
You are nearly there.
"inte x" will not make the variable x12 binary. It will only make the variable x binary. To make every variable binary, you can either write:
inte x12
inte x13
inte x14
etc., for all your variables, or your can write "inte" with the number of variables, such as
inte 36
if you have 36 variables.
More precisely, if you type
inte 5
then the first 5 variables in the formulation (starting with the objective function) are made binary.
You can download a demo version of LINDO from www.lindo.com. However, it should have come with your Winston textbook. If you purchased the textbook as required, you would already have it.
LINDO shows only one solution at a time. However, you may be able see that more than one solution exists, by looking at the output. Look for “snake eyes.” This is beyond what you need for MSCI 215, but here goes. Snake eyes occurs 2 ways.
Snake eyes can occur when a variable is 0 and has reduced cost 0. In this case, there are probably alternative optima.
Snake eyes also occurs when a slack is 0 and has dual price 0. In this case, the solution is degenerate, meaning that more than the minimum number of constraints needed are binding. If the solution is degenerate, then the snake-eyes signal of alternative optima should be ignored.
But LINDO does not automatically print out the alternative optimal solutions, partly because there will be an infinite number of alternative optima. Even if you just want corner solutions, there can be a huge number of them.
Consider the following linear program:
Max x + y
subject to
x + y <= 1
x, y >= 0
The optimal objective value is 1, but the solution could come up
x=1, y=0, or
x=0, y=1. Another optimal solution is
x=0.5, y=0.5, but this is not a corner point solution, and will not be produced by the simplex algorithm.
Lindo is deterministic software - it doesn't depend on any random numbers. Given the same input, the same version of Lindo should produce the same output on different computers. However, different versions of Lindo may attack the problem differently and produce different solutions. Reordering variables or constraints may produced different solutions: "Max x + y" may produce a different solution than "Max y + x". So yes, the solution could be different, and you may not have made a mistake.
However, the objective function value should be the same for a given model, with the model variables and constraints in any order, for all LP software, on any computer. If the objective function value is different, that is more serious, and indicates a clear error somewhere. In particular, your What'sBest model should have the same objective value as your Lindo model.
If you are worried that either the Lindo or the What'sBest models are wrong, because the solutions are different, try typing the Lindo solution into the What'sBest decision cells. You should get the same objective value, and all constraints should still be feasible. If so, the models are probably consistent.
It sounds like you might just be clicking on the file in Explorer, and hoping the operating system will recognise the file as a LINDO file, then automatically open it up in LINDO. Better to open up LINDO first, and then retrieve your file with LINDO's File Open menu.
No. You cannot use parentheses in LINDO. You must write it out the long way, like this:
120 x11 + 120 x12 + 120 x13 + 120 x14 <= 500
No. In LINDO, you must write it out at length, like this:
x11 ≤ 50
x12 ≤ 50
x13 ≤ 50
and so on.
No. Your first part is not right. Changing an objective coefficient by less than its allowable decrease or increase may change the values of the variables; the basis is the same. Note the label at the top of the range report: "Ranges in which the basis is unchanged." If you change a coefficient or right hand side by an amount less than the allowable decrease or increase, you still have the same basic solution. Whether an objective coefficient or a right hand side, the values of the variables may change, but the ones that are positive will stay positive, and the ones that are zero will stay zero.
Dual prices and reduced costs are rates: change in the objective per change in the parameter. You can apply them within the range of the allowable increase and decrease, which may be bigger or smaller than 1.
You can change two or more coefficients (or right hand sides) by an amount less than their allowable decrease or increase and still have the same basic solution, if you follow the 100% rule. See Hillier & Lieberman pages 267 and 273. That would be a bit much for this course, though.
Yes, a basic variable's objective coefficient has an allowable decrease of infinity (in a minimization) only if it is already being used to the maximum (subject to the constraints). Here, we are eating both oats and milk, as you suggest:
! Model 1.
Min oats + 2 milk
st
2 oats + 3 milk >= 6
oats + 10 milk >= 12
OBJECTIVE FUNCTION VALUE
1) 3.529412
VARIABLE VALUE REDUCED COST
OATS 1.411765 0.000000
MILK 1.058824 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 -0.470588
3) 0.000000 -0.058824
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
OATS 1.000000 0.333333 0.800000
MILK 2.000000 8.000000 0.500000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 6.000000 18.000000 2.400000
3 12.000000 8.000000 9.000000
But let's increase the price of oats from 1 to 2, which is more than its allowable increase of 0.333333:
! Model 2.
Min 2 oats + 2 milk
st
2 oats + 3 milk >= 6
oats + 10 milk >= 12
OBJECTIVE FUNCTION VALUE
1) 4.000000
VARIABLE VALUE REDUCED COST
OATS 0.000000 0.666667
MILK 2.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 -0.666667
3) 8.000000 0.000000
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
OATS 2.000000 INFINITY 0.666667
MILK 2.000000 1.000000 2.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 6.000000 INFINITY 2.400000
3 12.000000 8.000000 INFINITY
We do not eat oats, and the allowable price increase is infinity. If we decrease the price of oats (compared to Model 1), from 1 to 0.1, by more than its allowable decrease of 0.8, we eat only oats.
! Model 3.
Min 0.1 oats + 2 milk
st
2 oats + 3 milk >= 6
oats + 10 milk >= 12
OBJECTIVE FUNCTION VALUE
1) 1.200000
VARIABLE VALUE REDUCED COST
OATS 12.000000 0.000000
MILK 0.000000 1.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 18.000000 0.000000
3) 0.000000 -0.100000
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
OATS 0.100000 0.100000 0.100000
MILK 2.000000 INFINITY 1.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 6.000000 18.000000 INFINITY
3 12.000000 INFINITY 9.000000
Why is the allowable decrease on oats only 0.1? Why isn't it infinity? What happens if they pay us to eat oats (so the cost is negative)? Put this in Lindo and try making the cost of oatmeal negative - you might be amused.
Profit maximising models usually have many other constraints, possibly including upper limits on demand, but more likely on capacity. An increase in one decision variable most likely results in a trade-off with other variables. Prefer to maximise profit when possible.
Show non-negativity constraints in your algebraic formulation. You do not need to add non-negativity constraints in Lindo or What'sBest.
No. Hopefully your model will be so beautifully set out, that we can infer your formulas.
No, you do not need to discuss the sensitivity analysis. Focus on the model and the key results.
The definition of reduced cost, "the amount the optimal OV would be hurt if the variable is increased by 1," does indeed make sense only for non-positive variables. Increasing a basic variable by 1 will still hurt the OV.
I like your definition, "the amount the optimal OV would be hurt if the variable is included in the solution". Perhaps we should be most precise: "the rate at which the optimal OV would be hurt when a nonbasic variable is increased." This will all make more sense in MSCI 216.
(Students, you are advised to try this with Lindo.) With "W3C4 >= 2" the RHS had an allowable increase of 0. The dual price of -5 was therefore not valid when the RHS was increased. Variable W2C3 was zero with "W3C4 >= 2", but W2C3 became 1 with "W3C4 >= 3". The basis changed.
26 March 2001, jfr.