Gams Modell 01 Introduction.pdf

8/10/2019 Gams Modell 01 Introduction.pdf

1/32

- 1 -

Technische Universitt BerlinFachgebiet Wirtschafts- und Infrastrukturpolitik

Methods for Network Engineering

Methods for etwork ngineering


2/32

- 2 -



Module 2: Introduction to GAMS


3/32


4/32

- 4 -



What is GAMS?

The most important features of GAMS are:

Capability to solve small scale to large scale problems with little code.Model and solver are independent. Problems can be solved by different solution methodsonly by changing the solver.Since GAMS has been built to resemble mathematical programming models, the translationfrom the mathematical model to GAMS is almost transparent.GAMS uses common English words, thus it is easy to understand the statements.


5/32- 5 -



Downloading GAMS

A free demo distribution is available at http://www.gams.com/

Without a license, the GAMS distribution has the following limitations:Model limits:

Up to 200 constraintsUp to 300 variablesUp to 2000 nonzero elements (1000 nonlinear)

Up to 30 discrete variablesSolver (global) limits:

Up to 10 constraintsUp to 10 variables

T h i h U i i B li
http://www.gams.com/http://www.gams.com/


6/32- 6 -



Excercise: Transportation Problem

In the classic transportation problem, we are given the supplies at several plants

and the demands at several markets for a single commodity, and we are giventhe unit costs of shipping the commodity from plants to markets. The economicquestion is: how much shipment should there be between each plant and eachmarket so as to minimize total transport cost? Shipping costs are 90 $ per caseper kmile.

Two supply plants (Seattle, San Diego)Three markets (New York, Chicago, Topeka)One commodity (i.e.: coffee)

Shipping Distances [kmiles]

Markets Supplies

New York Chicago Topeka

Plants Seattle 2.5 1.7 1.8 350

San Diego 2.5 1.8 1.4 600

Demand 325 300 275

Technische Universitt Berlin


7/32- 7 -



Excercise: Transportation Problem

Minimize: Total shipping cost

Subject to: Demand satisfaction and supply constraints

Seattle

San Diego

Topeka

New YorkChicago



8/32- 8 -



Algebraic Representation

Indices (or sets):

i = plants j = markets

Given Data (or parameters):a i = supply of commodity of plant i [in cases]b j = demand for commodity at market j [cases]

cij = shipping cost per unit between plant i and market j [1000 $ per case]Decision Variables:

xij = amount to ship from plant i to market j [cases], where x ij 0, for all i, j

Constraints:Observe supply limit at plant i: j xij a i , for all i [cases]

Satisfy demand at market j: i xij b j , for all j [cases]Objective Function:

Minimize i j cij xij [$K]



9/32- 9 -



Algebraic Representation

Grundlagen des Operations Research (OR 1):

Objectivefunction min z = 0.225 x 11 + 0.153 x 12 + 0.162 x 13 + 0.225 x 21 + 0.162 x 22 + 0.126 x 23SupplySeattle x11 + x12 + x13 350SupplySan Diego x21 + x22 + x23 600DemandNew York x11 + x21 325DemandChicago x12 + x22 300DemandTopeka x13 + x23 275Positivevariable xij 0



10/32- 10 -

Fachgebiet Wirtschafts- und Infrastrukturpolitik


The GAMS Model

A GAMS model is a collection of statements in the GAMS language.

An entity of the model cannot be referenced before it is declared to exist.Entity: Object (i.e.: set, list, table, scalar, parameter)All the entities of the model are identified (and grouped) by type

Terminate every statement with a semicolonThe GAMS compiler does not distinguish between upper- and lowercase letters.

Multiword names are not allowed New York, use hyphens New-YorkFormatting:

Multiple lines per statementEmbeded blank linesMultiple statements per line

DocumentationLines starting with an asterisk [*] are commentsWithin specific GAMS statements commentary is possible



11/32- 11 -



The GAMS Model

Solution

Solve Displays

ModelVariable

declarationsEquation

declarations and definitionsModel

definition

Data

Setdeclarations and definitions

Parameterdeclarations and definitions Value Assignments



12/32- 12 -



The GAMS Model (SETS)

Sets are used to declare indices and their possible values

Declare and name the setsAssign their members between slashes / /We can put sets into one group:

SETS

i canni ng pl ant s / SEATTLE, SAN- DI EGO /

j mar ket s / NEW- YORK, CHI CAGO, TOPEKA / ;or into separate statements:

SET i canni ng pl ant s / SEATTLE, SAN- DI EGO / ; SET j mar ket s / NEW- YORK, CHI CAGO, TOPEKA / ;

