Deterministic OR Methods for Data Scientists

Learning Outcomes

Learning Outcomes

Having successfully completed this module you will be able to:

• describe graphical method, simplex methods (primal and dual) and apply them to solve relatively small LP problems
• derive the range of the RHS until the optimal basis start changing and the corresponding range of the optimal value (Section 4 (Sensitivity))
• describe situations when sensitivity analysis is used (Section 4 (Sensitivity))
• describe the method for finding initial BFS and to avoid cycling (Section 2 (Simplex Method))
• define basic solution, basic feasible solution, optimal BSF of LP problems in standard form (Section 2 (Simplex Method))
• describe relationships for primal-dual pair in terms of optimality, feasibility and boundedness (Section 3 (Duality))
• describe duality theorems and complementary slackness
• write the general form of a mathematical programming problem (Section 1 (Intro to MP))
• describe the dual Simplex method (using dictionary) (Section 3 (Duality))
• describe the motivation for using duality and formulate the dual problem given the primal
• distinguish between LP, IP, and NLP (Section 1 (Intro to MP))
• describe the idea behind the Simplex method (Section 2 (Simplex Method))
• formulate various problems using LP, IP and NLP
• state LP duality theorem (Section 3 (Duality))
• interpret shadow price and primal-dual pair in terms of profit maximization vs. resource scarcity (Section 3 (Duality))
• describe 5 steps for formulating a mathematical programming problem (Section 1 (Intro to MP))
• describe and prove week duality theorem (Section 3 (Duality))
• describe how dual simplex can be used in the case additional constraint leads to infeasibility (Section 4 (Sensitivity))
• write down general form and standard form of LP problems (Section 2 (Simplex Method))
• describe the motivation for using duality and formulate the dual problem given the primal (Section 3 (Duality))
• apply parametric programming to calculate the change of the objective value (and the optimal solutions) when more than one objective coefficient or the RHS are changed continuously (Section 4 (Sensitivity))
• apply these steps to the two examples in the handout (and similar problems) (Section 1 (Intro to MP))
• model either-or, set-up costs and other condition-based constraints using binary variables and constraints in the context of integer programming (Section 5 (Integer Programming))
• using duality and complementary slackness to verify optimality (Section 3 (Duality))
• describe economic interpretation of shadow price and perform sensitivity analysis on LP
• describe general branch and bound method (Section 5 (Integer Programming))
• describe branch and bound methods
• apply the dictionary and full tableau Simplex method to solve LP problems in standard form given a starting BFS (Section 2 (Simplex Method))
• describe complementary slackness conditions (Section 3 (Duality))
• derive (upper) bound on IP using LP relaxation (Section 5 (Integer Programming))
• obtain (lower) bound on IP using rounding (Section 5 (Integer Programming))
• solve LP problems with two variables using the graphical method (Section 1 (Intro to MP))
• derive the range of the objective coefficient until the optimal basis start changing and the corresponding range of the optimal value (Section 4 (Sensitivity))
• transform LP problems from general form to standard form and vice versa (Section 2 (Simplex Method))
• formulate the knapsack problem using IP (Section 5 (Integer Programming))
• apply branch and bound to solve simple IP (e.g. with no more than 3 variables) (Section 5 (Integer Programming))

Linear Programming.

• Model construction and modelling issues.
• Simplex method: two-phase algorithm, dual simplex method, network simplex method.
• Duality: motivation and definitions, duality theorem, complementary slackness, optimality
• testing.
• Sensitivity analysis: ranging for objective function coefficients and right hand-side constraints,
• economic interpretation and applications.
• Parametric programming. Integer Programming.
• Modelling techniques using zero-one variables.
• Branch and bound algorithm for integer programming.

Teaching and learning methods

Five 2-hour lectures

Two 1-hour class sessions

Two 2-hour computer sessions

Resources & Reading list

Textbooks

HP Williams. Model Building in Mathematical Programming. Wiley.

FS Hillier & GJ Lieberman. Introduction to Mathematical Programming. McGraw Hill.

V Chvatal. Linear Programming. Freeman.

HP Williams. Model Solving in Mathematical Programming. Wiley.

WL Winston. Operations Research: Applications and Algorithms. Duxbury.

Summative

This is how we’ll formally assess what you have learned in this module.

Referral

This is how we’ll assess you if you don’t meet the criteria to pass this module.

Repeat Information

Repeat type: Internal & External