Disclaimer: The ISC software is distributed "as is," without warranties of any kind, either express or implied. The software is copyrighted by L. Jeff Hong, Barry L. Nelson and Jie Xu 2007. The authors grant permission for unlimited personal use of this software without fee. However, no derivative works based on the software may be prepared, including embedding any portion of it in another software product, without permission of the copyright holders.  

 

 

System environment:

 

The software has been compiled and run successfully on a Windows XP Professional with cygwin (http://cygwin.com/) providing the simulated Linux environment. The compiler was GCC (http://gcc.gnu.org/). The development platform was Eclipse (http://www.eclipse.org/).

 

ISC uses an open-source linear programming solver library called lp_solve (http://tech.groups.yahoo.com/group/lp_solve/). The version used during the development of this software was lp_solve 5.1. The user should download the proper library from the lp_solve website and set up the linker accordingly. We suggest that lp_solve 5.1 be used together with ISC because we had memory leakage problems with lp_solve 5.5. The library file liblpsolve51.a is needed for the computing platform as described earlier.

 

The software is written in standard C++. No vendor-specific C++ feature is used. In principle, any C++ compiler supporting standard C++ should be able to compile it. However, it is up to the user to figure out how to do that in their own computing environment. In the authors’ own experience, VC++ and GCC have slightly different rules and thus we provide two packages of source codes: one for VC++ and the other for GCC.

 

Below we provide brief instructions (taken from help documents from Visual Studio and Eclipse) for Visual Studio and Eclipse. What we provide is a way that works, but may not be the “best” way among many possible ways.  Other than the following descriptions, no support will be provided. 

 

  1. Visual Studio
    1. Download and save the source files (.cpp) and header files (.h) into one directory on your local machine.
    2. Obtain lp_solve from http://tech.groups.yahoo.com/group/lp_solve/. For a Visual Studio user, he/she can download lp_solve_5.1_dev.zip. Then unzip the file and copy header files into the directory containing ISC files.
    3. Create a Visual C++ project with the source files and header files downloaded.

                                                               i.      Choose File->New->Project From Existing Code.  In the wizard window, make sure you choose to create a Visual C++ project. Click next to move to the next window. Important fields in that window are

                                                             ii.      Project file location: In this field, specify in this field where you want to keep your project files using the Browse button.

                                                            iii.      Project name: give your project a name.

                                                           iv.      Make sure the box next to “Add files to the project from these folders” is checked.

                                                             v.      Use the “Add” button to add the directory containing the source files and header files. Use the “Remove” button to remove any directory that should not be selected.

                                                           vi.      Click “Next”. Make sure “Use Visual Studio” is selected, and select “Console application project”.

                                                          vii.      Click “Finish”

    1. Build the project.

                                                               i.      From lp_solve_5.1_dev.zip, copy “lpsolve51.lib” and “lpsolve51.dll” into the VC++ project directory.

                                                             ii.      Choose Project->Properties.

                                                            iii.      In the Property window, expand “Configuration Properties”, and click on Linker to expand it.

                                                           iv.      Then click on “Input”, and click on “Additional Dependencies” (the first item on the right). Type in “lpsolve51.lib”.

                                                             v.      Now build the project F7. You may see some performance warning messages. Please ignore them.

 

  1. Eclipse on a Windows machine with Cygwin. If the user has a Linux/Unix environment, the only difference is how you obtain the appropriate lp_solve library files. For Linux/Unix, things should be easier because lp_solve comes with appropriate library files. For a Windows user, he/she needs to follow step c described below.
    1. Make sure you can compile C++ with your Eclipse (CDT installed)
    2. Download and save the source files (.cpp) and header files (.h) into one directory on your local machine.
    3. Obtain lp_solve from http://tech.groups.yahoo.com/group/lp_solve/.

                                                              i.      For Windows user, download lp_solve_5.1_source.tar.gz, unzip the file, and inside the root directory “lp_solve_5.1”, find the directory “lpsolve51”. Run “cgcc.bat” under that directory. This may take a few minutes. So please be patient. After it finishes, the user should be able to see a file “liblpsolve51.a”. Copy that file, together with header files from lp_solve_5.1_dev.zip, into the directory containing ISC codes.

    1. Import source codes into Eclipse

                                                               i.      Create a new project by File->New->Project. Choose C++, and then Managed Make C++ Project. Click next. Then specify the name and location of the project. Click Next. Then make sure Project Type is “Executable”, and at least the “Debug” configuration is marked.

                                                             ii.      Choose File->Import->General->File Systems. Click Next.

                                                            iii.      In “From directory”, browse and find the directory containing source codes. Check the box besides the name of the directory to select all files. In “Into folder”, browse and select the directory where the user wants to keep the source codes. For example, we can use the default, the root directory of the project directory. Depending on your Eclipse configuration, Eclipse may begin building the project, and if so, will report a link error.

    1. Build the project

                                                               i.      Choose Project->Properties->C++ Build. On the right part of the window, choose “Tool Settings” tab, expand linker options, and click on “Libraries”. In the “Libraries(-l)” field, use the green “Add” button to add “lpsolve51”. In the “Library search path” field, use the green “Add” button to specify the directory where the file “liblpsolve51.a” is stored. If the user stores all source codes and lpsolve files in the project root directory, just click the “Workspace” button.

                                                             ii.      Eclipse will build/rebuild the project, and hopefully it is successful.

 

 

 

Using ISC to solve a discrete optimization via simulation problem:

 

Overview: ISC controls the optimization run. It assumes that there is a callable simulation that takes certain arguments and returns simulation output, as described below. ISC reports progress on a console window and saves the entire path of the optimization run to a file. Because ISC may be used for research purposes it also recognizes the existence of a function that can return the true expected value of the objective function to be paired with ISC’s estimate of it; this feature is irrelevant for practice. In ISC terminology, a “solution” is a setting of the integer decision variables.

 

ISC comes with a random number generator (Copyright:  Pierre L'Ecuyer, University of Montreal, http://www.iro.umontreal.ca/~lecuyer/myftp/papers/streams00.pdf) for its own internal algorithms. The user can use this or any other random number generator for their simulation.

 

1.      Code the simulation.

 

Include “masterheader.h”, which contains all header files used in ISC. At a minimum, the user must include “Simulator.h” and derive from the abstract base class Simulator. The user should implement two public methods:

 

double simulation(const Solution* const solution);

 

double gettruevalue(const Solution* const solution);

 

The simulation method runs the simulator to evaluate the solution represented by the pointer solution.

 

Inside of the method, the user can use two methods defined for the Solution class to recover values of the integer solution to be evaluated as illustrated below:

 

int dimension;

dimension = solution->getDimension();

const int* const x = solution->getDiscreteSolution();

 

In the code above, dimension gives the size of the integer array that contains the value of the integer solution, with x being the pointer to the array.

 

In the end, the user must return a double as the simulated objective value of the integer solution.

 

The gettruevalue method returns the true expected value of the objective function evaluated at the integer solution represented by solution if the true value is known (we used this option to study the performance of ISC), or simply the sample mean, recovered by double solution->getSampleMean() if the true objective value is unknown and estimated (the usual case). For most users, they can simply write

 

double gettruevalue(const Solution* const solution)   {return solution->getSampleMean();}

 

See ResponseSurface.h and ResponseSurface.cpp for examples of writing simple simulations.

 

Finally, include the new header file for the simulator in “masterheader.h”.

 

2.      Modify the main() function

 

Once the simulation is written, modify the main() function inside main.cpp.

 

  • Specify the path and name of the file containing control parameters for ISC. For example, in the line below, the input file named inputFileF22.txt is located in the parent directory of the directory containing the source codes.

 

const char* inputFiles = {"../inputFileF22.txt"};

 

  • Create a simulator object as showed below. Replace “ResponseSurface” with the class name for the user’s own simulator.

 

ResponseSurface sim;

 

3.      Write the input file.

 

In the directory specified in Step 2, edit a text file with the name specified in Step 2. The format of the input text file MUST strictly follow the format described here:

 

First line: output_file_name

 

Second line:

budget_for_single_ISC_run      num_of_runs_for_ISC     backtracking_test(0 no, 1 yes)   ocba_heuristic(0 no, 1 yes)    number_of_GA_generations   dominant_niche_test(0 no, 1 yes)   cleanup(0 no, 1 yes)  stocsim(0 for deterministic simulation, 1 for stochastic simulation)  global_delta    back_alpha    back_delta    local_opt_alpha  local_opt_delta   cleanup_alpha   cleanup_delta  initialNumReps   numOfCandidates   elitismOff;

 

Third line:

dimension_of_the_solution_space    num_of_constraints ;

 

Fourth line:

initial solution

 

Fifth line:

constraints row by row

 

 

An example is given below:

 

g1

1000000  10   0  1  3   0   1   1  0.1  0.05   1  0.05  0.08  0.01  0.01  5  5  0

2 4

20 20

1 0 0

-1 0 -100

0 1 0

0 -1 -100

 

a.       First line: The names of output text files containing ISC sample paths will start with the string provided by the user on the first line of this input file.

 

b.       Second line (input parameters): Because ISC was developed for research purposes, there are a large number of tunable parameters that can be set. However, there are default values for all parameters except cleanup_delta, and the default value is invoked when user specifies a negative number for any of those parameters.  The nonnegative parameter cleanup_delta is the parameter in the ISC paper. When ISC selects among the locally optimal solutions discovered during its search, it guarantees to find the best of these solutions with probability 1 – cleanup_alpha when it is at least cleanup_delta better than the other locally optimal solutions, and it will estimate the true value of the selection solution to within ± cleanup_delta with the same probability. Therefore, cleanup_delta is measured in the same units as the simulation output and should be set to a practically significant difference that it is important to detect. Smaller values of cleanup_delta will lead to longer ISC run times. 

By default, ISC will make five independent optimization runs on any problem. To change this, reset the second parameter num_of_runs_for_ISC, say to 1.

If the user knows that the simulation response is exceptionally noisy, then the second-to-last parameter, initialNumReps, which controls the initial number of replications made at a newly visited solution, can be set. However, since ISC is adaptive setting this value is not required.

A standard second line that will work for most users is

-1  1   -1  -1  -1   -1   -1   -1  -1  -1  -1  -1  -1  -1  cleanup_delta  -1  -1  -1

Users interested in customizing the other parameters should read the ISC paper at www.ISCompass.net.

 

c.       Third line:

                                                   i.      The first number is the dimension of a solution. In the example above, each solution is a vector with 2 components, i.e., .

                                                 ii.      The second number is the number of constraints of the from Ax >= b. In the example above, there are 4 such constraints.

d.      Fourth line: an initial feasible solution provided by the user. In the example above, the initial solution is (20, 20).

e.       Fifth line: Starting from the fifth line, the user provides constraints row by row.

                                                   i.      The first constraint is , that is, .

                                                 ii.      The second constraint is , that is, .

                                                iii.      The third constraint is , that is, .

                                               iv.      The second constraint is , that is, .

 

There are default values for all parameters except cleanup_delta. The default is used when user specifies a negative value for any of those parameters.

 

 

ISC Output

 

After the user has successfully added the simulator to the ISC software, and created the input text file, ISC is ready to run. ISC generates an output text file with the name output_file_name.txt containing the average of all  num_of_runs_for_ISC runs of ISC.  The first column gives the number of simulations, and the second one is the average objective value across different ISC runs. In practice only one run would be made; the capability to make multiple independent runs is for research purposes.

 

ISC also generates a sample path for each individual ISC run. The name of the file for the first run of ISC is output_file_name0.txt. The names of the other files follows this format.

 

ISC also reports progress on the console.