DOC

# ch18 Handling Indivisibilities.doc - Department of Agricultural ...

By Maria Mason,2014-11-18 09:17
11 views 0
ch18 Handling Indivisibilities.doc - Department of Agricultural ...

Handling Indivisibilities

Bruce A. McCarl

Specialist in Applied Optimization

Regents Professor of Agricultural Economics,

Texas A&M University

Principal, McCarl and Associates

mccarl@tamu.edu

bruceamccarl@cox-internet.com

agecon.tamu.edu/faculty/mccarl

979-693-5694

979-845-1706

?B.A. McCarl March 2003 Handling Indivisibilities (indivis) page 1

Handling Indivisibilities

All or None -- Integer Programming

Many investment and other business problems involve cases where one has to take all or none of an item.

We cannot build ? of a plant or buy 3/4 of a machine. We must buy or build 1 or 2 or 3 or none but not a fractional part

maxCWCXCY123

s.t.AWAXAYb123

W0

X0andinteger

Yequals0or1

Here W is a normal,continuous LP variable,

X is an integer variable,

Y is a zero one variable

When problems have

only X they are called pure integer

only Y they are called pure zero one

W and X they are called mixed integer

other variants exist

?B.A. McCarl March 2003 Handling Indivisibilities (indivis) page 2

Handling Indivisibilities

Logical Conditions -- Integer Programming

Integer programming also allows many powerful logical conditions to be imposed

Consider the following: Suppose I am running a bottling plant that runs white milk but sometimes chocolate

If any chocolate is run I need to clean at cost of F. Let X then be the amount of chocolate milk processed

Then we add a component to the model as follows

maxCXFY

s.t.XMY0

X0

Yequals0or1

Note in this component M is a big number (10 billion) and for X>0 this implies Y=1 while if F>0 Y=0 if X=0.

So if we run any chocolate milk we clean whether it be 1 gallon or one million

Y is an indicator variable.

?B.A. McCarl March 2003 Handling Indivisibilities (indivis) page 3

Handling Indivisibilities

Integer Programming

Similarly suppose we can buy from k different types of machines and get from them capacity for the ith time period

maxCXFY~~mmkk

mk

s.t.aXCAPY0foralli~~immikk

mk

X0forallmm

Yequals0or1forallmk

In this case if they were mutually exclusive we could also add

Y1~k

k

Y -Y=0 12

or if a mutually exclusive machine can only be purchased if we have a minimum volume being used

aXLLY0foralli~~immikk

mk

?B.A. McCarl March 2003 Handling Indivisibilities (indivis) page 4

Handling Indivisibilities

Integer Programming in GAMS

Maximize 7X -3X -10X 123

X -2X ; 0 12

X -20X ; 0 13

X 0 X 0 integer X0,1 123

GAMS Input for Example Integer Program (basint.gms)

POSITIVE VARIABLE X1

INTEGER VARIABLE X2

BINARY VARIABLE X3

VARIABLE OBJ

EQUATIONS OBJF

X1X2

X1X3;

OBJF.. 7*X1-3*X2-10*X3 =E= OBJ;

X1X2.. X1-2*X2 =L=0;

X1X3.. X1-20*X3 =L=0;

option optcr=0.01;

MODEL IPTEST /ALL/;

SOLVE IPTEST USING MIP MAXIMIZING OBJ;

Differences

1. Must tell type of integer variable

2. Should set optcr or optca (problems occur if this is

not done because the default values are very large)

3. Use MIP solve need OSL, CPLEX or XPress not

ZOOM

?B.A. McCarl March 2003 Handling Indivisibilities (indivis) page 5

Handling Indivisibilities

Integer Programming Solution Difficulty

All sounds good but problems are hard. Let’s explore why

Calculus is basis of all continuous optimization but not here because there is no neighborhood around a point in which a derivative can be defined

2X3X1612

3X2X1612

X,X0&integer12

Feasible Region for X,Y nonnegative integers

Figure 15.1 Graph of Feasible Integer Points for First LP Problem

10

8

6

Y-Axis

4

2

0

0246810

X-Axis

?B.A. McCarl March 2003 Handling Indivisibilities (indivis) page 6

Handling Indivisibilities

Integer Programming Solution Difficulty

Figure 15.1 Graph of Feasible Integer Points for First LP Problem

10

8

6

Y-Axis

4

2

0

0246810

X-Axis

Note

1. Solutions are finite

2. A line between 2 feasible points does not contain

all feasible points

3. Moving between points is not always easy 4. Points are on boundary, interior and not in

general at corners

5. Rounding of LP point may not be bad

?B.A. McCarl March 2003 Handling Indivisibilities (indivis) page 7

Handling Indivisibilities

Integer Programming Solution Difficulty

Consider

X7X2312

X10X54 12

X,X0&integer12

Figure 15.2 Graph of Feasible Integer Points for Second Integer Problem

10

8

6

X2

4

2

0

1028046

X1

Here

Rounding not good

Movement between points hard ?B.A. McCarl March 2003 Handling Indivisibilities (indivis) page 8

Handling Indivisibilities

Integer Programming Solution Difficulty

Mixed Integer Programming Feasible Region X1 integer,

X2 continuous

3X2X1612

2X3X1612

X0&integer1

,X02

Figure 15.3 Mixed Integer Feasible Region

10

8

6

X1

4

2

0

0246810

X2

?B.A. McCarl March 2003 Handling Indivisibilities (indivis) page 9

Handling Indivisibilities

Integer Programming Solution Rounding

Solving the problem (solintr.gms)

Max1.4XX12

s.t.2X3X1612

3X2X1612

X,X0&integer12

as an LP yields X1=X2=3.2 which can be rounded to X1=X2=3 , Obj=7.2

But this may not always be feasible or optimal

In this case an objective of 7.6 arises at X1=4,X2=2 (solint.gms)

Rounding only works well if variable values are large

?B.A. McCarl March 2003 Handling Indivisibilities (indivis) page 10

Report this document

For any questions or suggestions please email
cust-service@docsford.com