• Author / Uploaded
• Christopher Suarez

Citation preview

CHAPTER 2. OPTIMIZATION MODELS

The art of modeling

Dali in his studio in Portlligat http://www.ernst-scheidegger-archiv.org/en/home/

Best way to learn...practice Profile of time http://www.elle.com

Building a model: five steps 1. Identify the data and dimensions of the model Data is given to us and it cannot be modified by our decisions Can be obtained by observation (ex. Waiting times)

2. Identify and describe the decision variables of the model Variables are used to represent all decisions that must be made as well as their components and consequences They are the answers to the decision maker questions (ex. How much to produce of an specific product)

3. Identify special restrictions on variables For example: variables can be integer, can have a lower bound or upper bound They are specific for every variable

Building a model: five steps 4. Express the constraints of the model Constraints are all restrictions that relate variables between themselves and with data They are the equations of the model If not possible, introduce new variables (Go to 2)

5. Formulate the objective of the model The objective is the criterion by which the quality of solutions is assessed (profit, cost, reliability, ...) Typically we want to maximize (ex. profit) or minimize (ex. cost) If not possible, introduce new variables (Go to 2)

Model 1. Farmer Jones Problem Farmer Jones must determine how many acres of corn and wheat to plant this year. An acre of wheat yields 25 bags of wheat and requires 10 hours of labor per week. An acre of corn yields 10 bags of corn and requires 4 hours of labor per week. All wheat can be sold at $4 a bag and all corn can be sold at $3 a bag. Seven acres of land and 40 hours per week of labor are available. Government regulations require that at least 30 bags of corn be produced during the current year. How can Farmer Jones maximize his total revenue?

Modelo 1. Granjero Jones problema Farmer Jones debe determinar el número de acres de maíz y trigo para sembrar este año. Un acre de trigo produce 25 sacos de trigo y requiere 10 horas de trabajo por semana. Un acre de maíz produce 10 sacos de maíz y requiere 4 horas de trabajo por semana. Todo el trigo se puede vender en $ 4 una bolsa y todo el maíz se puede vender en $ 3 una bolsa. Siete acres de tierra y 40 horas semanales de trabajo están disponibles. Las regulaciones gubernamentales requieren que se produjeron al menos 30 bolsas de maíz durante el año en curso. ¿Cómo puede granjero Jones maximizar su ingreso total?

Model 1. Farmer Jones Problem Data: Types of crops harvested: wheat (w), corn (c) Yields for crops: 25bsh/acre (w), 10bsh/acre (c) Labor requirement for crops: 10h/acre (w), 4h/acre (c) Selling price for crops: 4$/bag(w);3$/bag (c) Total acreage available: 7 acres Total labor available: 40 hours Minimum production requirement: 30bag (c) Don’t forget to always specify the units

Model 1. Farmer Jones Problem Variables: Number of acres of corn to be planted: 𝑥𝑐 , (acres)

Number of bags of corn to be produced: 𝑦𝑐 , (bags)

Number of acres of wheat to be planted: 𝑥𝑤 , (in acres)

Number of bags of wheat to be produced: 𝑦𝑤 , (bags)

Individual restrictions on variables The individual restrictions on the variables (IVRs) are all the constraints and specifications that are pertinent to a single variable. They are typically of three types: Sign restrictions

Type restrictions:

𝑥 is nonnegative,

𝑥 ∈ ℕ,

𝑥 is nonpositive,

𝑦 ∈ 0,1 (binary),

𝑥 is unrestricted in sign (urs)

𝑧 ∈ ℝ (continuous)

Bound restrictions 𝑥 ≥ 5, 𝑦 ≤ 25, 0 ≤ 𝑥 ≤ 100

𝑧 ∈ −3, −1 ∪ 1.3 (semicontinuos)

Model 1. Farmer Jones Problem IVRs: The variables are nonnegative: 𝑥𝑐 ≥ 0, 𝑥𝑤 ≥ 0, 𝑦𝑐 ≥ 0, 𝑦𝑤 ≥ 0

