Discrete Optimization in Flexible Manufacturing Systems Laboratory

Discrete optimization
in Flexible Manufacturing Systems

Laboratory
Contents:
1. Lingo commands
2. Lingo examples
3. Simple discrete optimization examples
4. FMS loading and routing example
LINGO Page 1
1 Lingo commands
1.1 Constraint translation

∑v
i∈W
ij ≥dj ∀j ∈ C
∀j ∈ C ∑
i∈W
v ij ≥dj
@FOR( C ( j): @SUM( W ( i): v( i, j) ) >= d( j) );
1.2 Statements
♦ Each statement must terminated by a semicolon.
♦ Each statement specifies a condition that the variables must satisfy
rather than a computational rule for computing a variable.
♦ Lingo disregards case, y and Y for example is the same variable.
♦ Comments start with „!” and finish with semicolon „;”.
♦ Statement names, e.g. @FOR( Days(d):[Overtime] Hours(d) < 12 );
[Total cost objective] MIN = @SUM( Days: Hours*HourCost)
1.3 Sets
♦ Primitive sets: set_name /domain/ [: variables];
♦ Domain definition by explicit list is used when set elements are called by name in model
description, e.g.
SETS:
Days / Mo, Tu, We, Th, Fr, Sa, Su/ : Hours;
ENDSETS
Hours(Mo) > Hours(Tu) + Hours(We)
♦ Domain definition by range is for large vectors, e.g. /1..10/.
♦ Derived sets are used for multi-dimensional vectors, e.g. matrices
set_name (list_of_parent_sets) [: variables];
♦ Sparse (not dense) sets are used to exclude some elements of derived sets:
set_name (list_of_parent_sets) | /explicit list/ [:
variables]; or
set_name (list_of_parent_sets) | condition [: variables]; e.g.
SETS:
Operations /1..5/;
Sequence (Operations, Operations) | ( 1,2 2,3 3,4 3,5 4,5 );
AllPairs (Operations, Operations) | &1 #GT# &2;
ENDSETS
3
1 2 5
4
Page 2 LINGO
♦ @SIZE( <set> ) size of a set.

♦ @IN( <set>, <element> ) if element belongs to set returns 1.
1.4 Variables
♦ Continuous, non-negative.
♦ @BIN() command declares variables as binary.
♦ @GIN() command declares variables as integer and positive.
♦ @FREE() command declares variables as binary negative or positive.
♦ @BND() command declares lover and upper bound for a variable, e.g. @BND(-5,x,5).
1.5 Conditional expressions

