1. Integer and mixed-integer programming
Welcome to our independent study lesson on integer and mixed integer linear programming. In the previous lesson, decisions could vary continuously. Today we add decisions that must be whole numbers or yes or no. Keep paper and the Python notebook beside you. Pause whenever a question appears. The aim is to build a model, solve it, and explain why its decisions make sense.

2. Your three-hour study route
The videos are shorter than the scheduled class because your working time matters. Use fifteen minutes to recall L P, thirty for integer geometry, and thirty five for modeling. Take a ten minute break. Then spend twenty five minutes on branch and bound, forty five on the lab, and twenty on the exit ticket. Pause the video rather than trying to finish every activity at playback speed.

3. Recall the LP certificate
Recall our maximization L P. A feasible production plan gives a value we can achieve. Feasible dual prices give an upper bound. When the two values agree, we have a certificate. Integer programming retains the idea of bounds, but an L P solution may no longer be an allowable plan. That distinction will drive the search procedure in this lesson.

4. Three kinds of decisions
Choose the variable domain from the meaning of the decision. Tonnes can usually be fractional, while an indivisible machine count cannot. A binary variable represents whether a line is available or selected. A mixed integer model may contain all three types. Making every variable integer is unnecessary and can change the engineering problem, especially when production is a continuous flow.

5. A small integer production problem
We first use a small illustrative batch problem, with objective units chosen only for teaching. Each batch of x earns three and each batch of y earns two. Two shared resources give the displayed inequalities. The coefficients remain linear. What changes relative to L P is the requirement that both batch counts be whole numbers. Sketch the continuous feasible region before adding the integer points.

6. Solve the continuous relaxation
Temporarily remove the integer restriction. Subtracting the first active equation from the second gives x equal to two, then y equal to two point five. To prove optimality, add the two resource inequalities. Their left sides sum to three x plus two y, and their limits sum to eleven. Thus every feasible point has objective at most eleven. Our point attains eleven, certifying the relaxed optimum. It still violates the whole batch requirement.

7. Rounding is not a solution method
Rounding y upward produces the plan two, three. Its resource use is five and seven, so it violates both limits. Rounding downward gives two, two and is feasible in this example. That success does not establish a general algorithm. Other problems can have infeasible rounded points or better integer points elsewhere. We need a method that verifies feasibility and provides a bound on quality.

8. The integer optimum
For a problem this small, we can list all feasible integer points. The point two, two gives ten, and no other point in the finite list gives more. This independent enumeration will later check our solver. The difference between eleven and ten is the absolute relaxation gap for this example. It is not the solver stopping gap after the optimum has been certified.

9. Bounds depend on objective direction
Removing restrictions enlarges the feasible set. Therefore a relaxed maximization can only improve or preserve the best value; it supplies an upper bound. A relaxed minimization supplies a lower bound. A feasible integer plan provides the opposite side. Before interpreting any solver bound, say whether your mathematical model is a maximization or a minimization, especially when you negated the objective in code.

10. Pause: check a proposed batch plan
Pause here and test the proposed integer plan three, one. Check both inequalities before comparing profit. The first resource use is four, which passes, but the second is seven, which exceeds six point five. Its objective is eleven, but that number is not attainable under our constraints. When you resume, keep this rule: domain checks and every resource check come before interpreting an objective.

11. A plant with two optional lines
Now move to our main engineering example. All data are illustrative, and money is measured in thousands of dollars per week. Production contributes eight per tonne on line A and six on line B, after variable costs. Opening a line incurs a weekly fixed cost, ten for A and eight for B. We must decide both whether to open each line and how much to produce.

12. Capacity and resource data
Line A can produce at most six tonnes and B at most eight. Labor requirements are two units per tonne on A and one on B. Twelve labor units are available. Total sales cannot exceed ten tonnes. This is an upper demand limit, not a requirement to produce ten. No production is feasible, and the model should retain that option if all profitable choices disappear.

13. Separate production from opening
Use a and b for continuous production amounts. Use y A and y B for binary opening decisions. These variables answer different questions. If a line is open, it can produce any allowed amount within its capacity, including zero unless we impose a minimum batch. If a line is closed, its production must be zero. The next constraints connect the two decisions.