When elements follow a sequence use asterisk:SET t t i me per i ods / 1991*2000/ ; t = {1991,1992,1993, .....,2000}SET m machi nes / mach1*mach24/ ; m = { mach1, mach2,......mach24}

Other useful options:When needing two different elements from the same existing set: alias (i,j)Subgroups if needing only parts of an existing sets: SET sub_mach(m) / 1995*1999/

Technische Universitt BerlinF h bi Wi h f d I f k li ik


13/32

- 13 -



The GAMS Model (DATA)

GAMS uses three formats for entering data:

Scalars (Lists)Dimension 0A scalar statement has no domain (it is not defined in a set) and has only one value

SCALAR f f r ei ght i n dol l ar s per case per t housand mi l es / 90/ ;

It is a list with only one entryParameters (Lists)

Dimension 1Declare parameters and their domains a(i) and b(j)The standard value is zero

TablesDimension 2

Direct assignmentsEach assignment statement takes effect immediately and overrides any previousvalue.


14/32



15/32

- 15 -



The GAMS Model (TABLE)

Data can also be entered in convenient table form

Declares the parameter and domainAlign data in columns

TABLE d( i , j ) di st ance i n t housands of mi l esNew- Yor k Chi cago Topeka

Seat t l e 2. 5 1. 7 1. 8San- Di ego 2. 5 1. 8 1. 4 ;

Alternative:PARAMETER d( i , j ) di st ance i n t housands of mi l es/ Seat t l e. New- Yor k 2. 5

Seat t l e. Chi cago 1. 7

/ ;



16/32

- 16 -

Fachgebiet Wirtschafts und Infrastrukturpolitik


The GAMS Model (DIRECT)

Assignments: When data values are to be calculated, you first declare the

parameter then give its algebraic formulation. GAMS will automatically makethe calculations.PARAMETER c( i , j ) t r anspor t cost i n 1000s of dol l ar s per case ;c( i , j ) = f * d( i , j ) / 1000 ;

You can enclose the elements names in quotes:c( ' Seat t l e' , ' New- Yor k' ) = 0. 40 ;



17/32

- 17 -

g p


The GAMS Model (CONDITIONS)

$(condition) can be read as "such that condition is valid

If b is greater than 1.5, then assign value 2 to aa$( b>1. 5) =2 ;For dollar condition on the left-hand side, no assignment is made unless thelogical condition is satisfied.

c( i , j ) $( ord ( i ) =1) = f * d( i , j ) / 1000 ;c( i , j ) $( ord ( i ) = card ( i ) - 1) = f * d( i , j ) / 1000 ;

For dollar condition on the right hand side, an assignment is always made. If thelogical condition is not satisfied, the corresponding term that the logical dollarcondition is operating on evaluates to 0.if-then-else type of construct is implied

c( i , j ) = ( f * d( i , j ) / 1000) $( ord ( i ) = card ( i ) - 1) ;

To stop the compiler at a certain line$exi t or $st op



18/32

- 18 -Methods for Network Engineering

The GAMS Model (VARIABLES)

Decision variables are expressed algebraically, with their indices specified.

Variable types are: FREE, POSITIVE, NEGATIVE, BINARY, or INTEGER. The defaultis FREEThe objective variable (z, here) is to be declared without an index and should beFREE and SCALAR

VARIABLES

z t ot al t r anspor t at i on cost s i n 1000s of dol l ar s ;

Positive VARIABLES

x( i , j ) shi pment quant i t i es i n cases ;



19/32


The GAMS Model (EQUATIONS)

Objective function and constraint equations are first declared by giving them

names:EQUATIONScost def i ne obj ect i ve f unct i onsuppl y( i ) obser ve suppl y l i mi t at pl ant idemand( j ) sat i sf y demand at mar ket j ;

Then their general algebraic formulae are described.:cost . . z =e= sum ( ( i , j ) , c ( i , j ) *x( i , j ) ) ;suppl y( i ) . . sum ( j , x( i , j ) ) =l = a( i ) ;demand( j ) . . sum ( i , x( i , j ) ) =g= b( j ) ;

=e= indicates 'equal to'=l= indicates 'less than or equal to'

=g= indicates 'greater than or equal to'



20/32


The GAMS Model (MODEL)

The model is given a unique name (here, TRANSPORT), and the modelerspecifies which equations should be included in this particular formulation (inthis case we specified ALL)

MODEL t r anspor t / al l / ;

This would be equivalent to MODEL t r anspor t / cost , suppl y, demand / ;

This equation selection enables you to formulate different models within asingle GAMS input file, based on the same or different given data.



21/32


The GAMS Model (SOLVE)

