Multi-criteria trade-off analysis can be accomplished with a variety of optimization tools, including Microsoft Excel (for small-scale problems) and ILOG CPLEX.
Solving Linear Optimization Problems with ILOG CPLEX
ILOG CPLEX is a tool for solving linear optimization problems, commonly referred to as Linear Programming (LP) problems, of the form (CPLEX Online Manual):
Maximize (or Minimize) c_{1}x_{1} + c_{2}x_{2} +...+ c_{n}x_{n} subject to a_{11}x_{1} + a_{12}x_{2} +...+ a_{1n}x_{n} ~ b_{1} a_{21}x_{1} + a_{22}x_{2} +...+ a_{2n}x_{n} ~ b_{2} .......... a_{m1}x_{1} + a_{m2}x_{2} +...+ a_{mn}x_{n} ~ b_{m} with these bounds l_{i} <= x_{i} <= u_{i}, ..... l_{n} <= x_{n} <= u_{n} where "~" can be <= (less than or equal), >= (greater than or equal), or = (equal), and the upper bounds u_{i} and lower bounds l_{i} may be positive infinity, negative infinity, or any real number. |
The data you provide as input for this LP is:
Objective function coefficients: c_{1}, ...... , c_{n} Constraint coefficients: a_{11}, ...... , a_{mn} Right-hand sides: b_{1}, ........ , b_{m} Upper and lower bounds: u_{1}, ...... , u_{n} and l_{1}, ...... , l_{n} |
CPLEX also can solve several extensions to LP:
Procedure for Problem Definition and Solution
Components of problems should be entered in the following order: (1) objectives; (2) constraints; (3) bounds; (4) completion of the problem definition.
Points to note are as follows:
Before entering the objective function, you must state whether the problem is a minimization or maximization. For example, you might type:
maximize x1 + 2x2 + 3x3
In the simple example shown immediately above, the variables are named simply x1, x2, x3, but you can give your variables more meaningful names such as cars or gallons.
Once you have entered the objective function, you can move on to the constraints. However, before you start entering the constraints, you must indicate that the subsequent lines are constraints by typing:
subject to or st
These terms can be placed alone on a line or on the same line as the first constraint if separated by at least one space. Now you can type in the constraints in the following way:
st x1 + x2 + x3 <= 20 x1 - 3x2 + x3 <= 30
Finally, you must enter the lower and upper bounds on the variables. If no bounds are specified, ILOG CPLEX will automatically set the lower bound to 0 and the upper bound to +ve infinity. You must explicitly enter bounds only when the bounds differ from the default values. In our example, the lower bound on x1 is 0, which is the same as the default. The upper bound 40, however, is not the default, so you must enter it explicitly. You must type bounds on a separate line before you enter the bound information:
bounds x1 <= 40
Since the bounds on x2 and x3 are the same as the default bounds, there is no need to enter them.
You have finished entering the problem, so to indicate that the problem is complete, type:
end
on the last line.
CPLEX has a wide range of features for retrieving and displaying problem characteristics (e.g., the binary variables, the bounds, the constraints, and so forth). We refer interested readers to the Online CPLEX manual for a more complete discussion.
Optimal Solution
The optimal solution that CPLEX computes and returns is:
Variables: x_{1}, ..... , x_{n} |
Simple Example
CPLEX is available on the ISR solaris (UNIX) workstations. To access CPLEX, type:
prompt >> tap cplex prompt >> cplex
Now suppose that we create an input file "example1" containing a description of the linear programming problem:
MAX X - 3Y ST A: -X + Y <= 3.5 B: X + Y <= 5.5 C: X + 2Y <= 9.0 D: X <= 4.5 BOUNDS X >= 0 Y >= 0 END
To load "example1" into CPLEX, we simply type:
CPLEX> read example1 lp Problem 'example1' read. Read time = 0.01 sec. CPLEX>
Here, we use the argument "lp" to indicate that the file is of type "linear programming."
The following script of code shows commands for displaying the problem parameters, and finding and displaying the optimal solution:
CPLEX> display problem all Maximize obj: X - 3 Y Subject To A: - X + Y <= 3.5 B: X + Y <= 5.5 C: X + 2 Y <= 9 D: X <= 4.5 Bounds All variables are >= 0. CPLEX> CPLEX> optimize Tried aggregator 1 time. LP Presolve eliminated 4 rows and 2 columns. All rows and columns eliminated. Presolve time = 0.00 sec. Dual simplex - Optimal: Objective = 4.5000000000e+00 Solution time = 0.00 sec. Iterations = 0 (0) CPLEX> CPLEX> display solution variables Display values of which variable(s): X Variable Name Solution Value X 4.500000 CPLEX> display solution variables Display values of which variable(s): Y The variable 'Y' is 0. CPLEX> CPLEX> display solution variables X-Y Variable Name Solution Value X 4.500000 All other variables in the range 1-2 are zero. CPLEX>
The optimal solution is at (x,y) coordinate ( 4.5, 0), where the objective function equals 4.5 - 0 = 4.5.
Copyright © 2005, Mark Austin. All rights reserved. This document may not be reproduced without expressed written permission of Mark Austin. |