DM841 - Discrete Optimization
Exercise Sheet, Autumn 2016 [pdf format]

This sheet will guide you through the example of a local search algorithm for the Queens problem using the framework EasyLocal. In your assignments it is possible to avoid using EasyLocal and develop everything by your own, if you feel overwhelmed by EasyLocal. In this case it is still recommendable to follow the design of EasyLocal and use as a starting point the code in Queens/ that we commented in class.

Preparation

  1. Revise the slides on “EasyLocal” to gain a view over the elements of EasyLocal.
  2. Download and Install EasyLocal following the instructions in link [S4].
  3. Download and uncompress the archive Queens.tgz. This is a worked out example.
  4. Make sure you have a working installation of EasyLocal and of the example. To test that everything is working as it should, go in Queens/, compile the project and run it with: 
    nqueens --main::instance queens8.txt

    Try 

    nqueens --help

    to see a list of command line parameters (more on this below).

  5. Take vision of the C++ documentation “C++ reference” and of the EasyLocal documentation (last link down the page from [S4]). You may need this later.
  6. Choose an IDE (Integrated development environment) like Visual Code, Eclipse, Xcode or Visual C++ or simply your favorite text editor. An IDE can be helpful when your source code is in several files. Eclipse could be a good choice as it works across all environments (Linux/MacOs/Windows), and hence you could receive help from your peers and from the teacher. Eclipse IDE for C/C++ Developers is the version you should install. Once installed you should create a C++ New Project that has as location the root directory of the Queens example you downloaded from the course page.
  7. Look at the code of the Queens example and try to understand what it does.

Workflow

The following is a TODO list to start developing your local search program for a new program following the Queens example.

  1. Define the Input class (in input.hh):
  2. Define State class (in basics.hh and basics.cc)
  3. Define Output class (in input.hh)::
  4. Define Move class (in basics.hh):
  5. Define StateManager class (in helpers.hh and helpers.cc)
  6. Define OutputManager class:
    Determines how a state is passed to and from an Output object. It is needed to print solutions and to get solutions from outside the program.
  7. Define NeighborhoodExplorer class:
  8. Define CostComponent classes (one for each cost component):
  9. Define DeltaCostComponent classes (one for each cost component):
  10. Implement a search engine. Most likely you will have to inherit from LocalSearch. The main local search procedure is defined in SearchEngine::Go(). See Figure 1. The class LocalSearch inherits from SearchEngine and adds a move and a list of observer.
        template <class Input, class State, typename CFtype>
        CostStructure<CFtype> SearchEngine<Input, State, CFtype>::Go(State& s) throw (ParameterNotSet, IncorrectParameterValue)
        {
          InitializeRun(s);
          while (!MaxEvaluationsExpired() && !StopCriterion() && !LowerBoundReached() && !this->TimeoutExpired())
          {
            PrepareIteration();
            try
            {
              SelectMove();
              if (AcceptableMoveFound())
              {
                PrepareMove();
                MakeMove();
                CompleteMove();
                UpdateBestState();
              }
            }
            catch (EmptyNeighborhood)
            {
              break;
            }
            CompleteIteration();
          }

          return TerminateRun(s);
        }
    Figure 1:
  11. Write the main() function including ( main.cc):
  12. Parameters. The search engine class SearchEngine and the solver class AbstractLocalSearch have their own parameters. For example in the definition of the class SearchEngine we find:
    Parameter<unsigned long int> max_evaluations;
    void RegisterParameters() {
       max_evaluations("max_evaluations", "Maximum total number of cost function evaluations allowed", this->parameters);
    }
    These parameters are inherited by all derived classes, hence by FirstImprovement too. If you need to add parameters to your local search then you have to add them in the definition of your class and register them via a new function defined by you in a similar way as in the RegisterParameters function shown above.
  13. Working with Parameters: Every class that inherits from Parametrized has an object parameters and can print all registered parameters with the function:
    Print( std::ostream& os = std::cout);

    Hence you can print from main.cc with:

    qsd.Print();

    Each parameter can be printed with:

    par.Write();

    To read parameters from a file, from main.cc:

    SAT_solver.ReadParameters(std::istream& is = std::cin, std::ostream& os = std::cout);

    this function will read the parameters from a file stream that you previously open and print what has been read in the stdout.

    This function is also implemented in Parametrized and you can read its definition in the EasyLocal framework under utils/parameter.hh

    In the file one can write parameters as:

    prob 0.5

    then the parameter "prob" is read and set.

  14. Those that are not using EasyLocal can find an implementation of a chronometer and a random generator under Resources/NoEasyLocal.
  15. Scripts in Bash, Python and PHP for launching a batch of jobs, ie, execution of your local search program on different instances, are available at Resources/Scripts.

Exercise

Starting from the example handed out, implement the following:

  1. a variant of FirstImprovement that go beyond the local minimum where this algorithm gets currently trapped.
  2. a best improvement local search that ends in a local optimum
  3. a one exchange neighborhood
  4. the min conflict heuristic from the last slide of lecture 3.