Video transcript:

The year is 1941 and World War II is underway. Dr. George Dantzig, soon to be known as the Father of Optimization, has been assigned to the Combat Analysis Branch at the US Air Force. His office had been tasked with collecting data about sorties flown, bombs dropped, and aircraft lost. They are to analyze that data and build mathematicaI models to reduce costs to the army and increase losses to the enemy.

Dr. Dantzig quickly recognized that several defense challenges he was modeling were actually Linear Programs where both the objective function and resource constraints were expressed as linear equations. One of the problems that Dr. Dantzig studied was to find the best assignment of 70 persons to 70 jobs. In this decision problem, we have 70 people and we have 70 jobs.

We need to decide which person [p] is assign to which job [j]. Each person p is assigned to only one job. We want to find that person to job assignment for which the total value of the assignment is highest possible or maximum.

This decision problem isn’t easy by any means. Once you make one assignment, it limits what other assignments you can make next since the person and the job assigned cannot be assigned anymore. Note that for this decision problem, there are 70! such options, which is approximately 1 trillion times 1 trillion times repeated 7 times.

That’s more options than the number of atoms in the observable universe! Dr. Dantzig was able to model the person-job assignment as a mathematical model but realized there were no techniques available to solve this model. Realizing that he couldn’t explicitly go through all possible options, Dr. Dantzig developed an algorithm that “implicitly” lists all options while ensuring that the best solution is always identified.

His research resulted in an algorithm called the “Simplex Algorithm” that guaranteed the best solution of the assignment problem that could be solved by hand in a few days (since computers were still being developed). Simplex Algorithm was a major discovery that showed that to solve a mathematical model, we do not have to calculate all options but only a few options.

This implicit identification of all options is the key to solving decision problems with a large number of decision variables. With further advances in optimization technology and computers since 1940s, we can now solve linear programs with millions of variables within seconds. Mixed Integer Programing or MIP is a linear program where some decision variables are required to take integer values, i.e., they cannot take decimal values such as 2.3 or 2.5. MIPs are much more popular in modeling real-world problems since often whole numbers make more sense than fractional numbers.

Though nearly a century has passed since Dr. Dantzig solved the person-job assignment problem, LP and MIP continue to show up in numerous practical settings. Interestingly, truckload problems aren’t much different than those solved by Dr. Dantzig involving assignment of persons to jobs, A large trucking carrier has hundreds of drivers and thousands of loads to be moved for customers in a week.

The dispatcher must decide what next load should be assigned to each driver when they finish the current assignment considering drivers’ current locations, hours of service and their preferences. This decision problem is known as the Dispatch Optimization. Let us summarize how we solve business problems using MIPs. We define mathematical variables for each decision, write business constraints as mathematical equations, and represent the objective function also as a mathematical equation.

Then, use some MIP Solver to solve the MIP, and use the results to optimize your business. Now since you understand Linear Programming and Mixed Integer Programming, go be the smartest person in the room at your next networking event.