14. Linking constraint: a ≤ 6yA
Read the linking inequality in its two cases. When y A is zero, nonnegativity and the zero upper bound force a to zero. When y A is one, a can range from zero to six. This is a linear inequality because six is a constant. We do not need to multiply two decision variables. Repeat the same reasoning for line B with capacity eight.

15. An optional minimum production level
Suppose opening A is worthwhile operationally only if it produces at least three tonnes. Add the lower linking bound a at least three times y A, while retaining the upper linking bound. The two allowed states are closed with zero production, or open with production between three and six. This is an optional scenario, not part of our baseline model. Keep that distinction when comparing numerical answers.

16. Logic with binary variables
Binary variables also encode logical choices. At most one permits both to be closed. Exactly one removes that option. The implication A requires B means that selecting A forces B to one, which is written y A at most y B. It does not mean B requires A. Test each expression on the four binary pairs. These are alternative policy examples; we do not impose them all on the baseline.

17. The complete baseline MILP
Read the full baseline model from top to bottom. The objective subtracts each opening cost once. Labor and sales constrain production. Linking inequalities prevent production on a closed line. Production remains continuous, while the opening variables are binary. Before solving, check units: every objective term is thousands of dollars per week, every labor term is labor units per week, and sales are tonnes per week.

18. Verify by enumerating opening choices
There are only four opening patterns. For each pattern, fix the binary variables and solve the remaining continuous L P. Neither line gives zero. A alone produces six and earns thirty eight after its fixed cost. B alone produces eight and earns forty. Both produce two and eight, earning forty six. Enumeration provides an independent certificate for this small model and checks our M I L P result.

19. Audit the chosen production plan
Do not stop at a solver message. Insert the proposed solution into the original equations. Labor is exactly twelve and sales exactly ten. Production on A is below six and B is at eight, with both lines open. Variable contribution is sixty four, and total opening cost is eighteen, leaving forty six thousand dollars per week. This audit is also a useful way to find coefficient-order mistakes.

20. Choose a meaningful upper bound
The constant in a linking inequality should be a valid and reasonably tight upper bound. Six comes directly from A capacity. Replacing it with one hundred, while keeping the physical capacity separately, preserves binary feasibility but lets the relaxation pay a tiny fraction of the opening cost. A bound that is too small causes the opposite problem: it removes real operating plans. Derive U from engineering limits.

21. Relax the opening decisions
Relaxing the binary decisions allows fractional opening. At production two on A, the relaxation chooses y A equal to one third and pays only one third of its fixed cost. B remains fully open. The relaxed value is fifty two point six six seven, above the attainable integer value forty six. One third of an opened line is a mathematical device for bounding, not an allowable purchase or operating decision.

22. A loose bound makes the relaxation weaker
For this comparison, retain the physical production limits six and eight. Only loosen the linking constants to one hundred. The relaxed model can then use y A equal to zero point zero two and y B equal to zero point zero eight. It earns sixty three point one six because it pays too little fixed cost. The binary model is unchanged. Without the separate physical limits, we would be comparing a different problem.

23. Branch-and-bound: maintain two values
Branch and bound maintains a feasible integer incumbent and optimistic bounds for regions that have not been eliminated. In a maximization problem, a node whose upper bound is no better than the incumbent cannot improve the answer. A node can also close because it is infeasible or its relaxed optimum is already integer. We will illustrate these ideas using the two batch variables, rather than a large industrial tree.

24. Root node: split a fractional variable
Return to the batch model with resource limits four point five and six point five. Its root relaxation gives y equal to two point five. Any integer y must lie at most two or at least three. These disjoint branches lose no integer solutions. We keep all original constraints in both branches. Branching is not rounding one candidate; it partitions the remaining search space.

25. Left branch: y ≤ 2
In the left branch, the relaxed optimum becomes two point two five, two, with upper bound ten point seven five. Now x is fractional, so split on x. The child with x at most two has the integer optimum two, two and value ten. This gives our incumbent. Its feasibility can be checked directly, and every remaining node must beat ten to matter for the optimal value.

26. Prune the other left child
The other child requires x at least three and y at most two. Its relaxed solution has x equals three and y equals zero point five, with objective value ten. Although that point is fractional, its upper bound already equals our incumbent. We can prune if our purpose is to find one optimum and certify the value. If we wanted every alternative optimum, equality pruning would need more careful treatment.

