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

This leads to integer programming

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

    or if buying one meant we must buy another

    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