The variables are continuous: 𝑥𝑐 ∈ ℝ, 𝑦𝑐 ∈ ℝ, 𝑥𝑤 ∈ ℝ, 𝑦𝑤 ∈ ℝ,

A minimum production of corn is required: 𝑦𝑐 ≥ 30

Model 1. Farmer Jones Problem Constraints: Relationship between the acres of wheat planted and the number of bags of wheat harvested: 𝑦𝑤 = 25𝑥𝑤

Relationship between the acres of corn planted and the number of bags of corn harvested: 𝑦𝑐 = 10𝑥𝑐

Limit in the acres available: 𝑥𝑤 + 𝑥𝑐 ≤ 7

Limit in the labor available: 4𝑥𝑤 + 10𝑥𝑐 ≤40

Minimum corn production request by Government (already included in IVRs): 𝑦𝑐 ≥ 30

Model 1. Farmer Jones Problem Objective: Our goal is to maximize revenue. The revenue has two components: Revenue due to corn: 3𝑦𝑐

Revenue due to wheat: 4𝑦𝑤

Total revenue: 3𝑦𝑐 + 4𝑦𝑤

The objective is: 𝑀𝑎𝑥 3𝑦𝑐 + 4𝑦𝑤

Model 1. Farmer Jones Problem Mathematical formulation: 𝑀𝑎𝑥 3𝑦𝑐 + 4𝑦𝑤 Objective function s.t. Subject to 𝑦𝑤 = 25𝑥𝑤

IVR (sign restr.)

𝑦𝑐 = 10𝑥𝑐 𝑥𝑤 + 𝑥𝑐 ≤ 7 4𝑥𝑤 + 10𝑥𝑐 ≤40 𝑦𝑐 ≥ 30 𝑥𝑐 , 𝑥𝑤 , 𝑦𝑤 ≥ 0

IVR (type restr.)

𝑥𝑐 , 𝑥𝑤 , 𝑦𝑐 , 𝑦𝑤 ∈ ℝ

Constraints

IVR (lower bound)

Can we make it better?? (Hint: substitute variables)

Model 1. Farmer Jones Problem Mathematical formulation: 𝑀𝑎𝑥 30𝑥𝑐 + 100𝑥𝑤 s.t. 𝑥𝑤 + 𝑥𝑐 ≤ 7 4𝑥𝑤 + 10𝑥𝑐 ≤40 𝑥𝑐 ≥ 3 𝑥𝑐 , 𝑥𝑤 ≥ 0 𝑥𝑐 , 𝑥𝑤 ∈ ℝ

Model 1. Farmer Jones Problem Mathematical formulation: 𝑀𝑎𝑥 30𝑥𝑐 + 100𝑥𝑤 s.t.

Data Variables Objective function

Constraints IVR

𝑥𝑤 + 𝑥𝑐 ≤ 7 10𝑥𝑤 + 4𝑥𝑐 ≤40 𝑥𝑐 ≥ 3 𝑥𝑐 , 𝑥𝑤 ≥ 0 𝑥𝑐 , 𝑥𝑤 ∈ ℝ

Model 1. Farmer Jones Problem Resource allocation problem Linear program (objective function and constraints are linear in the variables) Later we will see more types of problems

There are different formulations for the same problem (some better than others) Better in what sense?

Algebraic modeling languages To solve practical problems, we use optimization solvers: Solvers are implementation of solution algorithms. The more general the algorithms, the slower they typically produce solutions. Some problems are very challenging to solve. Solvers have (sometimes complicated) input formats.

To simplify the creation of input files for optimization solvers, algebraic modeling languages are used : Algebraic modelers convert problems into solver inputs. Algebraic modelers help debug models. Algebraic modelers call appropriate solvers. There are many commercial algebraic modelers, including GAMS, AMPL, XPRESS-IVE, ...

