.. _MMW Confidence Intervals: MMW confidence intervals: ========================= If we want to assess the quality of a given candidate solution ``xhat_one`` (a first stage solution), we could try and evaluate the optimality gap, i.e. the gap between the value of the objective function at ``xhat_one`` and the value of the solution to the problem. The class ``MMWConfidenceIntervals`` computes an estimator of the optimality gap as described in [mmw1999]_ (Section 3.2) and an asymptotic confidence interval for this gap. Inclusion in generic_cylinders ------------------------------ MMW confidence intervals can be computed automatically at the end of a ``generic_cylinders`` run by supplying the following options: * ``--mmw-num-batches``: number of MMW batches (required) * ``--mmw-batch-size``: number of scenarios per batch (required) * ``--mmw-start``: first scenario number used by MMW (required) * ``--mmw-xhat-input-file-name``: path to a ``.npy`` file with the candidate solution xhat (optional). If absent, the best xhat found during the main algorithm run is used automatically. Such a file can be produced by a previous ``generic_cylinders`` run using the ``--solution-base-name`` option, which writes ``.npy``. The option ``mmw-xhat-input-file-name`` can be omitted, but all three of the other options must be present. None of the mmw options have a default value. .. note:: MMW uses the EF solver to evaluate scenario batches. By default it reuses ``--solver-name``; supply ``--EF-solver-name`` to override. .. note:: The software calls ``scenario_creator`` and ``scenario_names_creator`` from the model module. If those functions create serially correlated scenarios, they must be written so that scenarios numbered above ``--mmw-start`` are independent of those used to compute the candidate solution. Furthermore, they need to independent enough from each other to satisfy the assumptions made be Mak, Morton, and Wood. For Programmers --------------- We will document two steps in the process : finding a candidate solution ``xhat_one``, and evaluating it. Sequential sampling is also supported; see :ref:`Sequential Sampling Confidence Intervals` .. note :: At the time of this writing, the confidence interval software assumes that the scenarios are presented in random order (i.e., they are not ordered by scenario number). Finding a candidate solution ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Computing this confidence interval means that we need to find a solution to an approximate problem, and evaluate how good a solution to this approximate problem ``xhat_one`` is. In order to use MMW, ``xhat_one`` must be written using one of two functions ``ef_ROOT_nonants_npy_serializer`` or ``write_spin_the_wheel_first_stage_solution`` with an npy serializer argument. These functions write ``xhat`` for the root node of the scenario tree to a file and can be read using ``read_xhat``. When using a cylinders driver, the function ``sputils.first_stage_nonant_npy_serializer`` can be given as the ``first_stage_solution_writer`` argument to the function ``sputils.write_spin_the_wheel_first_stage_solution``. See ``examples/farmer/CI/farmer_ef.py`` for a small EF example and ``examples/uc/uc_cylinders.py`` for a hub-and-spoke example. From ``generic_cylinders.py`` the incumbent xhat from a hub-and-spoke run can be written automatically by setting ``--incumbent-on-improvement-filename-prefix``, which produces both ``.csv`` and ``.npy`` files each time a better inner bound is found. Evaluating a candidate solution ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ To evaluate a candidate solution with some scenarios, one might create a ``Xhat_Eval`` object and call its ``evaluate`` method (resp. ``evaluate_one`` for a single scenario). It takes as an argument ``xhats``, a dictionary of non-anticipative policies for all non-leaf nodes of a scenario tree. While for a 2-stage problem, ``xhats`` is just the candidate solution ``xhat_one``, for multistage problem the dictionary can be computed using the function ``walking_tree_xhats`` (resp. ``feasible_solution``). Computing a confidence interval ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The first step in computing a confidence interval is creating a ``MMWConfidenceIntervals`` object that takes as an argument an ``xhat_one`` and options. This object has a ``run`` method that returns a gap estimator and a confidence interval on the gap. Examples ^^^^^^^^ There are example scripts for sequential sampling in both ``farmer/CI`` and ``aircond``. Using stand-alone ``mmw_conf.py`` ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ (The stand-alone module is currently for use with 2-stage problem only; for multi-stage problems, instantiate an ``MMWConfidenceIntervals`` object directly) ``mmw_conf`` uses the ``MMWConfidenceIntervals`` class from ``mmw_ci`` in order to construct a confidence interval on the optimality gap of a particular candidate solution ``xhat`` of a model instance. To use the stand-alone program a model compatible with ``Amalgamator`` and ``.npy`` file with a candidate solution to an instance of the model are required. First, ensure that the model to be used is compatible with the ``Amalgamator`` class. This requires the model to have each of the following: a ``scenario_names_creator``, a ``scenario_creator``, an ``inparser_adder``, and a ``kw_creator``. See ``farmer.py`` in ``examples`` for an example of an acceptable model. Note: the `options` dictionary passed to ``kw_creator`` will have the command line arguments object in `args`, which is not required (or used) by ``amalgamator`` but is used by confidence interval codes to be able to pass problem-specific args down without knowing what they are. Once a model satisfies the requirement for amalgamator, next a ``.npy`` file should be constructed from the given model. This can be accomplished, for example, by adding the line ``sputils.ef_ROOT_nonants_npy_serializer(instance, 'xhat.npy')`` after solving the ef ``instance``. When using ``Amalgamator`` to solve the program, this can be done by adding the line ``sputils.ef_ROOT_nonants_npy_serializer(ama_object.ef, "xhat.npy")`` to your existing program (see the example in ``examples/farmer/archive/farmer.py`` for an example of this). Once this is accomplished, on the command line, run ``python -m mpisppy.confidence_intervals.mmw_conf my_model.py xhat.npy gurobi --num-scens n --alpha 0.95``. Note that ``xhat.npy`` is assumed to be in the same directory as ``my_model.py`` in this case. If the file is saved elsewhere then the corresponding path should be called on the command line. Additional solver options can be specified with the ``--solver-options`` option. This program will output a confidence interval on the gap between the solution to the EF and the optimal solution. There is an additional option, ``--with-objective-gap``, which will computes a confidence interval around the solution of the stochastic program. Since the exact value of the objective function cannot be determined, we use the realizations of the objective function at the candidate solution to construct an additional confidence interval about the mean of the realizations computed.