Combinatorial Optimization, Mixed Integer Programming and Network Theory

This chapter covers basic theoretical and practical aspects of Mixed integer Programming (MIP) both theoretical and practical topics related to Continuous Linear Programming (CLP) and Network Theory using Python. Like, Continuous Linear Programming, MIP uses linear equations to model optimization problems. However, some of the decision variables can only take Integer values. Feasible solutions are no longer found at vertices of the feasibility region, and this fundamental fact drastically increases the complexity of MIP problems. Network Theory provides a framework rather useful to solve MIP problems, and therefore it is also introduced in this course. CLP allows us to model, solve and analyse the solution of optimization problems using linear equations. “The world is not linear” but still, CLP is a really powerful tool to solve a plethora of real world optimisation problems.

Tutorials

This section contains some basic tutorials:

Contents:

• Introduction to Combinatorial Optimization
• Algorithm Efficiency Assessment
• Genetic Algorithms
• Solving Sudoku's with a Genetic Algorithm
• Introduction to Mixed Integer Programming
• MIP in Python using PuLP
• Transportation Problems
• Graph Theory tutorial
• Graph Theory tutorial: Routing

Exercises

In this section you have a collection of CLP problems sorted by difficulty:

• Easy problems: You can tackle these problems after the first lesson on MIP.

• Normal problems: These problems require that you are familiar with concepts like Duality and the Simplex method.

• Hard problems: This is the type of problems that definitively get you ready for the exam.

Contents:

• Tarmacking shifts (Easy MIP modeling exercise)
• Allocation Orders to Machines (Easy MIP modeling exercise)
• Planning production and inventories (Normal MIP modeling exercise)
• Truck Deliveries (Easy MIP transportation problem modeling exercise)
• Arcadia Deliveries (Normal MIP transportation problem modeling exercise)
• Distribution Problem Example (Normal MIP modeling exercise)
• Transport Planning (Normal MIP modeling exercise)
• Plastic Injection Production Planning (Hard MIP modeling exercise)
• Machinery Transport Planning (normal graph theory exercise)
• Overbooking (normal graph theory exercise)
• Production Planning (normal graph theory exercise)
• Production Sequencing (normal graph theory)
• Planet Express Deliveries (normal transportation problem)
• Earth's Fleet Assignment (normal MIP and graph theory problem)
• 3D Printing Precision Parts (normal MIP modeling exercise)
• Spellman's Network Optimization (Normal transportation problem)
• Professor's X School Network Optimization (Normal transportation problem)

Solved Exercises

In this section you have the solution to the different exercises.

Contents:

• Tarmacking shifts (Easy modeling exercise)
• Planning production and inventories (Normal modeling exercise)
• Allocation Orders to Machines (Easy modeling exercise)
• Truck Deliveries (Easy transport exercise)
• Arcadia Deliveries (Normal MIP transportation problem modeling exercise)
• Distribution Problem Example (Normal modeling exercise)
• Transport Planning (Normal modeling exercise)
• Plastic Injection Production Planning (Hard MIP modeling exercise)
• Machinery Transport Planning (normal graph theory exercise)
• Overbooking (normal graph theory exercise)
• Production Planning (normal graph theory exercise)
• Production Sequencing (normal graph theory)
• Planet Express Deliveries (normal transportation problem)
• 3D Printing Precision Parts (normal MIP modeling exercise)
• Spellman's Network Optimization (Normal transportation problem)
• Professor's X School Network Optimization (Normal transportation problem)

Python libraries

This section contains Python library tutorials:

Contents:

• MIP with Python
• Networkx Tutorial