GAMS GAMS is a commercial software (algebraic modeling language) that transforms models written in natural form into standard computer inputs GAMS provides access to a variety of solvers A demo version is available at: http://www.gams.com/download You can install it for free on your computer (available for several OS).

There are good comprehensive manuals on GAMS website http://www.gams.com There are many GAMS examples available Sidweb, within GAMS.

Learning GAMS Demo models: GAMS models library

Learning GAMS A GAMS Tutorial, by Richard E. Rosenthal You can find it on the help menu

Solving problems with GAMS We are using a Demo version, that solves small problems For larger problems we can use NEOS (free web server) http://www.neos-server.org/neos/ You need to input your GAMS code and select the solver

1. Declare sets and parameters Put data between // 2. Variables and IVRs (positive, negative, binary, integer or free)

3. Declare constraints (and objective function)

4. Define constraints (and objective function)

5. Define model through its components model farmer_jones_mdl /all/

6. Specify model type and objective lp, mip, nlp, minlp… Minimizing, maximizing

7. Display results Use “.l”

Choosing solvers

Choosing solvers In our example we use CPLEX You can use different solvers for different types of problems Linear Programming: CPLEX, XPRESS, COINIPOPT, . . . Mixed Integer Programming: CPLEX, XPRESS, . . . Mixed Integer Quadratic Programs: CPLEX, . . . Nonlinear Programming (local): CONOPT, MINOS, SNOPT, . . . Nonlinear Programming (global): BARON, LINDOGLOBAL, . . . Nonlinear Mixed Integer Programming: BARON, LINDOGLOBAL, COINBONMIN, . . .

Instead of using the command “option lp=cplex;" inside of your GAMS code, you can set your default choice of solvers.

GAMS solution

Model 2. Feed Mix Problem An agricultural mill produces animal feed mix by combining limestone, corn and soybean meal. The price (in cents) per kg of limestone, corn and soybean are 10, 30.5 and 90 respectively. The final product must contain: At least 0.8% of calcium No more than 1.2% of calcium At least 22% of protein At most 5% of fiber The nutrient contents of the ingredients are as follows: 1kg of limestone contains 0.38kg of calcium, negligible amounts of protein and fiber. 1kg of corn contains 0.001kg of calcium, 0.09kg of protein and 0.02kg of fiber 1kg of soybean meal contains 0.002kg of Calcium, 0.5kg of protein and 0.08kg of fiber. Find the composition of the feed mix that satisfies these conditions and minimize the cost

Model 2. Feed Mix Problem Un Agricultor produce la mezcla de alimentación mediante la combinación de piedra caliza, maíz y harina de soja. El precio (en centavos de dólar) por kg de piedra caliza, el maíz y la soja son 10, 30.5 y 90, respectivamente. El producto final debe contener: Al menos 0,8% de calcio No más de 1,2% de calcio Al menos 22% de la proteína A lo sumo 5% de fibra El contenido de nutrientes de los ingredientes son los siguientes: 1 kg de piedra caliza contiene 0.38kg de calcio, cantidades insignificantes de proteína y fibra. 1 kg de maíz contiene 0.001kg de calcio, 0,09 kg de proteína y 0,02 kg de fibra 1 kg de harina de soja contiene 0.002kg de calcio, 0,5 kg de proteína y 0,08 kg de fibra. Encuentra la composición de la mezcla de alimentación que satisface estas condiciones y minimizar el coste

Model 2. Feed Mix Problem Mathematical formulation: 𝑀𝑖𝑛 10𝑥𝑙 + 30.5𝑥𝑐 + 90𝑥𝑠 s.t. 𝑥𝑙 + 𝑥𝑐 + 𝑥𝑠 = 1 0.38𝑥𝑙 + 0.001𝑥𝑐 + 0.002𝑥𝑠 ≥ 0.008 0.09𝑥𝑐 + 0.05𝑥𝑠 ≥ 0.22 0.02𝑥𝑐 + 0.08𝑥𝑠 ≥ 0 0.38𝑥𝑙 + 0.001𝑥𝑐 + 0.002𝑥𝑠 ≤ 0.012 0.09𝑥𝑐 + 0.05𝑥𝑠 ≤ 1

