Introduction to Linear Programming and Integer Linear Programming Helena Ramalhinho Louren o Introduction Outline brief introduction to Modeling Combinatorial Optimization Linear Programming Excel solver Integer Linear Programming Solution Methods for LP and ILP AMPL LP ILP introduction 1 LP ILP introduction 2 Helena Ramalhinho Louren o 2022 1 Decisions in complex situations Too many alternatives Too many constraints A very complex environment Very fast changes Nee to make a very fast decision time How to evaluate the different alternatives How to choose the best decision LP ILP introduction 3 Real Problem The modeling process Data Analysis Optimization Model Results Interpretation Set of Models Solution Methods r e k a m n o i s i c e D Simulation Solution Analysis Scenarios Make a decision Operations Research provides many methods and techniques to analyze the consequences of decisions before their introduction to reality LP ILP introduction 4 Helena Ramalhinho Louren o 2022 2 Linear Programming Linear programming LP is a widely used mathematical modeling technique designed to help managers in planning and decision making relative to resource allocation Integer Linear Programming ILP An integer programming model is one where one or more of the decision variables has to take on an integer or binary values in the final solution LP ILP introduction 5 Combinatorial Optimization Combinatorial Optimization problem Given a set of elements E 1 2 n Set of feasible solutions F Each element of F is a subset of E Objective function f x F R In the minimization version the problem consists in Finding x F such that f x f x x F Discrete Optimization Graph models LP ILP introduction 6 Helena Ramalhinho Louren o 2022 3 Combinatorial Optimization Problems Traveling Salesman Problem TSP Routing problems Vehicle Routing Problem VRP Heterogeneous Vehicle Routing Problem HVRP Location problems Scheduling Problems Job shop scheduling problem Parallel machines Other Clique problems LP ILP introduction 7 Traveling Salesman Problem Traveling Salesman Problem Given a number of cities and the costs distances of traveling from any city to any other city What is the least cost round trip route that visits each city exactly once and then returns to the starting city 12 10 5 5 6 8 10 18 14 LP ILP introduction 8 Helena Ramalhinho Louren o 2022 4 Facility Location Models Where to locate the facilities Warehouses Schools Hospitals Etc How to meet customer demands from the facilities Which facility facilities serves each customer How much demand is met from each facility Costs Transportation warehousing customer service LP ILP introduction 9 Facility Location Models Facility Location Models p Median ILP Model Covering problems Maximal covering location problem Capacitated Facility Location Single source capacitated facility location And many more LP ILP introduction 10 2 Helena Ramalhinho Louren o 2022 5 Vehicle Routing A large part of many logistics systems involves the management of a fleet of vehicles used to serve warehouses retailers customers General class of vehicle routing problems Can be applied to other areas too Humanitarium Logistics Retailing and Logistics E commerce Flow routing in telecommunications LP ILP introduction 11 Vehicle Routing A set of customers at known geographical locations has to be supplied by a fleet of vehicles from a single depot Each customer has a specific demand Each route starts and finish at the depot The objective is to find the set of routes whose total length or cost is minimal Warehouse LP ILP introduction 12 Helena Ramalhinho Louren o 2022 6 Scheduling Resources Tasks Allocation of limited resources to the processing of tasks Machines crews vehicles planes buses personal Jobs flights distribution operations projects with the objective of Minimize completion time cost etc Important role in most manufacturing logistics and service industries Strategic and operations decisions LP ILP introduction 13 OR Methodology Identify a problem Get to know the problem context get Data Build a Model Mathematical Model Obtain a solution to the model Algorithm Understand the solution the real context Take the decision LP ILP introduction 14 Helena Ramalhinho Louren o 2022 7 OR Methodology Identify the problem Describe in detail the problem and identify all the components Identify the qualitative and quantitative aspects of the problem Get to know the problem context Identify the relationships of the problem with the context of the organization Obtain the relevant data Verify the data LP ILP introduction 15 OR Methodology Build a model A Model is an abstract representation of a real world system Simplification is the very essence of Modeling Which components should be included in the model Types of models Linear programming Integer Linear Programming Combinatorial Optimization Networks Non linear Simulation Etc LP ILP introduction 16 Helena Ramalhinho Louren o 2022 8 OR Methodology Obtain a solution to the model Which are the adequate solution methods to be applied to the model Algorithms Exact Methods Heuristics and Metaheuristics Which is the best software to be applied Commercial software Algorithm design and code LP ILP introduction 17 OR Methodology Understand the solution the real context Does the solution obtain makes sense in the real life Did we have considered all relevant components Take the decision Evaluate the impact of the solution Evaluate the decision process model method Review frequently the impact of the decision LP ILP introduction 18 Helena Ramalhinho Louren o 2022 9 Linear Programming Linear programming LP is a widely used mathematical modeling technique designed to help managers in planning and decision making relative to resource allocation LP ILP introduction 19 Linear Programming The Linear Programming Models have 4 properties in common All problems seek to maximize or minimize some quantity the objective function Restrictions or constraints that limit the degree to which we can pursue our objective are present There must be alternative courses of action from which to choose The objective and constraints in problems must be expressed in terms of linear equations or inequalities LP ILP introduction 20 Helena Ramalhinho Louren o 2022 10 Linear Programming Formulating a linear program involves developing a mathematical model to represent the managerial problem The steps in formulating a linear program are Completely understand the managerial problem being faced