Optimization
From QERM Wiki
Contents |
Evolutionary Algorithms
Evolutionary algorithms are an optimization method based on biological evolution. This included genetic algorithms, differential evolution, particle swarm optimization, and more.
Here is a table of some of the free libraries I found in my search. There is currently a Java bias in the list.
Library | Description | Language | Notes |
---|---|---|---|
EvA2 | Comprehensive heuristic optimization framework with emphasis on Evolutionary Algorithms, including simulated annealing, genetic algorithms, particle swarm optimization, cluster-based niching, and supports multi-objective optimization and finding multiple solutions | Java | Includes GUI and API, recommended |
JGAP | Genetic Algorithms and Genetic Programming framework | Java | Lots of documentation, but I had trouble getting good results with it, also has clunky API |
JCell | Framework for working mainly with cellular genetic algorithms (cGAs), but also it has implemented steady-state GAs, generational GAs, and distributed GAs | Java | |
jMetal | Metaheuristic Algorithms in Java: aimed at the development, experimentation, and study of metaheuristics for solving multi-objective optimization problems, includes many algorithms | Java | |
Opt4J | Framework currently includes a multi-objective Evolutionary Algorithm, a multi-objective Differential Evolution, a multi-objective Particle Swarm Optimizer, and a single-objective Simulated Annealing | Java |
Linear Programming
There are many commercial packages, but here is a free option:
- lp_solve: Mixed Integer Linear Programming (MILP) solver
- Probably more?
CPLEX
CPLEX is a commercial package that has a free (limited) student license. Limitation regards the number of decision variables allowed (500 max).
- CPLEX Instructions
- Set up folders to contain problems, solutions, and log files as desired, an example is provided below
- Construct your problem as a text file (.cpx), with objective, constraints, and variable definitions - see format below
- Create a batchfile to place in the same folder as cplex.exe on your computer - see format below
- Open the command prompt and type "cmd" to open the DOS command window (excuse my lack of correct terminology)
- Navigate to the director containing cplex.exe (e.g. "cd C:\Program Files\ILOG\CPLEX121\x64_win64")
- Type "cplex<batchfilename.txt" and press enter (no quotes)
- You are done! Look in C:\YourFolder\Solutions to find your results.
- Changing CPLEX parameters
- Open the command prompt and type "cmd" to open the DOS command window
- Navigate to the director containing cplex.exe (e.g. "cd C:\Program Files\ILOG\CPLEX121\x64_win64")
- Type "cplex.exe"
- At the CPLEX command prompt type "help"
- To see options for output details, for example, follow the following string of commands:
- set
- output
- writelevel: {0 = auto; 1 = all values; 2 = discrete values; 3 = non-zero values; 4 = non-zero discrete values}
- You may select one of these options for a single problem run, or you may put the sequence set output writelevel 3 in your batchfile.
- You can also run CPLEX from the cplex command prompt by following these steps and selecting appropriate commands (try starting with read, rather than set).
- Sample file setup:
- C:\Program Files\ILOG\CPLEX121\x64_win64\
- - cplex.exe <should already be in this folder>
- - batchfilename.txt
- C:\YourFolder\Problems\
- - problemformulation1.cpx
- - problemformulation2.cpx
- C:\YourFolder\Solutions\
- C:\YourFolder\Logs\
- Sample problem file format (note that lines may be no longer than 360 characters): Problem Format
- Sample batch file format (save as .txt):
set mip tolerances mipgap 0 set threads 2 set workmem 1000 set timelimit 86400 set mip strategy file 2 set emphasis mip 0 set output writelevel 3 set logfile C:\YourFolder\Logs\Max_Habitat_Quality5M.log read C:\YourFolder\Problems\Max_Habitat_Quality5M.cpx lp mipopt change problem fixed Primopt write C:\YourFolder\Solutions\Max_Habitat_Quality5M.cpx sol set logfile C:\YourFolder\Logs\Max_Habitat_Quality6M.log read C:\YourFolder\Problems\Max_Habitat_Quality6M.cpx lp mipopt change problem fixed Primopt write C:\YourFolder\Solutions\Max_Habitat_Quality6M.cpx sol
CPLEX command | Interpretation |
---|---|
set mip tolerances mipgap 0 | sets tolerance level to 0, i.e. CPLEX must find exact optimal solution |
set threads 2 | set to number of processors on computer – splits work so that CPLEX runs faster |
set workmem 1000 | not sure, probably just sets amount of memory CPLEX will use |
set timelimit 86400 | sets time limit, in seconds that CPLEX is allowed to run for. CPLEX will return the best solution it has found by the end of the run time, or return none if problem is infeasible. |
set mip strategy file 2 | not sure |
set emphasis mip 0 | not sure |
set output writelevel 3 | sets amount of detail for output file. Level 3 returns only variables with non-zero values in optimal solution. Omit line, or set to 0 to receive all output. |