0.02𝑥𝑐 + 0.08𝑥𝑠 ≤ 0.05 xl

≤1 xc

≤1 xs

xl , xc , xs ≥ 0 xl , xc , xs ∈ ℝ

≤1

Model 2. Feed Mix Problem Blending problems What can you say about the objective function and constraints in relation to the variables? Linear functions

The Feed Mix problem is a linear problem (LP)

GAMS Model for Feed Mix Problem

GAMS Model for Feed Mix Problem

GAMS Results for Feed Mix Problem

Model 3. Box design problem We wish to design a rectangular box of dimension 𝑙 𝑥 𝑤 𝑥 ℎ with volume at least 300 cm3 whose total surface area is minimal.

Let’s work on the board…

Model 3. Box design problem Deseamos diseñar una caja rectangular de dimensión 𝑙 𝑥 𝑤 ℎ 𝑥 con un volumen de al menos 300 cm3 cuya superficie total es mínima.

Vamos a trabajar en el tablero ...

Model 3. Box design problem Mathematical formulation: 𝑀𝑖𝑛 2(𝑦𝑙 𝑦ℎ + 𝑦𝑙 𝑦𝑤 + 𝑦𝑤 𝑦ℎ ) s.t. 𝑦𝑙 ∗ 𝑦𝑤 ∗ 𝑦ℎ ≥ 300

yl , 𝑦w , 𝑦ℎ ≥ 0 yl , 𝑦w , 𝑦ℎ ∈ ℝ

Model 3. Box design problem Are the objective and constraints linear in the variables? This is a Nonlinear Problem (NLP)

GAMS model for Box design problem

GAMS model for Box design problem

GAMS results for Box design problem

Model 4. Job Machine Assignment problem A production facility has three machines (A,B,C) that have 35h, 20h and 26h of remaining processing time available over the next week. Using this capacity, the facility has to decide which of 6 jobs to produce. The amount of processing time needed by the jobs are 10h, 13h, 8h, 6h, 15h and 22h respectively. Further the revenue associated with producing a certain job on a certain machine is given in the following table: 1

2

3

4

5

6

A

8

7

5

6

8

10

B

7

8

4

3

7

9

C

10

6

6

3

6

10

Additionally, Job1 and Job3 cannot be performed on the same machine (because the change-over time is too large). The list of jobs assigned to Machine B must contain at least Job 5 or Job 6. Machine C is not assigned more than 2 jobs. The factory's goal is to select the allocation of jobs to machine that maximizes revenue while respecting available processing capacities.

Model 4. Job Machine Assignment problem Una planta de producción cuenta con tres máquinas (A, B, C) que tienen 35h, 20h y 26h de tiempo de procesamiento disponible durante la próxima semana restante. El uso de esta capacidad, la planta tiene que decidir cuál de 6 puestos de trabajo para producir. La cantidad de tiempo de procesamiento necesario por los puestos de trabajo son 10h, 13h, 8h, 6h, 15h y 22h respectivamente. Además los ingresos asociados con la producción de un determinado puesto de trabajo en una determinada máquina se da en la siguiente tabla: 1

2

3

4

5

6

A

8

7

5

6

8

10

B

7

8

4

3

7

9

C

10

6

6

3

6

10

Además, Puesto de Trabajo1 y Puesto de Trabajo 3 no se pueden realizar en la misma máquina (porque el tiempo de cambio de formato es demasiado grande). La lista de los puestos de trabajo asignados a la máquina B debe contener al menos 5 o 6 Puesto de Trabajo. Máquina C no se asigna más de 2 puestos de trabajo. El objetivo de la fábrica es para seleccionar la asignación de los puestos de trabajo de la máquina que maximiza los ingresos respetando al mismo tiempo las capacidades de procesamiento disponibles.

