Math317Fa26 Lec13 IntegerProgramming
Watch on YouTube →
Overview
Steven Miller introduces integer programming as a way to model decisions that must be discrete, such as whether a plane flies or a worker is scheduled, and shows why its optimization can differ sharply from continuous linear programming. He develops a toolkit for encoding binary indicators, logical conditions, thresholds, minima and maxima, and piecewise-linear behavior, then applies the modeling ideas to path puzzles and Sudoku.
Key takeaways
- A continuous relaxation can substantially overstate what is achievable with indivisible choices: the 100 kg knapsack example yields about $294 when divisible but only $200 when items must be whole units.
- Binary variables let integer linear programs express yes-or-no decisions, including whether a plane flies, whether a quantity is nonnegative, and whether exactly one of two conditions holds.
- Finite bounds and a smallest discrete unit make it possible to encode sign tests with auxiliary binary variables and big-M-style inequalities.
- Logical requirements such as exclusive OR, inclusive OR, and if-then rules can be translated into linear constraints, making complex scheduling rules modelable.
- Encoding Sudoku digits as powers of ten turns the requirement that each digit appear once into the single sum 111,111,111 for each row, column, and 3×3 block.
Chapters
- Steven Miller contrasts real-valued linear programming, addressed earlier with the simplex method, with integer programming, which restricts choices to discrete values.
- He notes that integer programming is significantly harder to solve exactly, though practical methods can often find solutions close to optimal.
- The central modeling question is which real-world constraints can be expressed as an integer linear program.
- Airline scheduling uses binary decisions for whether a plane takes a particular flight, while also enforcing pilot-hour limits and mandatory rest periods.
- Miller describes a movie-theater schedule developed with colleagues that improved on a manually planned schedule and increased expected profit despite leaving a longer gap on one screen.
- Worker schedules can encode availability, family obligations, requested time off, and preferences such as working Saturday only if necessary.
- The example has a 100 kg capacity and three items: 51 kg worth $150, 50 kg worth $100, and 50 kg worth $99 per unit.
- The $99 item is dominated by the $100 item because both weigh 50 kg, so there is no reason to choose the lower-value option.
- With divisible items, taking 100/51 of the first item earns about $294; with whole units, two 50 kg items earn $200, while the 51 kg item leaves insufficient capacity for another item.
- Miller assumes each quantity is bounded by some finite limit and takes values in multiples of a smallest unit δ.
- A binary variable Z_A can mark whether a bounded quantity A is nonnegative, enabling models to represent conditions that depend on a sign test.
- For movie tickets, A could represent demand minus theater capacity, allowing a model to detect excess demand and assign a penalty.
- The sign indicator is constrained to be binary, so Z_A can only equal 0 or 1.
- Two additional inequalities use the bound N_A and the discrete step δ to force Z_A=1 when A≥0 and Z_A=0 when A<0.
- Miller emphasizes that auxiliary variables and inequalities make a condition expressible as an integer linear program, though they may increase the computational burden.
- Separate binary indicators for A≥0 and B≥0 encode logical OR conditions: requiring their sum to equal 1 gives exclusive OR, while requiring a sum of at least 1 gives inclusive OR.
- The distinction matters in examples such as sports outcomes: a game can end in a tie in some sports, while baseball requires one team to win.
- Miller connects these constraints to tracking wins and elimination scenarios, including how the 2004 Red Sox secured a wild-card berth earlier than some accounts reported.
- Integer programming can encode if-then statements, such as adjusting movie demand when Spider-Man and a Star Wars movie are scheduled at the same time.
- A truncation construction can make a variable contribute only after it reaches a threshold, representing situations where small quantities are not worthwhile.
- For an oil supplier, a threshold can encode a minimum level of demand required before serving a city becomes profitable.
- Miller describes formulations that create variables equal to the minimum or maximum of two quantities.
- A maximum-flow variable can track the peak traffic across a bridge, while a minimum-speed constraint can represent the 50 mph limit in the film Speed.
- Absolute values and piecewise-linear functions can be built from sign indicators and if-then rules, allowing different linear formulas in different input ranges.
- For a grid puzzle with four colors, assign each cell (i,j) a color variable taking values from 1 through 4.
- Constraints must ensure colored paths connect each pair of matching dots without creating invalid crossings or blocking another route.
- The model only needs a feasible solution, so its objective function can be arbitrary, for example minimizing the color assigned to one particular cell.
- Represent each Sudoku cell choice using one of the nine values 10^0 through 10^8 rather than directly using digits 1 through 9.
- Requiring the nine encoded values in a row, column, or 3×3 block to sum to 111,111,111 forces every power of ten to appear exactly once.
- This converts the no-repeated-digit rule into a sum constraint; Miller assigns it as a problem to formulate and compare with a direct integer-programming encoding.
Transcript excerpt
0:00 Welcome to math 317 operations research. And what I want to do today is talk a little bit about what can be done with linear programming. How many of you have taken a almost a good stats class? I'll just say a stats class that included the method of least squares or best fit lines. I took mine from a psychology department, so I'm never sure what content we actually covered. It's one of my favorite results of all time. But if you want to use the, you know, if you want to find the best fit line, your data should be linear. Most relationships aren't linear, but with a logarithmic change of variables, a lot of times nonlinear data can become linear. So what we're going to do right
0:47 now is we're solving linear programming problems. We did the simplex method which said if we had real input and you we had you know real variables we can find a solution. We have not analyzed because this is just a first class how quickly we can find a solutions. The simplex method for the most part runs very quickly. We have not done that but I've shown you some other algorithms that initially look like they could be slow. The uklitian algorithm looks like you go down only by one worst case scenario every single time. If your number is of size 10 to the 400, that's terrible. But the worst case scenario can't happen every single time. In the Ukidian algorithm, every two iterations, you drop by at least a factor of two. That means it runs in logarithmic time. It's efficient. We can use it. I'm just using that as a
1:35 hope and a prayer that you will accept that the simplex method runs quickly without doing all those calculations. We
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.