This tutorial include basics of using popular optimization solvers and modeling tools.
O. Login to Servers
It is easy and convenient to start and use AMPL on the servers (polyps) of Lehigh CORAL. To access lehigh servers, you need to ssh with your personal account (assigned by Lehigh ISE Administrator Aykut Bulut). The command to login to servers at Lehigh ISE on Linux/Unix based operating systems (e.g. Mac OS, Red Hat, Ubuntu, Debian etc.) is:
ssh
For Windows users, please install PuTTY. Refer to CORAL User Guide and PuTTY website for installation and usage. It’s simple!
There are currently three types of machines with shared storage under Lehigh ISE Department.
“coral” is mainly for documentation usage or administrative usage which does not work with many solvers and software (probably some GNU commands and simple solvers works on it).
“shark” is mainly used for connecting to Lehigh internal servers via off-campus internet service. It is also lack of mainstream solvers and software.
“polyps” contains the main clusters which we should generally used for experiments and programming. This is only accessible via on-campus internet or Lehigh campus VPN. The polyps includes multiple clusters. You will be assigned one when you login. However, you can ssh into one specific cluster which is NOT recommended (except for particular use).
NOTICE: due to their usages and limited software, we do NOT recommend run programs using “coral” and “shark”. These two are used to connect to the Lehigh internal server “polyps”.
A list of the resources you can use on “polyps” is available here. Feel free to refer to Lehigh ISE/COR@L Wiki to know more about tools and systems available at ISE.
To log out the server, just simply type
logout
and enter.
Before the tutorial, please copy all the folder for your tutorial by entering
cp -r /tmp/ISE406T ./
I. AMPL
AMPL (A Mathematical Modeling Language) is a algebraic language modeling tool to describe and solve large-scale mathematical optimization problems. It is written and maintained by ampl.com. Please visit here for a complete list of different solvers and check the column of documentations for usages. To access AMPL under “polyps”, just type in:
ampl
then type “enter/return”. To exit type in:
exit;
In order to write a AMPL model, we need to understand some of the important syntaxes. A list of available functions and syntaxes in writing an AMPL model is reachable at http://www.ampl.com/BOOK/CHAPTERS/10-params.pdf. Some basics are:
param: declare/define parameters (known)
set: declare/define a set of parameters
var: declare/define variables (unknown to be solved)
sum: sums of multiple formulas
minimize/maximize ***: minimizing/ maximizing an objective
subject to: followed by constraints
The following serves our first example just for practicing writing a model:
# Example 1
# Declaration of parameters
param m = 5;
param a {i in 1..m, j in 1..m} = i-j;
var x {i in 1..m} >=0;
# Objective Function
minimize obj: x[1] + 2*x[2];
# Constraints
subject to constraint1 {i in 1..m}:
sum {j in 1..m} a[i,j]*x[j] <= 0;
subject to constraint2 {j in 1..m}:
x[j] <= 10;
Please save the file as “***.mod” (with suffix mod) for modeling with AMPL. To simply introduce the usages of AMPL in the documentation, I list the following basic usage for your reference.
Model/Load an AMPL model file:
model ***.mod;
Form an AMPL model file:
write **.mod;
Reset the whole model (Before loading a new model):
reset;
Sometimes we can immediately get a notice from AMPL showing that
Solution determined by presolve; objective obj = 0.
for Example 1.
Select solver of your choice:
option solver ***;
where “***” stands for the solver name, and some of the available solvers that you may use in your Lehigh ISE 406 class can be chosen by the following names:
CPLEX: cplexamp
MOSEK: mosek
Gurobi: gurobi_ampl
We will not illustrate all the methods in each solver. Just take CPLEX with AMPL as an example for the following case (comes in the end of this section). Again, for a complete list of solvers and corresponding methods, please refer to here. Note that not all the solvers listed in available in Lehigh ISE “polyps” server since we may only have an older version of AMPL installed.
Load an existing data file (please load a model before loading data):
data **.dat;
Please do NOT forget the semicolon “;” for commands under AMPL.
To illustrate how to load existing data set diet.dat and model diet.mod. Please download them then just simply load the model and data, and form the model by
model diet.mod; data diet.dat; write diet.mod;
More examples with models and data are available at the AMPL website with a detailed illustrations of the problems at here.
You can also manually input data at AMPL prompt by entering data mode with
and data, and form the model by
data;
and set any parameter value, say for m, by using
param m := ***;
Starting with anything else will exit the data mode (say “model;”).
We can review the existing parameters, sets, variables, constraints and the objective by
show;
and display any values of these items by
display ***;
After setting all the options just type
solve;
which would return with the solving status. For the diet example, it shows
CPLEX 12.6.1.0: optimal solution; objective 88.2 1 dual simplex iterations (0 in phase I)
To change the method in CPLEX from default method to, say barrier method (IPM), just type
option solver cplexamp; option cplex_options baropt;
then solve it and it shows on my laptop that
CPLEX 12.6.1.0: baropt CPLEX 12.6.1.0: optimal solution; objective 88.2 6 barrier iterations 0 push, 1 exchange dual crossover iterations
II. CPLEX
MPS (Mathematical Programming System) file is a format originally proposed by IBM, which later can be accepted and solved by most commercial or some open-source LP solvers, including CPLEX, GuRoBi and MOSEK. Other format files for LP problems include bas and lp files. Please check the user’s manual for reading them for different solvers.
We are taking a classical example of mps file and try to use it for demonstrating usage of these mentioned popular solvers.
CPLEX is a commercial solver developed by IBM. To access CPLEX under “polyps”, just type in:
cplex
then type “enter/return”. To exit type in:
quit
and for any question just type:
help
It’s really easy to operate with CPLEX with the “help” command and the user’s manual. Note that dual to the possibly limited updates of CPLEX on polyps, some “newly added” functions may not work. Let’s take the pilot.mps as an example. To read the MPS file, either
read pilot.mps
or
read pilot mps
works in CPLEX. Then we can solve it by using primal method/simplex with
primopt
or just simply truncated form “prim”.
Please practice yourself with different methods available in CPLEX and compare the results.
III. Gurobi
Gurobi is also a commercial optimization solver by Gurobi Optimization. Gurobi is named for its founders: Zonghao Gu, Edward Rothberg and Robert Bixby. Bixby was also the founder of CPLEX, while Rothberg and Gu led the CPLEX development team for nearly a decade. To access Gurobi on the cluster, just enter:
gurobi.sh
and read the mps file by
m = read('pilot.mps')
To set different methods or parameters, please use
setParam(method/parameter, value)
and solve the problem by using
m.optimize()
For a complete list of usages, please refer to the official guide or other resources online.
IV. MOSEK
MOSEK is a commercial mathematical optimization solver by MOSEK ApS. To use MOSEK to solve the mps format problem, just type
mosek pilot.mps
with options for different methods. Please refer to the User’s Guide and other references for different options. For example, the following command exploit and solve the problem by using primal simplex.
mosek pilot.mps -d MSK_IPAR_OPTIMIZER MSK_OPTIMIZER_PRIMAL_SIMPLEX
The “pilot.bas” file is generated for storage of solutions and iterations.
V. MATLAB
MATLAB, developed by MathWorks, is a widely used programming software across all engineering fields. However, this is a commercial software and is very expensive to purchase, and currently there is no academic license free to use (cheaper but not free, MOSEK, CPLEX and Gurobi all have free academic license available). Fortunately, we have it available on machines owned by Lehigh (including polyps: just type matlab to enter), and I recently learned that it should be free for all Lehigh students to use for academic purpose now. Please log into your Lehigh account and download it from here if you would like to. Alternatively, GNU Octave is also available as an open-source version of MATLAB.
All the mentioned solvers, namely CPLEX, GuRoBi and MOSEK, have interfaces for MATLAB. It is recommended that you can learn to install the three solvers with MATLAB interfaces although this is not mandatory. If you are interested, just refer to the manuals I cited above.
In this scope, we will learn how to use some of the popular MATLAB optimization tool boxes available. The ones that are popular for research purpose are CVX Toolbox, SeDuMi and YALMIP. Since the installation guide and user’s guide is detailed enough, and it’s not really our focus in ISE 406 class, we won’t illustrate any more on CVX, which also provides solvers of MOSEK, Gurobi, etc.
SeDuMi is an optimization solver mainly for solving SDP (semidefinite programming) problems, currently maintained by Lehigh University. Our focus here is not on the definition of SDP problems and you will be able to learn it in your future classes, please refer to the Wiki page for more knowledge into this topic. Download and unzip the package at SeDuMi Github. Even though their installation guide says that one needs to run install_sedumi to install it. In fact, one may just add all the directories to your MATLAB path and it would be sufficient to use it. There is an official user guide available, and please take a look for your reference. Now let us see how to use SeDuMi to solve a SDP (semidefinite programming) problem.
Some commonly used simple syntaxes are:
K.f: number of free components
K.l: number of non-negative components
K.q: dimensions for quadratic or second-order cone constraints
K.s: dimensions for positive semi-definite (PSD) constraints
For instance, we take the example prob_sedumi, which is by getting the largest eigenvalue of a single matrix A. The formulation is somehow simple and can be written as the following SDP problem.
min x s.t. xI-A≽0
By running the code as following (with specific A defined in the code)
A = [1 -2 3; -2 0 -4; 3 -4 5];
K.s = size(A,1);
I = eye(K.s);
bt = -1;
ct = -[vec(A)];
At = -[vec(I)];
[x,y,info]=sedumi(At,bt,ct,K);
A solution of y = 8.8612 should be returned and if you check the eignvalues of A, the largest one exactly matches this value.
For more information about how to solve different problems using SeDuMi, please refer to some existing tutorials online (say here).
YALMIP is a popular optimization solver which is originally developed for solving LPs and SDPs but later was promoted to a more complete package. For installation, simply download the package and unzip it. Then add folders under the YALMIP directory to your MATLAB path. A lazy piece of code provided by the YALMIP website is to run the following the MATLAB command window.
cd YALMIPfolderShouldbeHere urlwrite('https://github.com/yalmip/yalmip/archive/master.zip','yalmip.zip'); unzip('yalmip.zip','yalmip') addpath(genpath([pwd filesep 'yalmip'])); savepath
Then type the following to verify the success of installation:
yalmiptest
and if there are no errors, then you are done with installation.
If you are interested, please refer to YALMIP website for more information on available solvers and how to solver other type of methods. The three mentioned solvers above are also available in YALMIP. There is also a list of commonly used commands in YALMIP at here. Some of the basic commands include:
sdpvar: set SDP variables, e.g. x = sdpvar(d,1) is a d dimensional variable;
sdpsettings: set solver for optimization, e.g. options = sdpsettings(‘solver’,’sedumi’);
optimize: solve the problem with desired optimization solver; usage: optimize(constraints, objective, options).
The syntax for writing the constraints and objective is simple. For constraints, if we use “cons” to represent, that should simply be initialized as
cons = [Ax <= b];
with know A, b. We may also add additional constraints by
cons = cons + [Bx <= d]; cons = cons + [x >= 0];
The objective can be simply written in the form similar to:
obj = c'*x;
Then we can solve the problem by
optimize(cons, obj, options);
The syntaxes for YALMIP is pretty simple and it works with most mathematical operators in MATLAB. For instance, we take the example prob_yalmip which is to solve the following problem as an example: find a non-negative pair of (x1, x2) which solves the following problem:
min 2x(1) + x(2)
s.t. 2x(1) + 2x(2) - 1 ≥ 0.1 |x|
2x(1) + 2x(2) - 2 ≥ 0.1 |x|
where the norm is the Euclidean norm.
By solving the problem with SeDuMi through YALMIP, the code is appeared as
ops =sdpsettings(‘solver’,’sedumi’);
A = [2 2; 2 1];
e = [1;1];
b = [1;2];
c = [2;1];
x = sdpvar(2,1);
prob = [A*x-b>=0.1*sqrt(x(1)^2+x(2)^2)*e];
prob = prob + [x(1)>=0];
prob = prob + [x(2)>=0];
obj = c’*x;
solvesdp(prob,obj,ops);
x = double(x);
obj = double(obj);
The solution is stored in x and the corresponding objective value is in obj.
There are also a lot of optimization functions originally available in MATLAB such as linprog for linear programming and quadprog for quadratic programming. If you are interested, you can check the MATLAB Optimization Toolbox for a complete list of all those functions with instructions and usages.
ATTENTION! Please finish your assignments for ISE 406 in accordance with the requirements. If the problem requires you to write an AMPL file and solve with CPLEX, MOSEK, Gurobi, please do NOT use other interfaces of these solvers (YALMIP, SEDUMI, etc.). Always be in consistent with the instructor’s requirements. Otherwise, you will get no points 🙂
Updated: Sep 29, 2016.
