Utils

Information for prospective graduate students and associates

Our research group is heterogeneous and always looking for graduate students and postdocs who are interested in research in optimization, transportation, and logistics. This page in intended for prospective graduate students. Read the information on this page very carefully.

Due to the large volume of solicitation, make a well-articulated case for yourself and provide relevant information, or you will be ignored. This includes but is not limited to

  1. not sending mass email. Make your case personal. What part of my research interests you? What can you offer to the group?
  2. Be precise on the research topics that interest you.
  3. Computing is extremely important. Can you code (not Google code!)? In which languages?
  4. What is your background in optimization? What exact and heuristic methods did you use (i.e., implemented yourself)?
  5. Do you have partial funding for your studies? Note that FSA ULaval offers very good funding to all accepted M.Sc. and Ph.D. students.

English is mandatory. Your email should demonstrate your skills in writing properly.

For M.Sc. and Ph.D. students: although all teaching is done in French at FSA ULaval, you may write your thesis in English. Note, however, that you need to provide the results of a formal French test before admission.

If you read through here, follow these rules and send us your CV, examples of your research, codes, and keep it short.

Install and run Concorde with CPLEX

Concorde TSP is one of the best solvers for the Traveling Salesman Problem. Its current version was released in 2003, but it is still considered to be the state of the art in its field.

CPLEX is a general purpose solver. It is also considered to be one of the best in its class.

In order to obtain exact solutions with Concorde, one needs to link it to a solver. However, Concorde’s documentation falls short, since in 2003 CPLEX’s version was 8.0, and it is currently under version 12.9 (as of April 2019).

To link and compile Concorde with CPLEX, you will need to follow the instructions below:

1. Download:

Concorde TSP: Concorde-03.12.19 from http://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm

CPLEX version 12.9: see instructions to download and install CPLEX.

2. After installing CPLEX, extract concorde files:

gunzip co031219.tgz
tar xvf co031219.tar

3. Change the following concorde files before linking it to CPLEX:

cd concorde

– to avoid undefined reference to ’dlopen’ or ‘pthread’ or similar.

In “concorde/Makefile.in” change LIBFLAGS to:

            LIBFLAGS = @LIBS@ -lpthread

In “concorde/TSP/Makefile.in” change LIBFLAGS to:

            LIBFLAGS = @LIBS@ -lpthread -ldl

4. Create simlinks from some CPLEX files to the directory where you want to compile Concorde:

ln -s /path/to/cplex/include/ilcplex/*.h .
ln -s /path/to/cplex/lib/x86-64_sles10_4.1/static_pic/libcplex.a .

5. Run the configure:

./configure --prefix=/path/to/concorde –with-cplex=/path/to/concorde

6. Run make

make

7. Change to following concorde files after linking it to CPLEX:

– To avoid error: expected ‘,’ or ‘. . .’ before ‘new’ or ‘class’

In “concorde/concorde.h” use find and replace to change all *new) to *NEW) and all *class) to *CLASS)

–  To avoid error: ‘CPX_PARAM_FASTMIP’ undeclared (first use in this function).

In “concorde/LP/lpcplex8.c” after #undef  CC_CPLEX_DISPLAY add:

            #ifndef CPX_PARAM_FASTMIP
            #define CPX_PARAM_FASTMIP 1017
            #endif

8. Rename “concorde.a” to “libconcorde.a”

mv concorde.a libconcorde.a

Solving a TSP with concorde using a TSPLIB format file

To solve a TSP with the TSPLIB format using concorde you should put the file “concorde/TSP/concorde” and your .tsp file in the same folder and run:

./concorde filename.tsp

Solving a TSP with concorde in C++

You can find the documentation to all concorde functions in www.math.uwaterloo.ca/tsp/concorde/DOC/concorde_org.html.

A simple file implementing concorde in C++ is below.

Makefile:

TOCONCORDE = /full/path/to/concorde #e.g. /home/username/concorde
TOCPLEX = /full/path/to/cplex #e.g. /home/username/ibm
CPPFLAGS = -DIL_STD -I$(TOCONCORDE)
CXX = g++
LIBS = -L$(TOCONCORDE) -lconcorde -lilicplex -lconcert -lcplex -L$(TOCPLEX)/cplex/lib/x86-64_sles10_4.1/static_pic/ -L$(TOCPLEX)/concert/lib/x86-64_sles10_4.1/static_pic/ -m64 -lm -lpthread -ldl
main: main.o
            $(CXX) $(CFLAGS) -o main main.o $(LIBS)

main.cpp:


//This file solves a TSP using concorde given a symmetric 2D distance matrix

//Info about concorde functions: www.math.uwaterloo.ca/tsp/concorde/DOC/concorde_org.html

#include <iostream>
#include <vector>
extern "C" {
#include <concorde.h>
}

using namespace std;

//Receive a symmetric 2D distance matrix (dist) and create a TSP optimal tour (tour)
void solving_tsp_concorde(vector< vector<int> > * dist, vector<int> * tour){
 //Creating a sequential tour
 for(int i = 0; i < tour->size(); i++)
tour->at(i) = i;
 if(dist->size() > 4 ){//TSP for more than 4 cities
  int rval = 0; //Concorde functions return 1 if something fails
  double szeit; //Measure cpu time
  double optval; //Value of the optimal tour
  double *in_val = (double *) NULL; //Can be used to specify an initial upperbound (it can be NULL)
  double *timebound = (double *) NULL;; //Run time limit
  int success; //1 if the run finished normally, and set to 0 if the search was terminated early (by hitting some predefined limit) 
  int foundtour; //1 if a tour has been found (if success is 0, then it may not be the optimal tour)   
  int hit_timebound = 0; //1 if timebound was reached
  int *in_tour = (int *) NULL; //Gives a starting tour in node node node format (it can be NULL)
  int *out_tour = (int *) NULL; //Optimal tour (it can be NULL, if it is not NULL then it should point to an array of length at least ncount).  
  char *name = (char *) NULL; //Specifes a char string that will be used to name various files that are written during the branch and bound search
  static int silent = 1; //Suppress most output if set to a nonzero value

CCrandstate rstate;
  int seed = rand();
CCutil_sprand(seed, &rstate); //Initialize the portable random number generator
  int ncount = dist->size(); //Number of nodes (cities)
  int ecount = (ncount * (ncount - 1)) / 2; //Number of edges
  int *elist = new int[ecount * 2]; //Array giving the ends of the edges (in pairs)
  int *elen = new int[ecount]; //Array giving the weights of the edges
  int edge = 0;
  int edgeWeight = 0;
  for (int i = 0; i < ncount; i++) {
  for (int j = i + 1; j < ncount; j++) {
  if (i != j) {
elist[edge] = i;
elist[edge + 1] = j;
elen[edgeWeight] = dist->at(i)[j];
edgeWeight++;
edge = edge + 2;
}
}
}

out_tour = CC_SAFE_MALLOC (ncount, int);
name = CCtsp_problabel("_");
CCdatagroup dat;

  //Initialize a CCdatagroup
CCutil_init_datagroup (&dat);

  //Convert a matrix of edge lengths to a CCdatagroup
rval = CCutil_graph2dat_matrix (ncount, ecount, elist, elen, 1, &dat);

  //Solves the TSP over the graph specified in the datagroup
rval = CCtsp_solve_dat (ncount, &dat, in_tour, out_tour, &in_val, &optval, &success, &foundtour, name, timebound, &hit_timebound, silent, &rstate);
  for (int i = 0; i < ncount; i++) {
tour->at(i) = out_tour[i];
}

szeit = CCutil_zeit();
CC_IFFREE (elist, int);
CC_IFFREE (elen, int);
CC_IFFREE (out_tour, int);
CC_IFFREE (name, char);
}
}

int main(){

//Dataset (distance matrix of a 5 city TSP)
int ncities = 5;
int initialize[ncities][ncities]=
{
{0,3,4,2,7},//A
  {3,0,4,6,3},//B
  {4,4,0,5,8},//C
  {2,6,5,0,6},//D
  {7,3,8,6,0}//E
 };
 
 //Copying initial dataset for the distance structure
vector< vector<int> > * dist = new vector< vector<int> >( ncities, vector<int>(ncities) );
for(int i = 0; i < dist->size(); i++)
  for(int j = 0; j < dist->size(); j++)
dist->at(i)[j] = initialize[i][j];
 
 //Tour stores the optimal tour
vector<int> * tour = new vector<int>(ncities, 0);

 //Solve TSP
solving_tsp_concorde(dist,tour);

 //Print solution
 for(int i = 0; i < tour->size(); i++)
cout<<tour->at(i)<<"_";
cout << endl;
 return 0;
}

If main run with no errors, your concorde is setup!

Thanks Allyson!

Install CPLEX on linux (without administration privileges)

[update] IBM has changed the website from where CPLEX can be downloaded. It is now ibm.biz/CPLEXonAI.

Following the post on how to download CPLEX for free (academics and students), find here how to install it under linux.

Register with IBM on the hub and download CPLEX 12.9 from https://ibm.onthehub.com/
Select on the menu Data & Analytics –> Software –> CPLEX
For Linux, download option “File: IBM ILOG CPLEX Optimization Studio 12.9 for Linux x86-64 Multilingual (CNZM2ML)”

Note that to install it, you do not need administrator privileges.

bash cplex_studio129.linux-x86-64.bin

Follow on-screen instructions, and when asked about the path to install it, write

/home/username/CPLEX_Studio129

change “username” by your username on the machine

Atter installation, edit the file ~/.bashrc and add the following line at the end:

export PATH=$PATH:/home/username/CPLEX_Studio129/cplex/bin/x86-64_linux

Remember to change username.

Save the file, and execute the commands

source .bashrc
cplex

You should have loaded CPLEX now.

How to: compile C++ with Gurobi in Linux

In order to compile your C++ project with Gurobi, you first need to create the appropriate libgurobi_c++.a compatible with your g++ version. To do so, access the following directory and compile it:

cd [GRB_path]/linux64/src/build
make
The file is now created, so copy it to the lib folder:
cp libgurobi_c++.a ../../lib/
Now you can create your makefile. For example:
CCC = g++ 
FLAGS = -g -Wall -Wextra 
GRBPATH = /[full path to]/gurobi752/ 

exec: code.cpp 
     $(CCC) $(FLAGS) code.cpp -o exec -I$(GRBPATH)/linux64/include -L$(GRBPATH)/linux64/lib -lgurobi_c++ -lgurobi75 

clean: 
     rm -f code *.o *~

You might need to change spaces to tabs in the above makefile.

This was useful? Buy me a cup of coffee to help me keep this website running!



How to: handle capacity constraints for different commodities measured in different units

I have been working on a vehicle routing problem in which the truck transports several commodities, but these are measured in different units. Hence, we know the capacity of the truck for each of these commodities alone, but we don’t know how to convert them into one another so that we can load two commodities and still respect the capacity.

Continue reading How to: handle capacity constraints for different commodities measured in different units

How to: Configure IBM CPLEX with Apple Xcode

In this tutorial I will describe how to configure Apple Xcode to use IBM CPLEX with Concert technology in a C++ project. This tutorial assumes you already have CPLEX installed. If this is not the case, follow the How to Download and Install a full version of CPLEX (for Mac, obviously).

First, start Xcode and select “Create a new Xcode project”. This is also available from the File menu.

1

Continue reading How to: Configure IBM CPLEX with Apple Xcode

How to: Configure MS Visual Studio to use IBM CPLEX Concert

In this tutorial I will describe how to configure Microsoft Visual Studio Express to use IBM CPLEX with Concert technology in a C++ project. This tutorial assumes you already have CPLEX installed. If this is not the case, follow the How to Download and Install a full version of CPLEX. If you’re looking for how to use CPLEX with Apple Xcode, follow the How to configure IBM CPLEX with Apple Xcode.

First, open MS Visual Studio and start a new C++ console application. You might want to see How to Install Visual Studio and Create a C++ project.

When your project is created, right click “Project” and select “Properties”.

properties

Continue reading How to: Configure MS Visual Studio to use IBM CPLEX Concert

How to: Download and install IBM ILOG CPLEX Optimization Studio (Windows)

In this tutorial I will describe how to download and install a full version of IBM ILOG CPLEX Optimization Studio 12.6.1 (the latest version as of now – May 2015).

IBM gives scholars and university researchers free access to its software and systems. This support to our academic research is greatly appreciated. You need to register and apply for the IBM Academic Initiative program, through IBM Academic Initiative.

When you receive the confirmation of your eligibility, you can login and click on “Access IBM software and systems”, which will allow you to search for whatever IBM product you want. Here, I was looking for “CPLEX”. A list of CPLEX versions appears in the pop-up list, I clicked on CPLEX 12.6.1, the latest one.

Continue reading How to: Download and install IBM ILOG CPLEX Optimization Studio (Windows)