♦ Operators: #NOT#, #AND#, #OR#, = #EQ#, ≠ #NE#, > #GT#, < #LE#, ≥ #GE#, ≤
#LT#.
♦ Conditional sets — sets with a membership filter:
set_name /domain/ | <conditional_expression> [: variables];
♦ Conditional statements:
@FOR( <set> | <conditional_expression> : <expression> );
e.g. @FOR( Days(D) | D #NE# Fr : Hours(D) < 8);
1.6 Data files

♦ @File( <file_path or file_name>); reads everything up to next “~” sign
or up to end of file.
♦ For subsequent @File commands Lingo reads from the point where it left off.
♦ Nesting is not allowed.
1.7Other functions
♦ @MIN(), @MAX(), @ABS(), @EXP(), @LOG(), @SIN(), @COS(),
@TAN()...
LINGO Page 3
2 Lingo examples
2.1 PC Mix
MODEL:
! Total profit for the week;
MAX = 200 * WS + 300 * NC;
! The total number of Wordsmiths produced is limited

by the supply of graphics chips;
WS <= 60;
! The total number of Numbercrunchers produced is

limited by the supply of math coprocessors;
NC <= 40;
! The total amount of memory used in all machines

manufactured for the week can't exceed 120 Mb;
WS + 2 * NC <= 120;
END
2.2 Transportation Problem
model:
! A 3 Warehouse, 4 Customer Transportation Problem;

SETS:
WAREHOUSE / WH1, WH2, WH3/ : CAPACITY;
CUSTOMER / C1, C2, C3, C4/ : DEMAND;
ROUTES( WAREHOUSE, CUSTOMER) : COST, VOLUME;
ENDSETS
! The objective;
[OBJ] MIN = @SUM( ROUTES: COST * VOLUME);
! The demand constraints;

@FOR( CUSTOMER( J): [DEM]
@SUM( WAREHOUSE( I): VOLUME( I, J)) >=
DEMAND( J));
! The supply constraints;

@FOR( WAREHOUSE( I): [SUP]
@SUM( CUSTOMER( J): VOLUME( I, J)) <=
CAPACITY( I));
! Here are the parameters;

DATA:
CAPACITY = 30, 25, 21 ;
DEMAND = 15, 17, 22, 12;
COST = 6, 2, 6, 7,
4, 9, 5, 3,
8, 8, 1, 5;
ENDDATA
end
Page 4 LINGO
2.3 A quadratic assignment problem
MODEL:
! A quadratic assignment problem: Given transfers between flights and

distance between gates, assign flights to gates to minimize total transfer
distance;
SETS:
FLIGHT/1..3/; ! There are three flights;
GATE/1..4/; ! There are five gates;
FXG( FLIGHT, GATE): X; !Flight-gate assignment;
GXG( GATE, GATE): T; !Distance between gates;
FXF( FLIGHT, FLIGHT): N; !Transfers btwn flights;
ENDSETS
DATA:
N = 0 30 5 ! No. transfers between flights;
20 0 0
30 40 0 ;
T = 0 5 10 14 ! distance between gates;

5 0 5 10
10 4 0 6
15 10 5 0 ;
ENDDATA
SETS:
! Transfer between 2 flights must be required and related to 2 different
gates. Warning: this set gets big fast.;
TGTG( FLIGHT, GATE, FLIGHT, GATE)|
&1 #LT# &3 #AND# (( N( &1, &3) #NE# 0) #AND#
( T( &2, &4) #NE# 0) #OR# ( N( &3, &1) #NE# 0)
#AND# ( T( &4, &2) #NE# 0)): Y;
ENDSETS
! Each flight, B, must be assigned to a gate;

@FOR( FLIGHT( B):
@SUM( GATE( J): X( B, J)) = 1);
! Each gate, J, can receive at most one flight;

@FOR( GATE( J):
@SUM( FLIGHT( B): X( B, J)) <= 1);
! Force Y(B,J,C,K)=1 if B assigned to J and C assigned to K;

! Assumes the T and N matrices are nonnegative;
@FOR( TGTG( B, J, C, K):
Y( B, J, C, K) >= X( B, J) + X( C, K) - 1);
! Min the sum of transfers * distance;

MIN = @SUM( TGTG( B, J, C, K): Y( B, J, C, K) *
( N( B, C) * T( J, K) + N( C, B) * T( K, J)));
! Make the X's 0/1 (Y's will naturally be 0/1);

@FOR( FXG: @BIN( X));
END
LINGO Page 5
2.4 Dynamic programming
MODEL:
SETS:
! Dynamic programming illustration (see Anderson, Sweeney & Williams, An
Intro to Mgt Science, 6th Ed.). We have a network of 10 cities. We want to
find the length of the shortest route from city 1 to city 10.;
! Here is our primitive set of ten cities, where F( i) represents the

shortest path distance from city i to the last city;
CITIES /1..10/: F;
! The derived set ROADS lists the roads that exist between the cities (note:
not all city pairs are directly linked by a road, and roads are assumed to
be one way.);
ROADS( CITIES, CITIES)/
1,2 1,3 1,4
2,5 2,6 2,7
3,5 3,6 3,7
4,5 4,6
5,8 5,9
6,8 6,9
7,8 7,9
8,10
9,10/: D;
! D( i, j) is the distance from city i to j;
ENDSETS
DATA:
! Here are the distances that correspond to the above links;
D =
1 5 2
13 12 11
6 10 4
12 14
3 9
6 5
8 10
5
2;
ENDDATA
! If you are already in City 10, then the cost to travel to City 10 is 0;
F( @SIZE( CITIES)) = 0;
! The following is the classic dynamic programming recursion. In words, the

shortest distance from City i to City 10 is the minimum over all cities j
reachable from i of the sum of the distance from i to j plus the minimal
distance from j to City 10;
@FOR( CITIES( i)| i #LT# @SIZE( CITIES):
F( i) = @MIN( ROADS( i, j): D( i, j) + F( j))
);
END

Discrete Optimization in Flexible Manufacturing Systems Laboratory

Uploaded by

Copyright:

Available Formats

Discrete Optimization in Flexible Manufacturing Systems Laboratory

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Discrete Optimization in Flexible Manufacturing Systems Laboratory

Uploaded by

Copyright:

Available Formats

Discrete optimization

in Flexible Manufacturing Systems

1.1 Constraint translation

@FOR( C ( j): @SUM( W ( i): v( i, j) ) >= d( j) );

♦ @SIZE( <set> ) size of a set.

1.5 Conditional expressions

1.6 Data files

! The total number of Wordsmiths produced is limited

! The total number of Numbercrunchers produced is

! The total amount of memory used in all machines

2.2 Transportation Problem

! A 3 Warehouse, 4 Customer Transportation Problem;

! The demand constraints;

! The supply constraints;

! Here are the parameters;

2.3 A quadratic assignment problem

! A quadratic assignment problem: Given transfers between flights and

T = 0 5 10 14 ! distance between gates;

! Each flight, B, must be assigned to a gate;

! Each gate, J, can receive at most one flight;

! Force Y(B,J,C,K)=1 if B assigned to J and C assigned to K;

! Min the sum of transfers * distance;

! Make the X's 0/1 (Y's will naturally be 0/1);

2.4 Dynamic programming

! Here is our primitive set of ten cities, where F( i) represents the

! The following is the classic dynamic programming recursion. In words, the

You might also like