The SOLVE statement consists of the following parts:Keyword SOLVEName of model to be solved t r anspor tKeyword usi ngOptimization procedure to be used (Linear Programming) l pKeyword (maximizing or) minimizing for the direction of the optimization mi ni mi zi ng name of variable to be optimized z

SOLVE t r anspor t usi ng l p mi ni mi zi ng z ;



22/32


The GAMS Model (BOUNDS)

For each value GAMS saves the following values in a database.lo = lower bound.up = upper bound.l = level or primal value.m = marginal or dual value

To shorten processing time you may consider giving GAMS some initial values.i.e.:

x. up( i , j ) = capaci t y( i , j ) ;x. l o( i , j ) = 10. 0 ;x. up( ' seat t l e' , ' new- yor k' ) = 1. 2*capaci t y( seat t l e' , ' new- yor k' ) ;



23/32


The GAMS Model (DISPLAY)

Each parameter and variable can be called using the display commandDISPLAY x. l , x. m, z. l



24/32


Overview: Parts of a GAMS Model

Command Purpose

SET Used to indicate the name of the indices

SCALAR Used to declare scalars

PARAMETER Used to declare vectors

TABLE Declare and assign the values of an array

VARIABLE Declare variables, assign type and bounds

EQUATION Function to be optimized and its constraints

MODEL Give a name to the model, and list the related constraints

SOLVE Indicate what solver to use

DISPLAY Indicate what you would like to display as output



25/32


Overview: Common Parameter Manipulations

Each parameter can be manipulated byMathematical standard operators

Exponentiation **Multiplication and Division * /Addition and Subtraction + -

FunctionsLogarithm (ln) LOG()

Index operatorsSummation: SUM(index of summation, summand)

SUM( j , x(i,j) ) equals j xij SUM( (i,j), x(i,j) ) equals i j xij

Product: PROD(index of product, factors)

Minimum: SMIN(values)Maximum: SMAX(values)



26/32


Solution Phases and Interpretation of the Output

Compilation Output Echo print Symbol reference map Symbol listing map Unique element listing map

Execution Output

Solution Output Equation listing Column listing Model statistics Solve summary Solver report Solution listing Report summary File summary

Compilation Error

Execution Error

Solution Error



27/32


The GAMS Model (SOLUTION)



28/32


Overview: GAMS Model Status

Model Status Description

1 OPTIMAL The solution is optimal (LP, RMIP)

2 LOCALLY OPTIMAL Local optimum has been found

3 UNBOUNDED The solution is unbounded

4 INFEASIBLE The linear problem is infeasible

5 LOCALLY INFEASIBLE No feasible point could be found for the nonlinear problem

6 INTERMEDIATE INFEASIBLE Current solution not feasible, solver stopped

7 INTERMEDIATE NONOPT. Incomplete solution, appears to be feasible

8 INTEGER SOLUTION Integer solution has been found to a MIP

9 INTERMEDIATE NON-INT. Incomplete solution to a MIP

10 INTEGER INFEASIBLE There is no integer solution to a MIP

ERROR UNKNOWNERROR NO SOLUTION

Terminated without known model status



29/32


Overview: GAMS Solver Status

Solver Status Description

1 NORMAL COMPLETION Solver terminated in a normal way, model status describes the solution

2 ITERATION INTERRUPT Solver was interrupted because it used to many iterations (ITERLIM)

3 RESOURCE INTERRUPT Solver was interrupted because it used to much time (RESLIM)

4 TERMINATED BY SOLVER Solver encountered difficulty and was unable to continue

5 EVALUATION ERROR LIMIT Too many evalutation of nonlinear terms at undefined values

UNKNOWN ERROR Termination error unknown



30/32


Appendix A

English Terms



31/32


Overview: English Terms 1

English German

set Menge (geometrischer Raum)

subset Teilmenge

inequality Ungleichung

feasible set Lsungsraum

objective function Zielfunktion

constrained optimization Optimierung unter Nebenbedingungenunconstrained optimization Optimierung ohne Nebenbedingung

(partial) derivative (partielle) Ableitung

differentiable differenzierbar

continuously differentiable stetig differenzierbar

root Nullstelleroot finding problem Nullstellenproblem



32/32


Overview: English Terms 2

English German

first order condition (FOC) Bedingung erster Ordnung

complementarity model Komplementarittsmodell

(mixed) integer problem (gemischt-)ganzzahliges Problem

quantity Menge (Volumen)

equilibrium Gleichgewicht

spatial equilibrium rumliches Gleichgewichttraffic equilibrium Verkehrsgleichgewicht

multiplier Multiplikator

edge Kante (eines Graphen)

arc Kante, Verbindung (eines Graphen)

node Knoten (u.a. eines Graphen)vertex Knoten (eines Graphen)

Documents

Gams Modell 01 Introduction.pdf