27. Right branch: y ≥ 3
The right branch initially has upper bound ten point five at one point five, three, so it cannot yet be discarded. Split x at one and two. The first child has bound ten and cannot improve the incumbent. The second requires x at least two and y at least three, forcing x plus y at least five, above four point five. No unexplored branch can now beat ten.

28. What certifies completion?
The proof combines a feasible plan with bounds covering every alternative. Our incumbent reaches ten. Each branch either has no feasible point or has upper bound at most ten. Therefore no feasible integer plan can be better. This is a global certificate for the linear integer model. Modern solvers add presolve, cuts and heuristics, so their actual node counts need not match our teaching tree.

29. Stopping early and reading the gap
A solver stopped by a time limit may have a useful feasible plan, or it may have none. Inspect status before reading variables. In our code we minimize negative profit. Therefore negative fun is the feasible profit, and negative mip dual bound is an upper bound on maximum profit. The field mip gap describes the solver gap. It is different from comparing the original L P relaxation with the integer optimum.

30. Why LP shadow prices need care
This figure is a separate machine sizing example, not the two line plant. Demand is D, each machine supplies four units, and each machine costs ten. Producing each unit also costs two. For nonnegative demand, the required machine count is the ceiling of D divided by four. Total minimum cost is ten times that count plus two D. Within a fixed machine count, cost rises with slope two. Crossing capacity requires another machine and a cost jump. Do not extrapolate an L P shadow price across that switch.

31. Python lab: predict before running
Open the guided notebook from the course page. The calculations use Python with NumPy and SciPy, version one point nine or later. No paid solver is required. Run cells from top to bottom and predict each result before executing it. This notebook is a worked tutorial, and an executed reference copy is available. The six independent exercises are on the separate practice page and printable worksheet. Try them before opening the worked solutions.

32. Step 1: choose a fixed variable order
Start by writing the variable order explicitly: a, b, y A, y B. Every coefficient vector and matrix column must follow that order. SciPy minimizes, so production contribution receives negative coefficients and opening costs positive coefficients. After solving, negate the minimized objective to report profit. Do not negate the constraints, and do not forget the fixed costs when checking the answer.

33. Step 2: encode variable domains
SciPy uses zero for continuous variables and one for integer variables in this example. To make an integer variable binary, also restrict its lower and upper bounds to zero and one. Setting integrality alone does not make a variable binary. We keep physical upper bounds on production as well. This makes later comparisons with loose linking constraints clear and helps catch mistakes.

34. Step 3: build the constraint matrix
Write each inequality in the same variable order. The labor row is two, one, zero, zero. The sales row is one, one, zero, zero. Bring linking terms to the left, giving one, zero, minus six, zero, and zero, one, zero, minus eight. Each linking row has right hand side zero. The notebook prints the matrix so you can compare it with the model before solving.

35. Step 4: solve and check status
Call milp using the coefficients, domains and linear constraints. First check the status and message. For the baseline, the solver should find production two and eight, with both opening variables one, and profit forty six. Small floating point differences are normal. A result printed near zero should be judged with a numerical tolerance, but you should not round away a large feasibility error.

36. Step 5: audit every constraint
Now audit the result independently of the solver status. Multiply the matrix by the variable vector and compare each row with its upper bound. Check lower and upper variable bounds, and check that binary entries are close to zero or one. Finally recompute eight a plus six b minus ten y A minus eight y B. A matching objective alone cannot detect every modeling error.

37. Step 6: compare relaxation and MILP
Run the same model with all integrality flags set to zero. Confirm the relaxed value is about fifty two point six seven and y A is one third. Then restore the two integer flags. Finally enumerate the four opening patterns and solve a continuous L P for each. Agreement between enumeration and M I L P is an independent check of this small model, not a proof that all future code is correct.

38. Step 7: change one assumption
Change one assumption at a time, resetting all other inputs to baseline. Reducing the sales cap to eight selects only B and gives forty. Raising B opening cost to twenty selects only A and gives thirty eight. Adding A minimum production three gives both lines open, production three and six, and profit forty two. These different decisions show why sensitivity experiments must state exactly what changed.

