| 2LP Manual: Essentials and Concepts | [Download PostScript Version] |
| 2LP Manual: Language Reference | [Download PostScript Version] |
| 2LP Manual: Keywords and Terms | [Download PostScript Version] |
A statement is a constraint, a test an assignment, a procedure call, a block built up from others statements using braces, one of the control statements continue, break, return, or a compound statement constructed with one of the other programming constructs of 2LP. A statement in 2LP either succeeds or fails.
Statements in 2LP can be grouped into a single statement block by enclosing them in braces. The statements within a block are invoked as a unit.
A procedure has the form>
proc_name(<parameters>)
{
<local declarations>
<statements>
}
The main procedure must be called 2lp_main()
The 2LP language supports four data types: int, double, string, and continuous. The types double and int are the same types as in C and C++, i.e. int is the integer type and double is the floating point type. The type string is analogous to char* in C. Arrays of each of the four basic types can be declared.
An affine expression and its type are defined by induction. The most basic affine expressions are identifiers and constants, which have their given types. This is the base case of the induction. An affine expression is then defined as an identifier, a constant, or a compound expression built up from simpler affine expressions. A compound expression inherits its type from its constituents. Let's look at some examples:
| Expressions and Types | |
| Expression | Type |
| a | int or double |
| b | int or double |
| X | continuous |
| X + a | continuous |
| (X + a) | continuous |
| b*(X + a) | continuous |
| floor(b*(X+a)) | double |
| Y - floor(b*(X + a)) | continuous |
More formally, compound expressions are built by means of the following constructions:
function ( <affine expression> )
( <affine expression> )
<unary plus/minus> <affine expression>
<affine expression> <binary operator> <affine expression>
For compound terms formed by applying a function, the resulting affine expression has the type which is returned by the function. Putting parentheses around a term produces a new term of the same type; similarly, prefixing an expression with a unary plus or minus yields an expression of the same type.
In combining expressions by means of binary operators the type continuous dominates double and the types continuous and double both dominate int. There are two restrictions. In forming a compound affine expression, if the binary operator is *, then the left hand argument cannot be of type continuous; if the operator is /, neither argument can be of type continuous.
Hence, the basic rule is that an affine expression of type continuous can not be used as the left hand argument of a multiplication or as either argument to a division. The 2LP parser checks that complex expressions yield linear constraints by verifying that this rule is observed. So, for example, the line of code
b <= 1.5*(X + 1)*(Y - 12*X);
cannot be parsed successfully because the expression (X + 1) is being used as a coefficient.
Local and global variables of all types can be declared. Local variables of type continuous are of static storage class. This means that each time a procedure is called its local continuous variables denote the same variables as in previous calls. The constraints constructed with these variables remain in force after the procedure is exited successfully.
The relational operators are ==, <=, >=, !=, <, and >. The first three are called closed relational operators; the second three are called the strict relational operators. The strict relational operators !=, >, and < can only be used in tests and not in constraints.
A constraint is a declarative statement which enforces relations on continuous variables. Formally stated, a constraint is an expression of the form
<affine expression> <closed relational operator> <affine expression>
where at least one of the affine expressions is of type continuous. The closed relational operator can be ==, <=, or >=. When a constraint succeeds, it is consistent with the feasible region defined so far and is added to the defining constraints of the region. However, if a new constraint is added and no points lying in the current feasible region satisfy the new constraint, then the new constraint fails.
A test compares two expressions which are of type double or int. Formally, a test is an expression of the form
<affine expression> <relational operator> <affine expression>
where the affine expressions are not of type continuous. As with constraints, tests either succeed or fail. However, in contrast to constraints, tests will not affect the current feasible region or witness point. The strict operators !=, >, and < can only be used in tests and not in constraints. Expressions of type string can not be used in tests.
The fundamental operation on variables of types int and double is the assignment operation. This takes the form
<variable identifier> = <affine expression>;
where the variable and the affine expression are both of type int or double.
The fundamental operation on variables of type string is also the assignment operation. This takes the form
<variable identifier> = <variable identifier or constant>;
where the variable identifiers and the constant are both of type string.
Unlike constraints and tests, an assignment statement always succeeds.
A corner point on a polyhedron is called a vertex. The simplex based constraint solver maintains the current feasible region together with a distinguished vertex; this vertex is called the witness point.
When a variable of type continuous is used in a call to a built-in function and the parameter type is double then the witness point value is used. If a variable or expression of type double is used in a built-in function or procedure or user-defined procedure where an integer value is expected, the value is truncated; if a variable or expression of type int is used where a double is expected, the value is coerced to type double.
Loop variables are introduced in the headers of and loops, or loops, and c_or loops. For example, the variables i, j, and k are loop variables in the code segments below.
and(int i=0;i<N;i++) { ... }
or(int j=0;j<M;j++) { ... }
For and loops, or loops and c_or loops, the variable introduced as a loop control variable cannot be assigned in the body of the loop and can only be passed by value in a procedures call that occurs in the body of the loop. If backtracking takes place to a choice point which is within the scope of the loop body, the loop control variable is restored to its value at the creation of the choice point. The loop control variable's scope is restricted to the body of the loop. Note that this is different from the ANSI C and C++ conventions where the loop variable remains available until the end of the enclosing procedure.
The increment statement i++ can only be used in the step assignment in a loop header, elsewhere i=i+1 must be used. A similar remark holds for unit decrements.
Conjunction can be expressed two ways. The first is by simple juxtaposition:
<statement> <statement> ... <statement>
The second way is by means of the and loop. The keyword and begins the loop and is followed by a loop header. The general form of the loop header is
<initial assignment>; <loop condition>; <step assignment>
The initial assignment creates and initializes a new variable, called the loop control variable. The step assignment assigns a new value to the loop control variable. This allows for a wide range of ways of updating the loop variable.
The and loop header is followed by a statement which is called the body of the loop. As with all loop constructs in 2LP, the loop control variable in the and loop can only be assigned in the loop header and not within the body of the loop, nor may its value be accessed after the loop is exited.
The keyword sigma begins the loop and is followed by a loop header which has the form
sigma (<initial assignment>; <loop condition>; <step assignment>)
Unlike the other loop constructs, in this loop the condition must be a test on the control variable. The test is of the form
<control variable> <relational operator> <affine expression>
where affine expression is of type int or double. The relational operator can be <=,>=,==, <,>, or !=.
The value of the control variable is changed after each pass through the loop by the step assignment that assigns a value to the control variable. Note that this form allows change to the control variable in increments other than unit increments. For example, to sum the even-indexed elements of a 10-element array called b, one would write
a = sigma(int i=0;i<10;i=i+2) b[i];
When we do use unit increments, we may substitute i++ for the statement i=i+1. Similarly, for unit decrements, we use i=i-1 or i--.
The scope of the sigma loop is the summand that immediately follows the loop header, and the sigma loop expression has the same type as this term. Thus
sigma(int i=0;i<N;i++) a[i]*(X[i] - b[i])
is of type continuous and
sigma(int i=0;i<N;i=i+2) i
is of type int. One more point: if the test in the loop never succeeds, then the loop returns 0. For example the expression
sigma(int i=0;i<0;i=i+2) i
evaluates to 0 because the test 0 < 0 fails.
Persistent disjunction is expressed by the either/or construct. The syntax is:
either <statement 1>
or <statement 2>
...
or <statement n>
The statements are executed in order until one of them succeeds or they all fail. If none of them succeeds the either/or statement itself fails. If the first statement to succeed is <statement i> where i<n, a choice point is created. This means that if a later statement outside the scope of this either/or fails and control returns to the either/or statement, the process restarts with <statement i+1>.
Persistent disjunction can also be expressed with the or loop construct. The syntax is:
or(<initial assignment>; <loop condition>; <step
assignment>)
<statement>
The variable in the initial assignment is called a loop variable or loop control variable. Its scope is the <statement>. The <statement> is called the body of the loop. The semantics of this loop are as follows: the loop variable is initialized; the <loop condition> is executed and if it fails the loop is exited unsuccessfully. If <loop condition> succeeds, the loop continues. If <statement> succeeds, the loop exits successfully and a choice point is recorded; if this choice point is activated by a later failure, the loop variable is updated using the value it had when the loop last exited successfully. If a break statement is executed within the body of the loop, the loop is exited with failure and no choice points are created. If a continue statement is executed within the body of the loop, all choice points created in the loop body are removed; control returns to the top of the loop.
For conditional disjunction as in C/C++, the 2LP syntax is expressed by the c_either/or construct. The syntax is:
c_either <statement>
or <statement>
...
or <statement>
Conditional disjunction is close to if/then/else in spirit and in semantics. In fact,
c_either <statement>
or <statement>
is equivalent to
if <statement>
then ; // Null statement
else <statement>
The statements are executed in order until one of them succeeds or they all fail. If none of them succeeds the c_either/or statement itself fails. If the first statement to succeed is <statement i> where i<n, the program proceeds past the c_either/or statement but no choice point is created. This means that if a later statement fails, control does not return to the c_either/or statement.
Conditional disjunction can also be expressed with the c_or loop construct. The syntax is:
c_or(<initial assignment>; <loop condition>; <step
assignment>)
<statement>
The variable in the initial assignment is called a loop variable or loop control variable. Its scope is the <statement>. The <statement> is called the body of the loop. The semantics of this loop are as follows: the loop variable is initialized; the <loop condition> is executed and if it fails the loop is exited unsuccessfully. If <loop condition> succeeds, the loop continues. If <statement> succeeds, the loop exits successfully but no choice point is recorded. If a break statement is executed within the body of the loop, the loop is exited with failure and no choice points are created. If a continue statement is executed within the body of the loop, all choice points created in the loop body are removed; control returns to the top of the loop.
Implication and Conditional Statements.
The syntax of the implication statement in 2LP is
if <statement>
then <statement>
If the antecedent statement succeeds, the consequent statement is called; if the consequent fails, the if/then statement fails, otherwise it succeeds. If the antecedent statement fails, the if/then statement succeeds without calling the consequent statement. The if/then/ else statement has the following syntax:
if <statement>
then <statement>
else <statement>
In this construct, if the antecedent fails, the statement following else is called. The entire if/then/else succeeds depending upon the success or failure of the statement following the else. By way of example, consider the statement
if X >= Y;
then Z <= 100;
else Z >= 150;
If the constraint X >= Y is consistent with the current feasible region, then the conditional reduces to the conjunction X >= Y; Z <= 100. If the constraint X >= Y is not consistent with the current feasible region, Z <= 100 is not invoked but the constraint Z >= 150 is tried; in this case if it is not feasible, the entire if/then/else statement fails. The interpretation of implication for constraints generalizes the standard programming semantics for if/then/ else. When constraints are not involved, the conditional constructs in 2LP have their usual meaning. Thus, for example, if a and b are of type int or double, the code segment
if a > b;
then printf("Good morning world");
else printf("Good evening world");
will print "Good morning world" only if the test a > b succeeds; otherwise, it prints "Good evening world."
A choice point is created by an either/or statement or by an or loop. Choice points are the internal mechanism for supporting persistent disjunction. Upon failure, the code returns to the last choice point created which still has open alternatives. This mechanism is robust in that a choice point will be returned to even after the procedure in which it is created is exited.
2LP provides a preprocessor facility, which is a preliminary step in compilation. The two features supported are #define and #include.
The #define feature is used to replace a token with an arbitrary sequence of characters, the substitution can be disabled by #undef . Substitutions are made only for tokens and do not take place within quoted strings. The general form is :
#define <identifier> <replacement string>
#undef <identifier>
The most common use of #define is to abstract dimensions:
#define N 10
continuous X[N];
Another common use provide syntactic sugar. Two examples are:
#define do_and_undo not not //double negation
#define until_break and(;;) //infinite loop
#define until_success or(;;) //infinite loop
This preprocessor feature does not support macros with arguments.
The #include feature is used for file inclusion. Any source line of the form
#include filename-in-quotes
can be used. Searching for the file begins where the source program was found. Included files may contain #include lines.
This feature can be used to edit and run models which would be too large for the editor if grouped into one file.
This keyword must be the procedure name for the main procedure.
absgap(double)
The absgap procedure establishes a gap between the last solution found in a find_max or find_min block. Example:
find_max: Z;
subject_to {
absgap(1.0);
search();
}
This keyword used to code an and loop. For example
and(int i=0;i<N;i++)
See also Conjunction.
The boolean keyword is used to create external functions that either succeed or fail. The external function should return an integer. For example:
extern boolean start_empty_job(int,int);
The break statement is used to break out of either an and, an or loop or a c_or loop. If it is used in an and loop, the and loop succeeds. If it is used in an or loop or c_or loop, the loop fails and returns without having created any choice points.
This keyword indicates that the disjunction is conditional as in C/C++.
See also Conditional Disjunction.
This keyword follows a c_either statement when using a conditional disjunction or begins a c_or loop construct.
See also Conditional Disjunction.
double ceil(double)
This function, when called with a double returns with next highest integer value. When it is called with a continuous variable, it returns the next highest integer value of the witness point of that variable.
This keyword is used in the body of and, or and c_or loops. In an and loop the body is exited successfully and control returns to the head of the loop. In an or loop the body is exited unsuccessfully and control is returned to the head of the loop; no choice points that were created in the body of the loop are kept.
The continuous keyword is used to create storage for continuous variables. Example:
continuous X,Y,Z[10];
See also Types.
The double keyword is used to create storage for double variables. Example:
double x,y,a[40];
See also Types.
This keyword indicates the beginning of the else part of an if/then/else statement.
See also Implication and Conditional Statements.
This keyword is used to indicate persistent disjunction. The either construct is followed by one or more or constructs.
See also Persistent Disjunction.
exit()
This procedure terminates the 2LP code.
This keyword is used to tell the 2LP system that the variables or procedures that follow are actually declared in an external DLL. This keyword must be followed by one of the following types: int, double, boolean, or void. Example:
extern int wait_list[QUEUESIZE][JOBS];
extern boolean goal(int);
double fabs(double)
This function, when called with a double returns the absolute value of the variable. When it is called with a continuous variable, it returns the absolute value of the witness point of that variable. Example:
d = fabs(wp(X));
The find_all keyword must be followed by a statement:
find_all <statement>
After <statement> succeeds, backtracking takes place and the next solution to <statement> is sought. This process continues until all solutions have been found. When no more solutions are possible, the find_all exits successfully without having changed the original feasible region.. However, if <statement> itself never succeeds, then the find_all <statement> also fails. Example:
find_all {
solve_salt_and_mustard();
count = count + 1;
}
The find_max keyword is used with the subject_to keyword to use a branch and bound search to find the maximum value of a variable or expression (the objective function) subject to the conditions in the subject_to block. This construct forces the code to constrain the objective function to be as good as the previous solutions found. The find_max construct fails if the statement following the subject_to fails. At exit the find_max construct shrinks the feasible region to a single point, namely the best solution that was found. Example:
find_max: Return;
subject_to
new_central_loop();
The find_min keyword is used with the subject_to keyword to use a branch and bound search to find the minimum value of a variable or expression (the objective function) subject to the conditions in the subject_to block. This construct forces the code to constrain the objective function to be as good as the previous solutions found. The find_min construct fails if the statement following the subject_to fails. At exit the find_min construct shrinks the feasible region to a single point, namely the best solution that was found. Example:
find_min: Cost; subject_to
and(int i=0;i<ITEMS;i++)
Serving[i] == k;
double floor( double )
This function, when called with a double returns with the nearest integer less than or equal to itself. When it is called with a continuous variable, it returns the nearest integer less than or equal to its witness point.
The keyword for the first part of an if/then/else statement.
See also Implication and Conditional Statements.
Used to create storage for integer variables. Example:
int i,j,k[40];
See also Types.
integral( continuous )
The integral function succeeds if the parameter is integer valued to within . Example:
no_injuries()
{
and(int i=0;i<N;i++)
integral(X[i]);
}
double lb( continuous )
This function returns the current lower bound of the continuous variable passed to it as a parameter. The current lower bound is the lower bound that the simplex solver has for this variable. Example:
check_bound(continuous R, int dir, double limit)
{
if dir == 1;
then ub(R) >= limit;
else lb(R) <= limit;
}
See also ub.
max: <affine expression>
This operator moves the witness point to a vertex of the feasible region for which the affine expression has the maximum possible value.
See also min.
min: <affine expression>
This operator moves the witness point to a vertex of the feasible region for which the affine expression has the minimum possible value.
See also max.
double nint( double )
This function, when called with a double returns with the integer value nearest to itself. When it is called with a continuous variable, it returns the nearest integer to its witness point.
not <statement>
The keyword not followed by statement succeeds if <statement> fails and conversely, the negation fails if <statement> succeeds. The feasible region is restored to its state preceding the execution of the construct regardless of its success or failure. Examples:
if not X <= Y;
then printf("The constraint would fail\n");
else printf("The constraint would succeed\n");
if not p();
then printf("A call to p() can be successful\n");
else printf("A call to p() can not be successful\n");
double objcdn( continuous )
This function returns a true or conservative estimate of how much the coefficient of the continuous variable can be decreased without requiring a change in the witness point. that yields the optimal solution.
See also objcup.
double objcup( continuous )
This function returns a true or conservative estimate of how much the coefficient of the continuous variable can be increased without requiring a change in the witness point that yields the optimal solution.
See also objcdown.
This keyword is used after an either statement or to code an or loop. For example:
or(int i=0;i<N;i++)
X[j] == i;
See also Persistent Disjunction.
This keyword has the same syntax as in C. It supports the ANSI C standard format options as given in The C Programming Language, B. Kernighan and D. Ritchie, Prentice Hall.
double random()
This built-in function returns a floating point number in the interval (0,1). Successive calls produce a pseudo-random sequence. The underlying pseudo-random number generator is seeded by a call to seed
double range ( continuous );
This built-in function returns an estimate of the amount the bound on a variable can be altered without changing its reduced cost. This estimate will be exact or conservative; over this range the reduced cost is equal to the shadow price.
double rc( continuous );
This built-in function returns the reduced cost of a continuous variable.
This statement exits the current procedure and returns to the calling procedure. Example:
if k==0
then {
a = 15;
return;
}
void seed(int)
A call to this procedure seeds the built-in pseudo-random number generator. Pseudo-random sequences are created by calls to random.
This keyword is for writing a constraint in a notation similar to the ordinary mathematical usage for the equation
For example, the 2LP expression is
sigma(int i=0;i<100;i=i+1) a[i]*X[i] == b;
The keyword string is used to create storage for character strings. Example:
string s,t,u[12];
This keyword is used with the find_min, and find_max keywords. Example:
find_min: Z;
subject_to
search();
This keyword is used as part of an if/then/else statement.
See also Implication and Conditional Statements.
double ub( continuous )
This function returns the current upper bound of the continuos variable passed to it as a parameter. The current upper bound is the upper bound that the simplex solver has for this variable. Example:
check_bound(continuous R, int dir, double limit)
{
if dir == 1;
then ub(R) >= limit;
else lb(R) <= limit;
}
See also lb.
The void keyword is used to declare external functions that are called from a 2LP model and interpreted as procedures that always succeed. Example:
extern void insert_states(int);
double wp(continuous):
The wp function returns the current value that the witness point gives to the expression passed as a parameter. The parameter to this function must be an affine expression of type continuous.
| Go back to the LBS Lab homepage | Any questions? Contact the Lab |