Math317Fa26 Lec12 SimplexMethod
Watch on YouTube →
Overview
Steven Miller connects mathematical problem-solving to asking useful questions, beginning with a discussion of reported AI-generated results and Lean proof certificates before revisiting Euclid's proof that there are infinitely many primes. He then formulates an oil-shipping transportation problem as a linear program and explains the simplex method's two phases, including how an augmented problem finds feasibility and how basis exchanges guide optimization.
Key takeaways
- Euclid's product-plus-one proof guarantees a prime outside any proposed finite list, but it does not imply that each successive product-plus-one number is itself prime.
- The Euclid-Mullin sequence generates distinct primes by adding new prime divisors of product-plus-one numbers, and its patterns motivate questions that computations alone do not settle.
- An oil transportation model minimizes ∑ᵣ∑ₘ gᵣₘxᵣₘ subject to refinery supply limits, market demand equalities, and nonnegative shipment quantities.
- Unused refinery supply can be represented by a zero-cost dummy market, converting a supply inequality into an equality without changing the shipping objective.
- Phase I minimizes the sum of auxiliary variables in Ax + z = b; a zero minimum proves original feasibility, while a positive minimum proves infeasibility.
- In Phase II, an invertible basis A_B yields a dual candidate yᵀ = c_BᵀA_B⁻¹; dual feasibility certifies optimality when its objective matches the primal feasible solution.
Chapters
- Steven Miller opens with a report of more than 700 AI-produced papers addressing over 300 open problems, noting that some results have Lean certificates and others still require review.
- He emphasizes that Lean certificates increase confidence but are not infallible, citing a known Lean bug that allowed a false proof related to the 3x+1 problem.
- Miller frames asking worthwhile questions about mathematical data as a key skill as AI capabilities change.
- Assume the complete prime list is p₁ through pₙ and form N = p₁p₂⋯pₙ + 1.
- If N is prime, the assumed list omitted a prime; if N is composite, none of the listed primes divides N because each leaves remainder 1.
- In either case, the assumption that there are finitely many primes leads to a contradiction.
- The initial terms arise from the construction 2, then 2·3+1 = 7, then 2·3·7+1 = 43.
- The pattern does not always produce a prime: a later product-plus-one number has 13 as a new prime divisor.
- Miller recommends gathering more data before trusting a conjecture and points to open questions about which primes occur and how long it takes to reach a prime of a given size.
- Let sᵣ denote refinery r's supply, dₘ market m's demand, and gᵣₘ the cost of shipping one unit from refinery r to market m.
- Define xᵣₘ as the number of units shipped on that refinery-to-market route, with xᵣₘ ≥ 0.
- The basic objective is to minimize total shipping cost while meeting market demand and respecting refinery supply.
- For each refinery r, total shipments satisfy ∑ₘ xᵣₘ ≤ sᵣ.
- For each market m, incoming shipments satisfy ∑ᵣ xᵣₘ = dₘ in the basic model.
- The objective sums route costs times shipped quantities, ∑ᵣ∑ₘ gᵣₘxᵣₘ.
- Miller distinguishes exact-demand assumptions from extensions that allow market capacity, extra reserves, or unmet demand.
- To convert refinery supply inequalities into equalities, add a dummy market where unused oil can remain at its refinery.
- Assign the dummy route a shipping cost of zero so retained oil does not change the objective.
- Miller contrasts hard movie-scheduling constraints, such as not assigning overlapping films to one screen, with soft preferences such as starting a movie every 20 minutes.
- Additional scheduling considerations include simultaneous movie endings, hallway crowds, ticketing demand, and theater-cleaning labor.
- The canonical problem is to minimize cᵀx subject to Ax = b and x ≥ 0, with A an m-by-n matrix and m < n.
- Miller assumes the rows of A are linearly independent and b is not a combination of fewer than m columns, conditions used to simplify the analysis.
- The assumption b ≥ 0 can be arranged by multiplying any equation with a negative right-hand side by −1.
- With more variables than equations, the model can have many feasible solutions, making optimization meaningful.
- Phase I determines whether a basic feasible solution exists and returns one when it does; otherwise it reports infeasibility.
- A basic feasible solution satisfies Ax = b and has linearly independent columns corresponding to its nonzero variables.
- Phase II starts from a basic feasible solution and seeks an optimal basic solution, or detects a direction along which cost decreases without bound.
- The apparent circularity between phases is avoided because Phase II is applied to a related problem for which a starting feasible solution is already known.
- Introduce nonnegative auxiliary variables z and solve Ax + z = b, equivalently [A I][x; z] = b.
- The choice x = 0 and z = b supplies an initial feasible solution because b ≥ 0.
- Minimize the auxiliary cost ∑ᵢ zᵢ: an optimum of zero gives a feasible solution to the original Ax = b problem.
- If the minimum remains positive, at least one auxiliary variable is needed, so the original constraints are infeasible.
- Under the stated assumptions, a basic feasible solution has exactly m nonzero entries; their columns form a basis matrix A_B.
- Since A_B is invertible, the basis variables solve A_Bx_B = b, and the corresponding dual candidate is yᵀ = c_BᵀA_B⁻¹.
- If y satisfies yᵀaⱼ ≤ cⱼ for every column aⱼ, primal and dual feasible costs agree, certifying optimality.
- When the dual candidate is infeasible, simplex algebra identifies a column exchange that improves the solution; continued improvement may also reveal unbounded cost.
Transcript excerpt
0:00 Welcome to math 317 operations research. This is lecture 12. Uh for those of you who are not following all the math posts, open AAI released over 700 papers yesterday at 6 pm on over 300 different major open problems with tremendous results. Incredible. Uh some of the problems are completely resolved. Others made more progress that has been made in decades. And so yet again the structure of this class is in flux because things have changed from the start of the semester to now in terms of just what is capable of being done with the tools that are out there and trying to prepare you. You know we are talking right now as a math community as to just what does this mean for what skills we want you to get because this is no longer using millions of
0:49 dollars of computer time. This is now just using the next generation that hasn't been released yet and it seems to be doing it without massive interactions with humans with just like one initial prompt. >> Have they been >> I I don't want to say too much because this is being recorded so I'll try to end class early. >> Have they have been formally reviewed? >> Uh they have not all been formally reviewed but a lot of them have lean certificates not all. And so some of these have then been fed into other things that have verified. So some of them have already been verified and because they have lean certificates, it's almost surely true that they are correct. There are some things that have been proved with lean certificates that are false because some people have exploited known bugs in lean. There was one I think on the 3x plus1 problem with a recursive flaw that has since been
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Steven Miller.