How to assign jobs to every machine?

Machines

Jobs

How to assign jobs to every machine?

Machines

Jobs

Model 4. Job Machine Assignment problem Mathematical formulation: 𝑀𝑎𝑥

6 j=1

3 m=1 rjm xjm

s.t. 3 m=1 xjm ≤ 1 ∀j 6 j=1 pj xjm ≤ PAm

= 1,2,…,6 ∀m = 1,2,3

x1m + x3m ≤ 1 ∀m = 1,2,3 x52 + x62 ≥ 1 6 j=1 xj3

≤2

xjm ∈ 0,1

∀j = 1,2,…,6 ∀m = 1,2,3

Model 4. Job Machine Assignment problem This is an assignment problem We use indexing or subscripts to represent a collection of similar quantities with a single symbol We use only binary variables This is an Integer Programming model (IP) What is the difference between binary variables and discrete variables?. Give examples Now, we will learn how to use “sets” in GAMS

GAMS model for Job Machine Assignment problem

GAMS model for Job Machine Assignment problem

GAMS results for Job Machine Assignment problem

Model 5. Production-Delivery Problem Fordco produces cars in Detroit and Dallas. The Detroit plant can produce up to 6,500 cars. Producing a car costs $2,000 in Detroit. The Dallas plant can produce up to 6,000 cars. Producing a car costs $1,800 in Dallas. Cars must be shipped to three cities: New Orleans (NO), Chicago (C) and New York (NY). Car demands are 2,000 at (NO), 4,000 at (C) and 3,000 at (NY). The cost of shipping a car is presented in the following table: From/To

NO

C

NY

Detroit

$800

$600

$300

Dallas

$500

$200

$200

At most 2,700 cars can be shipped from a given plant to a given city. Fordco wishes to minimize the cost of meeting demand.

Model 5. Production-Delivery Problem Fordco produce automóviles en Detroit y Dallas. La planta de Detroit puede producir hasta 6.500 coches. La producción de un coche cuesta $ 2,000 en Detroit. La planta de Dallas puede producir hasta 6.000 coches. La producción de un coche cuesta $ 1.800 en Dallas. Los vehículos deben ser enviados a tres ciudades: Nueva Orleans (NO), Chicago (C) y Nueva York (NY). demandas de coches son 2.000 al (NO), 4.000 en (C) y 3.000 al (NY). El costo de envío de un automóvil se presenta en la siguiente tabla: From/To

NO

C

NY

Detroit

$800

$600

$300

Dallas

$500

$200

$200

A lo sumo 2.700 coches pueden ser enviados desde un centro dado a una ciudad determinada. Fordco desea minimizar el costo de satisfacer la demanda.

Model 5. Production-Delivery Problem Mathematical formulation 𝑀𝑖𝑛

2 𝑝=1

3 𝑐=1 𝑥𝑝𝑐

𝑠𝑐𝑝𝑐 + 𝑐𝑝

s.t. 3 𝑐=1 𝑥𝑝𝑐 2 𝑐=1 𝑥𝑝𝑐

≤ 𝑘𝑝 ∀𝑝 = 1,2 ≤ 𝑑𝑐 ∀𝑐 = 1,2,3

𝑥𝑝𝑐 ≤ 2,700 ∀𝑝 = 1,2 ∀𝑐 = 1,2,3 𝑥𝑝𝑐 ∈ ℤ+ ∀𝑝 = 1,2 ∀𝑐 = 1,2,3

Model 5. Production-Delivery Problem This is a transportation model The variables are integer (IP) Later we will see that we can solve it as a LP Transportation problems are considered to be network problems Network problems: optimization problems define on networks

Model 5. Production-Delivery Problem Road or connections (edges) Cities (nodes)

GAMS model for Production-Delivery Problem

GAMS model for Production-Delivery Problem

GAMS results for Production-Delivery Problem