39. Step 8: consider an extra capacity module
Introduce another binary decision for one optional labor capacity module. It adds four labor units and costs seven thousand dollars per week. Move minus four k into the labor constraint and add plus seven k to the minimization objective. The best purchase plan produces six and four, with both lines open, and earns forty seven after all costs. Compare with forty six without the module: the net benefit is only one.

40. Step 9: compare purchase costs
Separate the operating improvement from the purchase price. With the module available, the best operating profit after line opening costs is fifty four, compared with forty six without it. The gross improvement is eight. A module cost of seven leaves one of net benefit. A cost of ten is too high, so the optimized decision is not to buy, leaving profit forty six. Never subtract the module cost twice.

41. Independent exercises
Pause and complete the first three exercises on the separate practice page or printable worksheet. The first changes the small integer batch model, not the plant model. The second and third each start from the original plant baseline. Write the changed equation, predict the decision, solve, and check feasibility. For the batch question, enumerate the feasible integer points. For the plant questions, compare the permitted opening patterns. Check whether alternative plans tie.

42. Independent exercises: decisions and bounds
For exercise four, set the capacity module cost to eight. Check both purchase states because a solver may return only one of multiple best plans. Exercise five adds a minimum batch of four for A. Exercise six is conceptual: an incumbent of forty six and upper bound forty eight does not prove optimality, but it limits the possible improvement. Write the bound interval without confusing it with the final answer.

43. Exercise solutions: batch and sales cap
Check your reasoning against these answers. With the first batch resource limit at four, two, two remains feasible and gives ten. Enumeration verifies it is best. For plant sales cap six, A alone gives forty eight minus ten, or thirty eight, beating the other patterns. Under the at most one policy at baseline demand, B alone gives forty and beats A at thirty eight. Verify each statement by comparing allowed patterns.

44. Exercise solutions: module and minimum batch
At module cost eight, the improved operating profit fifty four minus eight equals forty six, so both purchase states can be optimal. At minimum A production four, opening both gives at most thirty eight, while B alone still gives forty. In the bound question, the optimum lies between forty six and forty eight. The absolute remaining gap is two; no exact optimum is certified until the bounds meet or an acceptable tolerance is justified.

45. Exit Ticket: explain, then submit
Use the online exit ticket after completing the lab. There are four required written questions and an optional reflection. Explain the reasoning rather than submitting only numbers. You may answer in Thai or English. The form is anonymous, and the instructor sees your response privately. Wait for the saved receipt before closing the page. Pause now, and do not advance to the solutions until you have attempted all four questions.

46. Exit Ticket questions
Question one asks you to interpret the linking inequalities in both binary states. Question two distinguishes a feasible integer decision from an optimistic relaxation. Question three changes the module cost to nine while all other baseline data stay fixed. Question four uses maximization node bounds of forty five, forty six and forty eight with incumbent forty six. Explain which nodes can be pruned if we seek one optimal solution.

47. Exit Ticket solutions: linking and relaxation
For question one, substitute zero and one into both linking inequalities. Zero forces a to zero, while one allows production from three to six. The figure illustrates only question one. Question two returns to the baseline without that minimum batch constraint. Its relaxed solution pays only one third of A opening cost. That opening fraction violates the binary rule. The larger relaxed profit is an upper bound from a larger feasible set, not an attainable M I L P outcome.

48. Exit Ticket solutions: purchase and pruning
At cost nine, buying the module gives fifty four minus nine, or forty five. Not buying gives forty six, so reject the purchase. The incremental benefit of buying is negative one. For pruning, nodes with bounds forty five and forty six cannot improve incumbent forty six. A node bounded by forty eight might improve it, so it needs further processing. Its upper bound is not a promise that forty eight is attainable.

49. A reliable MILP workflow
A reliable model starts with clear decisions and units. Use binary variables for choices, continuous variables for divisible quantities, and tight valid bounds to connect them. After solving, audit the equations and objective rather than trusting a single status message. When assumptions change, reoptimize and compare complete net outcomes. These habits transfer to equipment selection, production scheduling and process network design beyond our small examples.

50. Resources and next steps
Use the official SciPy documentation to confirm the exact definitions of solver fields. The course page contains this deck, the five narrated chapters, the guided lab, practice exercises and separate solutions. Save your notebook and your exit ticket receipt. When we meet again, bring an example where your prediction differed from the solver and explain the constraints you checked. That comparison is often where the most useful learning happens.