HSE 2017. Optimization

Lab 1 - Local Search Methods

Task

Implement:

• Repeated Local Search
• Iterated Local Search
• Guided Local Search

for Quadratic Assignment Problem.

Test instances

Test instances are placed in directory ./lab_1/test_instances/.

Input format

n (number of plants/locations)

Next n rows: distances matrix D

Empty row

Next n rows: flows matrix F

Output file

Filename

instancename.sol (e.g. Tai20a.sol)

Format

a1 a2 a3 ... an - solution (permutation means plant a1 is opened in location 1 and so on, separator - spacebar)

Lab 2 - Variable Neighborhood Search

Task

Implement General VNS Scheme for the Cell Formation Problem (Biclustering).

Test instances

Test instances are placed in directory ./lab_2/test_instances/

Input format

m p (number of machines and parts)

Next m rows:

m(row number) list of parts processed by machine m separated by space

e.g:

1 9 17 19 31 33

means machine 1 processes parts 9 17 19 31 33

Output format

Filename

instancename.sol (e.g. 20x20.sol)

Format

m1_clusterId m2_clusterId ... - machines to clusters mapping

p1_clusterId p2_clusterId ... - parts to clusters mapping

Running

Prerequisites

• Python 3
• Installed packages: numpy

How to run

• Go to lab_2 directory
• Run main.py with the desirable log level (default log level: INFO)

Available parameters:

• --rvns_iterations - number of RVNS iterations
• --gvns_iterations - number of GVNS iterations
• --is_iterations - number of iterations for generating initial solution
• --mode - run mode:
  • all - runs GVNS on all files in TEST_INSTANCES dir in multi-threads
  • single - runs GVNS on single file for provided number of iterations in single thread
• --filename - path to test instance for single mode
• --sf_iterations - number of iterations for instance in single mode

Example:

$ LOG_LEVEL=DEBUG python3 main.py --mode all