UPI Study › Courses › Quantitative Analysis › Free lessons › Lesson 9.2 Free with a free account
Indivisible by Design
Quantitative Analysis · Chapter 9: Linear and Integer ProgrammingSection 9.2 · lesson 41 of 5512 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Quantitative Analysis.
Lesson complete
Earn the 3 college credits for Quantitative Analysis
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Solving for the Best Outcome →← Constraints as EquationsNext lesson: Solving for the Best Outcome →
In this lesson
Using integer programming to solve budgeting and distribution challenges.
- Distinguish pure integer, mixed integer and binary programs
- Formulate business decisions as integer programs
- Explain why LP relaxation and rounding are unreliable
- Solve a capital-budgeting problem by enumeration
Transcript
Everything said in the video, section by section (1,771 words). Read along, or search it.
Linear and Integer Programming · Section 9.2
Indivisible by Design
Welcome to Chapter nine point two of Quantitative Analysis. Indivisible by Design. This section is about decisions that come in whole units. Linear programming is happy to hand you a fraction of an answer. Integer programming refuses, and that refusal changes everything. By the end you will be able to tell pure, mixed and binary programs apart. You will formulate real business decisions as integer programs. You will know why relaxing and rounding is a trap. And you will solve a capital budgeting problem from first principles.
Why Whole Numbers
You Cannot Hire 0.7 of a Worker
Standard linear programming lets a decision variable take any value it likes. In a continuous setting, that flexibility is exactly what makes the maths tractable. It is also what makes some answers useless. A solver might tell you to assign two point seven workers to a shift. Or to ship one point four truckloads out of a warehouse. Or, most memorably, to open six tenths of a factory. Each of those answers is mathematically optimal and operationally meaningless. You cannot hire seven tenths of a worker. Integer programming fixes this by demanding whole numbers from some or all variables. That single restriction buys you an enormous amount of modelling honesty. It also costs you an enormous amount of computing time, as we will see.
Three Families
Pure, Mixed and Binary
Integer programs come in three families, and the difference is simply which variables must be whole. A pure integer program, abbreviated I L P, requires every decision variable to be an integer. A mixed integer program, or M I P, has some integer variables and some continuous ones. A binary integer program restricts variables to just the values zero or one. You will see it written as B I P, or as a zero-one program. Of the three, the binary program is the one you will meet most often in business. The reason is simple: an enormous number of managerial decisions reduce to a single yes or no. Do we fund this project? Do we open this warehouse? Neither question has a sensible fractional answer. So the zero-one variable is not a simplification, it is the honest representation.
Binary Variables
Four Ways a Yes/No Becomes a Model
Binary variables are the workhorse of integer programming. The convention is straightforward: the variable equals one if the action is taken, and zero if it is not. Four canonical applications appear in almost every operations research course. First, capital budgeting, where a firm has candidate projects, each with a known cost and expected net present value. The budget is fixed, so the task is choosing the best affordable subset. Second, facility location, where you choose which sites to open and how much to ship from each. Fixed opening costs are traded off against variable transportation costs. Third, scheduling, where one binary variable covers each worker and shift pair. Coverage constraints force each period to meet minimum demand, and this is how airlines roster crews and hospitals schedule nurses. Fourth, set covering, which insists every demand location is served by at least one facility. Fire stations, ambulance bases and cell towers are all placed this way.
Logic As Algebra
The Constraints That Carry the Logic
The variables are the easy part. The constraints are where the thinking lives. Take facility location, where you must stop the model shipping goods out of a warehouse it never built. The linking constraint does this. The shipment from a site to a customer must not exceed big M, times the open indicator for that site. If the site is closed, the indicator is zero, so every shipment from it is forced to zero. If the site is open, the indicator is one, and big M is loose enough not to bind. Now take set covering. For each location, the sum of the facility indicators that can serve it must be at least one. Notice that facility location mixes a binary open decision with a continuous flow decision. That combination is what makes it a classic mixed integer program. Binary variables can also express if-then logic, either-or choices, and at most k limits. Mastering those tricks is the real skill here, because the solver only optimises what you actually wrote down.
Why IP Is Hard
Relax First, Then Bound
Once a model is formulated, somebody has to solve it. For linear programs, the simplex method reaches the optimum quickly in practice. Integer programming is fundamentally harder. Most variants are what computer scientists call N P hard. In plain terms, the work can grow explosively as the problem grows. So the first move is almost always the same. Drop the integrality requirement and solve the linear program that remains. For a maximisation problem, that relaxed optimum is an upper bound on the integer optimum. For a minimisation problem, it is a lower bound instead. The logic is worth pausing on. The relaxation has strictly more freedom, so it can never do worse. That bound is cheap to compute, and it informs every serious integer programming algorithm.
The Rounding Trap
Why Rounding Is Not a Solution Method
Here is the mistake almost everyone makes once. Solve the relaxation, round the fractions, declare victory. It does not work, and the reason is worth seeing on real numbers. Relax the capital budgeting problem coming up later in this chapter. The relaxed answer funds projects two and three in full, and about eighty three per cent of project five. That gives a bound of two hundred and forty point eight, in thousands of dollars. The true integer optimum is two hundred and thirty eight. Now try rounding. Round project five up to one, and the portfolio costs five hundred and thirty. The budget is five hundred, so that answer is simply infeasible. Round it down to zero instead, and the value collapses to one hundred and seventy. That is sixty eight thousand dollars below the true optimum, from one rounding decision. Rounding is a heuristic check. It is never a solution method.
Branch and Bound
The Standard Exact Algorithm
Branch and bound is the standard exact algorithm for integer programming. It explores a tree, and every node of that tree is a linear program. Solve the linear program at the node and look at what comes back. If the solution is integer-feasible, keep it as the incumbent, the best whole-number answer found so far. If instead some variable comes back fractional, you branch. Suppose variable k lands at fractional value v. One child adds the constraint that k is at most the floor of v. The other child adds that k is at least the ceiling of v. Between them, those two children cover every integer possibility, and exclude the fraction. Then comes the step that makes the method practical. If a node's bound is worse than the incumbent, the whole subtree is pruned. You never explore it, because nothing inside it can possibly beat what you already hold. This is the engine inside commercial solvers like Gurobi and CPLEX, and open source ones like C B C and G L P K. Modern solvers layer cutting planes, heuristics and presolve on top of this core idea.
Worked Example
Six Projects, One Fixed Budget
Let us make all of this concrete. A firm has a capital budget of five hundred thousand dollars. It is evaluating six candidate projects, labelled P one through P six. Each project has a one-time cost and an estimated net present value, both quoted in thousands of dollars. Project one costs one hundred and twenty and returns fifty five. Project two costs one hundred and fifty and returns seventy two. Project three is the biggest, at two hundred, returning ninety eight. Project four costs ninety and returns forty. Project five costs one hundred and eighty and returns eighty five. Project six costs one hundred and ten and returns forty eight. Step one is the decision variables. One variable per project, equal to one if it is funded. Notice what the model quietly assumes. Costs and values are known, and a project cannot be part-funded.
Formulation
Objective, Budget, Binary
Step two is the objective function, and it is just a weighted sum. Maximise fifty five times x one, plus seventy two times x two, plus ninety eight times x three. Then forty times x four, plus eighty five times x five, plus forty eight times x six. Because each variable is zero or one, this sum simply adds up the values of the chosen projects. Step three is the constraints, and there are only two. The budget row uses the same shape, but with costs as the coefficients. One hundred and twenty x one, plus one hundred and fifty x two, and so on, up to five hundred. The second constraint is the integrality condition. Every variable must belong to the set containing zero and one. Look carefully at what is and is not linear here. The objective is linear, and so is the budget row. Only that last binary line separates this from an ordinary linear program. Drop it and simplex solves the problem instantly. Keep it and the problem turns combinatorial.
Enumeration
64 Portfolios, One Winner
Step four is to solve it, and with only six projects we can be brutally direct. Six binary variables give two to the sixth possible portfolios, which is sixty four. We test each one against the budget and record its total value. The winner is projects one, three and five. Its cost is one hundred and twenty, plus two hundred, plus one hundred and eighty. That is exactly five hundred, so the entire budget is consumed. Its value is fifty five, plus ninety eight, plus eighty five, which is two hundred and thirty eight. The runner up, projects three, five and six, reaches two hundred and thirty one. A four-project portfolio, one, four, five and six, also spends the full budget. But it delivers only two hundred and twenty eight, so more projects is not automatically better. And adding project six to the winner pushes the cost to six hundred and ten, which is over budget. No feasible portfolio beats two hundred and thirty eight thousand dollars.
Chapter Summary
What to Carry Forward
Let us pull the threads together. Integer programs enforce whole-number decisions, and that is what makes them indispensable. Workers, warehouses and projects simply do not come in fractions. Pure, mixed and binary programs differ only in which variables must be integer. Binary variables drive the four big application families you met earlier. The relaxation gives a genuinely useful bound, but its solution is usually fractional. Rounding that solution can leave you infeasible, or quietly poorer. Branch and bound is the canonical exact method, splitting and pruning its way to the answer. One closing warning about how these optima behave. Cut the budget to four hundred and fifty thousand and the answer becomes projects one, two and five. Project three, the star of the original solution, drops out entirely. Integer optima do not degrade gracefully. A small change in the budget can rewrite the whole portfolio.
About Quantitative Analysis at UPI Study
Quantitative Analysis (Math 250) is a self-paced online course of 55 video lessons in 13 chapters, from decision analysis and simulation to inventory and queuing models, project scheduling, linear programming and transportation models. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Math courses Every course with PRO →
Compare: Statistics vs Quantitative Analysis
Why take it here
Why students take Quantitative Analysis with UPI Study
Where the credit goes
Universities that work with NCCRS
Quantitative Analysis carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Indivisible by Design
What is the difference between pure, mixed and binary integer programming?
Why can't you just round a linear programming solution to get an integer answer?
How does branch and bound solve integer programs?
How do you solve a capital budgeting problem with binary variables?
About the Quantitative Analysis course
How many college credits is Quantitative Analysis?
How much does Quantitative Analysis cost and what is included?
Which universities accept UPI Study credits?
How long does Quantitative Analysis take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Quantitative Analysis.
55 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →