h1 Experiments with a Shared Memory Machine

h2 Objective
To run experiments using the open source SYMPHONY package to solve a mixed-integer programming problem on a multi-processor, shared memory machine.

h2 Description

In order to solve the large mixed-integer programmes (MIPs) used for network design, NDSG will make use of multi-processor shared-memory machines or distributed clusters of machines or both. This project is an initial discovery phase for this research and experiments with an existing MIP implementation that uses SYMPHONY as the MIP solver.

{link:SYMPHONY|https://projects.coin-or.org/SYMPHONY} is a branch-and-cut framework for solving mixed-integer programmes. It is part of the {link:COIN-OR|https://projects.coin-or.org} project. SYMPHONY has the functionality to run in parallel either on multi-processor, shared memory machines (using {link:OpenMP|https://www.openmp.org}) or a cluster of machines (using the {link:Parallel Virtual Machine - PVM|https://www.csm.ornl.gov/pvm}).

The machine used in this project was a Dell Precision 490. Its specifications are\:
* Intel(R) Xeon(R) CPU E5320 @ 1.86 Ghz 1.87Ghz (2 Processors)
* 4093 MB RAM

The MIP was generated from a Java application that linked to SYMPHONY using the Java Native Interface (JNI). The software environment was as follows\:
* Microsoft Vista 64 bit operating system
* Java Runtime Environment 1.6.0 for 64 bit
* Microsoft Visual Studio 2005 compiling for 64 bit
* SYMPHONY 5.1.3 using OpenMP

h2 Results

h3 Problem Summary

We experimented with an Automatic Test Generation problem during this project. Given a pool of possible test items we wish to select items that will provide us with our desired measure of student ability. Items may either be individual questions or part of a set of questions with additional material (a ~~testlet~~). If a question within a testlet is selected, then the additional material must also be included in the test. Constraints for the composition of the test include\:
* Minimum test time
* Maximum test time
* Desired proportions of topics
* Desired proportions of "shallow" and "deep" items

h3 Using an Interactive Solver

As a starting point I solved a sample test generation MIP (expressed as an MPS - Mathematical Programming System - file) three ways\:
* Using the commercial MIP solver CPLEX on my laptop
* Using SYMPHONY on my laptop
* Using SYMPHONY with OpenMP support on the Dell Precision 490 with all 8 processors
My laptop is an HP Compaq nx8220 with the following specifications\:
* Intel(R) Pentium(R) CPU 1.73 Ghz
* 512 MB RAM
and running Windows XP (32 bit). Both CPLEX and SYMPHONY were used as interactive solvers. I built SYMPHONY Interactive Solver with Open Support (in Visual Studio 2005 you set the flag in C++ > Language > Support OpenMP to yes) on the Dell Precision 490.

The result of the CPLEX solve is given below\:
{image:worksite:/Intmessage56424_cplex.jpg|cplex_solve.jpg}

The test generation problem is difficult for SYMPHONY to solve, so I did not expect the SYMPHONY Interactive Solver to solve the problem, rather I wanted to see how much of the branch-and-bound (BB) tree could be explored in a short time. In these tests I allowed for 5 minutes of computation.

On my laptop SYMPHONY explored just less than 600 BB tree nodes and reached a level just below the 200^^th level of the BB tree.

On the Dell Precision 490 SYMPHONY (with OpenMP and 8 processors) explored just less than 8800 BB tree nodes and reached a level just below the 600^th level of the tree.

From these initial experiments it was obvious that running SYMPHONY using OpenMP on the shared-memory Dell Precision 490 allowed for a significant increase in amount of the BB tree explored within a set time interval. However, we need to customise SYMPHONY to solve the test generation MIPs.

h3 Customising SYMPHONY

We added three customisations to SYMPHONY that helped solve the test generation problems\:
# User-defined branching - this made SYMPHONY prioritise branching on the inclusion of testlets. These variables will affect the inclusion of all the items within the testlet.
# Node heuristic - this used a simple threshold heuristic to decide if fractionally included items should be included or not. This heuristic was used at each node of the tree and would sometimes identify feasible integer solutions (especially as the level of the node in the tree increased). Testlets were included if any items in the testlet were included.
# Cut generation - SYMPHONY uses the COIN-OR {link:Cut Generator Library (CGL)|https://projects.coin-or.org/Cgl} to generate many different types of cuts for speeding up MIP solution times. The types of cuts we used for the test generation MIP were\:
* Gomory cuts
* Knapsack cuts
* Oddhole cuts
* Probing cuts
* Clique cuts
* Flow and cover cuts
* Rounding cuts
Both the mixed-integer rounding and lift-and-project cuts caused errors in SYMPHONY, most likely because the form of the test generation MIP was invalid for those cuts. For more information about cuts see the {link:CGL web page|https://projects.coin-or.org/Cgl}.

h3 Results and analysis

After customising SYMPHONY I tested the Dell Precision 490 on a larger testbed of test generation MIPs, including one (more difficult) MIP for a computer-adaptive test. The test MIPs were solved by a Java application that passed the necessary data to C++ (via the JNI) where the MIP was generated and then solved by SYMPHONY.

Since I only had access to the Dell Precision 490 for a limited period of time I could not complete all my experimentation, but I did complete a number of experiments and the results are shown in the table below.
{table}
~~Number of~~ \\ ~~Processors~~ | \\ 49081 | \\ 49082 | \\ 49083 | \\ 49084 | \\ 49085 | ~~Test~~ \\ 49086 | ~~MIPs~~ \\ 49087 | \\ 49088 | \\ 49089 | \\ 49090 | \\ 56424 | \\ CAST
8 | 546 | 13 | ~~limit~~ | 636 | ~~limit~~ | | 1019 | 731 | 6 | 11 | ~~limit~~ | ~~limit~~
7 | 991 | 18 | | ~~limit~~ | | 173 | | 727 | 6 | 11 | |
6 | 535 | 16 | | ~~limit~~ | | ~~limit~~ | | ~~limit~~ | 179 | 13 | |
5 | 885 | 20 | | 695 | | ~~limit~~ | | 313 | 385 | 25 | |
4 | 658 | 15 | | 690 | | 58 | | 902 | 193 | 12 | |
3 | 1617 | 16 | | 616 | | 153 | | | 321 | 12 | |
2 | 831 | 15 | | ~~limit~~ | | 377 | | | 370 | 13 | |
1 | | 15 | | 1173 | | 1499 | | | 364 | 72 | |
{table}

The time to find a solution tends to go up as the number of processors decreases, but this is not always the case. It is difficult to tell what the significant factors that influence the solution time are. When using different numbers of processors, the order the nodes in the BB tree are considered changes and so the order that good heuristic solutions are encountered also changes. This difference may explain why there is not a clear relationship between the solution time and the number of processors. More experimentation is necessary to determine this.

h2 Project Outcomes

One of the most important outcomes of this project was an analysis of the efficiency of the transfer of data from Java to C++ using the JNI. It was discovered that the data transfer was quite efficient, rather the generation of the test MIPs via C++ took some time to complete. The time to generate the test MIPs was reduced from 5 mins to 45 secs by parallelising sections of the code.

Another important outcome of this project was the knowledge and experience gained using SYMPHONY, customising the behaviour of SYMPHONY and using OpenMP (both with SYMPHONY and within the test generation C++ code). All of these areas of knowledge will be utilised in future work with SYMPHONY and the test generation application.

Other useful outcomes from this project include\:
# Analysis of the node heuristic and the MIP formulation for test generation
# Use of SYMPHONY in a multi-processor environment. SYMPHONY can also be compiled for a distributed environment using PVM and in the Linux OS. The ease with which SYMPHONY can be compiled for a shared-memory machine bodes well for its use with PVM and Linux, which should allow it to be deployed easily onto the Computational GRID (within BeSTGRID)

Unfortunately SYMPHONY still appears to be no match for CPLEX for the test generation MIPs. The development of a better node heuristic and advanced branching or cuts appear to be the next steps for closing the gap on CPLEX performance.

h2 Future Research

The main reason for long solution times is that the test generation problem is actually infeasible. However, this may often be the case so the formulation contains elasticity variables in non-critical constraints. By improving the node heuristic or generating better lower bounds within the tree, SYMPHONY may be able to decrease the bound gap more quickly and identify that no improvement can be made.

h2 Partial Project Blog

This is a ~~partial~~ blog from the beginning of this project. I had to rebuild much of my code on a "loaner" laptop. It has some useful descriptions of steps taken to use CPLEX (via Concert) and SYMPHONY for the test generation MIP.

h3 16-18 February 2007

# Downloaded the latest stable release of Symphony using SVN from \\ \\ https://projects.coin-or.org/svn/SYMPHONY/stable/latest \\ \\ to C:\COIN\Symphony.
# Copied the ILOG files from Cameron's laptop (C:\\\ILOG) to C:\\\ILOG on my "loaner" laptop.
# Opened the Linking.sln in the Linking directory. It assumes the location of both ILOG and Symphony are C:\\\ILOG and C:\\\COIN\SYMPHONY. \\ \\ Problem The libOsiSym project is no longer available at \\ \\ C:\\\COIN\\\SYMPHONY\\\SYMPHONY\\\Win32\\\v7\\\Osi\\\libOsiSym\\\libOsiSym.vcproj \\ \\ In fact it does not appear to exist in the latest Symphony release.
# Tried to build the solution without the libOsiSym project. Failed as jni.h is not present. Need to have jdk1.5.0_07 folder.
# Downloaded JDK 6 from the Java website. Installing the JRE 6 also.
# Set the include directories for Linking to be jdk1.6.0 instead of 1.5.0_07. Updating the JRE in WorkerProcess and Common.
# Updated WorkerProcess so that IntProgConstants has a time limit for the IPs. Give the time limit to the C++ solver in IntProgAlgorithm::createGenericTest. Use this in both Symphony and Cplex, if time limit = 0, then no time limit is assumed.
# Updated WorkerProcess so that IntProgNativeInterface gets both the time limit and the question usage values. Regenerated the JNI header file. Updated the solveMIP.def (for exporting the function svia the DLL). Made the corresponding updates in the user_problem class.
# Removed libOsiSym.lib from the Linker Additional Dependencies. Update the Debug_Symphony configuration and change the java for the Cplex configurations. Removed C:\\\COIN\\\SYMPHONY\\\SYMPHONY\\\Osi\\\src\\\OsiSym from the C/C++ Additional Include Directories.
# Added SYM_USER_APPLICATION to the preprocessing for both the Release and Debug versions of the libSymphony.vcproj.
# Need libOsiSym.vcproj, create Win32 project, made it a static library and copied the libOsiCpl.vcproj settings. Made sure to copy the differences for the Debug and Release configurations. Removed ..\\\..\\\..\\\..\\\src\\\OsiClp and replace with ..\\\..\\\..\\\..\\\SYMPHONY\\\include in C/C++ Additional Include Directories.
# Added (back) libOsiSym.lib from the Linker Additional Dependencies. Added (back) C:\\\COIN\\\SYMPHONY\\\SYMPHONY\\\Osi\\\src\\\OsiSym from the C/C++ Additional Include Directories. Again, did this for both Debug and Release configurations.
# Changed SYM_USER_APPLICATION to USE_SYM_APPLICATION in the preprocessing for both the Release and Debug versions of the libSymphony.vcproj.
# Success!! SYMPHONY is running again and I will test CPLEX on Cam's computer on Monday. Our solutions are no longer guaranteed to be optimal, but it will be interesting to compare them to the heuristic solutions. Also, I have set up the structures for CAST models to be solved with minor changes to IntProgAlgorithm.
# TO DO Can I quickly come up with a constraint branching method to quickly cut off the branch-and-bound tree in SYMPHONY? Do I need to do this or is a good solution in 3 minutes (the solver time limit) ok?
# Modified solveMIP.cpp so that getting an integer solution is acceptable (i.e., feasible is ok), even if not optimal. Checked if a solution was deemed optimal, then if the process terminated because of the time limit, checked to see if the solution was integer.
# Fixed Symphony bug (see old email below). COIN Utils bug has been fixed! \\ \\{code:none}
Hi Ted,

I have been using Symphony to write an MPS file so I can compare it
to Cplex and was having a problem with the MPS file. However, I found
that there was an error (I think) in both Symphony and the COIN library
for MPS files. I will describe the error and also how I fixed it. I have
been using Symphony downloaded from the latest directory.

1) Error in void OsiSymSolverInterface::writeMps

mps.setMpsData(colMat, getInfinity(), env_->mip->lb,
env_->mip->ub,
env_->mip->obj, env_->mip->is_int,
env_->mip->rhs,
env_->mip->rngval, colnames, rownames);

does not have the sense array. This call then uses the
CoinMpsIO::setMpsData function with rhs as the lower bound and
rngval as the upper bound. I added the sense array

mps.setMpsData(*colMat, getInfinity(), env_->mip->lb,
env_->mip->ub,
env_->mip->obj, env_->mip->is_int,
env_->mip->sense, env_->mip->rhs,
env_->mip->rngval, colnames, rownames);

and this caused an access violation in CoinMpsIO::setMpsData.

2) In both

CoinMpsIO::setMpsData(const CoinPackedMatrix& m, const double infinity,
const double collb, const double* colub,
const double* obj, const char* integrality,
const char* rowsen, const double* rowrhs,
const double* rowrng,
char const * const * const colnames,
char const * const * const rownames)
and

CoinMpsIO::setMpsData(const CoinPackedMatrix& m, const double infinity,
const double* collb, const double* colub,
const double* obj, const char* integrality,
const char* rowsen, const double* rowrhs,
const double* rowrng,
const std::vector<std::string> & colnames,
const std::vector<std::string> & rownames)

the first line stated something like

const int numrows = matrixByCol.getNumRows();

but matrixByCol had not been initialised (thus the access violation). I
replaced this line with

const int numrows = m.getNumRows();

and I can now create an MPS file that is correct.

I hope this fix is useful. If it has already been fixed or if there is a more
appropriate way to fix it please let me know.

Regards, Mike O'Sullivan
{code}
# There are still problems solving some of the test files. We could use elastic constraints. This would also give us a good way to determine which constraints are hard to satisfy, thus identifying areas where the question pool could be broadened.

h3 19 February 2007

# Implemented elastic constraints for both calculating the test time and satisfying the attribute requirements. This has lead to all test problems being solved, but in some cases the full 3 minutes are used. If we can get the solver running faster, then more nodes of the tree can be searched in this three minutes (running under debug mode does not find a solution because of all the output!).
# Changed the heuristic so the elastic variables are included.
# Currently, several fixed tests can be generated simultaneously (although this option has not been used yet). This is an effort to alleviate any later reuse problems. CAST does not support this, although we could change our MIP model to allow this (something for later).
# Changed the ILOG configurations in MSVC++ to the latest ILOG versions (9.1 for Cplex and 2.1 for Concert). Will have to update Cam's laptop?
# Can't find the cplex dll (cplex91.dll), need to put C:\\\ILOG\\\Cplex91\\\bin in to the system Path

h3 13 March 2007

# Interesting month! My laptop is finally back and mostly unharmed, I have updated Linking and WorkerProcess from the svn repositories.

-- MichaelOSullivan - 16 Dec 2010

• Intmessage56424_cplex.jpg: