Introduction

Topics covered in this chapter:

Overview

The MIP solution enumerator (XPRSmipsolenum) runs a customized MIP search on a user provided problem (XPRSprob). The search is customized such that nodes are not cut-off by bounding and integer solution nodes are branched. The MIP solution enumerator marshals the solutions found to storage in a user provided MIP solution pool (XPRSmipsolpool).

In general the MIP solution enumerator is useful for generating a set of solutions for a problem. In particular, the MIP solution enumerator can be used to generate the n-best solutions to a problem. The user will typically be interested in such a set when there are constraints and/or costs not reflected in the problem and the user wants a set of solutions from which a final solution can be selected that best meets the external constraints and objective.

Applications: N-Best Solutions Example

A typical use of the MIP solution enumerator is to generate the set of n-best solutions. The following example shows how this can be done:-

#include <stdio.h>
#include "xprs.h"
#include "xprs_mse_defaulthandler.h"

int main(int argc, char **argv)
{
  XPRSprob prob;
  XPRSmipsolpool msp;
  XPRSmipsolenum mse;
  int nMaxSols;
  int i, j, nSols, nCols, iSolutionId, iSolutionIdStatus;
  double dObj, dSol;
  int iPresolveOps;
  const char *sProblem = argv[1];

  XPRSinit(NULL);
  XPRScreateprob(&prob);
  XPRSreadprob(prob, sProblem, "");

  XPRS_msp_create(&msp);

  XPRS_mse_create(&mse);

  XPRSgetintattrib(prob, XPRS_COLS, &nCols);

  /* Disable heuristics to avoid duplicate solutions being stored */
  XPRSsetintcontrol(prob, XPRS_HEUREMPHASIS, 0);

  XPRSgetintcontrol(prob, XPRS_PRESOLVEOPS, &iPresolveOps);
  iPresolveOps &= ~(1 << 3); /* Disable dual reduction operations */
  iPresolveOps &= ~(1 << 5); /* Disable duplicate column removal  */
  XPRSsetintcontrol(prob, XPRS_PRESOLVEOPS, iPresolveOps);

  /* Run the enumeration */
  nMaxSols = 10;
  XPRS_mse_maxim(mse, prob, msp, XPRS_mse_defaulthandler, NULL, &nMaxSols);

  /* Print out the solutions found */
  XPRS_mse_getintattrib(mse, XPRS_MSE_SOLUTIONS, &nSols);
  for(i = 1; i <= nSols; i++) {
    XPRS_mse_getsollist(mse, XPRS_MSE_METRIC_MIPOBJECT, i, i, &iSolutionId, NULL, NULL);
    XPRS_mse_getsolmetric(mse, iSolutionId, &iSolutionIdStatus, XPRS_MSE_METRIC_MIPOBJECT, &dObj);
    printf("--------\n%3i = %12.5f\n", i, dObj);
    for(j = 0; j < nCols; j++) {
      XPRS_msp_getsol(msp, iSolutionId, &iSolutionIdStatus, &dSol, j, j, NULL);
      printf("%3i = %12.5f\n", j, dSol);
    }
  }

  XPRS_msp_destroy(msp);
  XPRSdestroyprob(prob);
  XPRS_mse_destroy(mse);

  XPRSfree();
}

In the example we use the XPRS_mse_defaulthandler function to manage the storage of at most nMaxSols ( = 10) solutions. The code for the XPRS_mse_defaulthandler callback is provided in the FICO Xpress Optimizer. Using the default control settings when a solution is found and there are nMaxSols ( = 10) solutions stored the XPRS_mse_defaulthandler callback will either reject the current solution or delete the worst existing solution depending on their objective values (when there is a tie the current solution is rejected). In this way the MIP solution enumerator will generate the set of n-best solutions.

It is important to note that duplicate solutions can potentially be stored in the cases where the MIP solution pool contains initial solutions prior to the enumeration run or if heuristics are activated in the XPRSprob. In the example we have disabled heuristics and the MIP solution pool does not contain any solutions prior to the enumeration run so there is no need to check for duplicates. The management of duplicate solutions is left to the MIP solution pool functionality which is discussed in Duplicate Solutions.

It is also important to note that it is sometimes necessary to disable certain FICO Xpress Optimizer presolve operations (i.e., setting the integer control PRESOLVEOPS in the example) to avoid spurious deletion of solutions from the enumeration search space. This is discussed in the following section Presolve considerations.

In the event that initial solutions are contained in the MIP solution pool prior to the enumeration run the MIP solution enumerator will load the set of feasible solutions (with the same number of columns as the XPRSprob) from the initial set of solutions as if they were found during the MIP search on the XPRSprob. Note that new versions of these solutions are created and the original versions are deleted from the MIP solution pool.

Once the enumeration run terminates the example demonstrates simple retrieval of the solution information. Note that the solution values are stored in the MIP solution pool and the metric information for the solutions is stored in the MIP solution enumerator.

Presolve considerations

The default control settings of the FICO Xpress Optimizer presolver assume that the user is satisfied if the MIP search finds a single solution with the best objective. The choice of the default presolve settings attempts to improve the efficiency of this type of search by cutting off MIP solutions from the feasible region that are either degenerate (i.e., that have equivalent representations with different feasible values of the variables) or dominated (i.e., that can be deduced to be worse than solutions contained in the remaining feasible region) or symmetric to another solution. The user must take care to disable these default presolve operations when solutions may be removed from the enumeration search space that are of interest. Also, the user should be aware that disabling these presolve operations can significantly increase the enumeration runtime.

Presolve operations removing dominated MIP solutions are collectively referred to as dual reduction operations. To disable duplicate column detection the user must unset bit 5 of the integer control PRESOLVEOPS. To disable all dual reduction operations the user must unset bit 3 of PRESOLVEOPS. See the Applications: N-Best Solutions Example for an example of how to unset these bits.

To disable FICO Xpress Optimizer from removing symmetric solutions, set the SYMMETRY control to 0.

Basic customization

By customizing the controls for the XPRS_mse_defaulthandler callback (i.e., setting MSE_CALLBACKCULLSOLS_MIPOBJECT and/or MSE_CALLBACKCULLSOLS_DIVERSITY) the user can modify the behavior of the callback when the number of solutions exceeds the maximum. The user can delete p solutions based on the MIP objective values and then delete q of the remaining nMaxSols - p solutions based on the diversity metric (see below). The current solution will be rejected if it is no better than any of the solutions that were deleted. In this way the user has simple control of how the solution set is generated.

In addition to the MIP objective the MIP solution enumerator provides a metric for solutions based on the 'diversity' of the solution with respect to the other stored solutions. The diversity metric for a solution is the sum of difference metrics between the solution and the other stored solutions. By default the difference value between two solutions is calculated by the MIP solution enumerator using a simple difference metric that considers only the MIP entities in the solution. Note that for the MIP solution enumerator to calculate the diversity metrics a problem needs to be attached to the MIP solution pool (see 'Duplicate solutions'). This is because the discrete structure of the solution variables is required for the difference metric calculation. The user will typically attach to the MIP solution pool the XPRSprob to be used to run the enumeration. Finally, note that the user can provide their own difference metric calculation for solution pairs in a callback defined with a call to XPRS_mse_setcbgetsolutiondiff (in this case there does not need to be a problem attached to the MIP solution pool).

Advanced customization

By providing a customized version of the XPRS_mse_defaulthandler the user can define a modified objective value for solutions. Typically this value reflects the 'true' objective of the solution in cases where the MIP objective does not completely model the user's problem. The modified objective value is stored with the solution and can be used to obtain a ranked order of solutions in the case where the user wishes to delete solutions based on this metric (see XPRS_mse_getcullchoice). Also with a customized callback the user is able to arbitrarily accept or reject the current solution. Typically the user will want to do this in cases where the constraints and/or objective of the MIP problem do not completely model the user's problem.

From the customized XPRS_mse_defaulthandler callback the user is able to set a return value that causes the MIP solution enumerator to set the cut-off for the search to the worst MIP objective of the active solutions. This can be useful to improve the run time of the enumeration. Note that the default n-best search uses this to improve the enumeration performance.

Data Model

The following UML diagram outlines the relationships the XPRSmipsolenum has with some other data entities.

Figure 5.1:

Starting from the top left the diagram shows the XPRSprob referenced by the XPRSmipsolenum in the top middle. The XPRSmipsolenum references the XPRSprob only for the duration of the enumeration-run routines XPRS_mse_minim, XPRS_mse_maxim and XPRS_mse_opt. The XPRSmipsolenum sets certain controls on the XPRSprob, registers an internal callback to receive solutions found during the enumeration and calls the relevant optimization function to execute the enumeration.

Moving to the top right the diagram shows the XPRSmipsolpool referenced by the XPRSmipsolenum. The XPRSmipsolenum references the XPRSmipsolpool only for the duration of the enumeration-run routines (in the same way as the XPRSprob).

While running the enumeration the XPRSmipsolenum maintains storage of additional information for each solution found that cannot be stored by the XPRSmipsolpool. The additional information is the MIP objective value (MIPObject) of the solution, any user-defined objective function value (ModObject) for the solution and a diversity-metric (Diversity) for the solution that measures how different the solution is with respect to the other solutions in storage. As indicated by the dashed line in the diagram, the solution ID is used to link the information stored separately in the XPRSmipsolenum and the XPRSmipsolpool.

Since a parallel storage of solution information is required the XPRSmipsolenum marshals the storage of solutions to the XPRSmipsolpool. To do this the XPRSmipsolenum registers an internal callback with the XPRSmipsolpool to track when solutions are deleted by the user from the XPRSmipsolpool. It is also necessary that the XPRSmipsolenum loads the solutions found during the enumeration directly into the XPRSmipsolpool overriding the automatic loading of solutions from the XPRSprob to XPRSmipsolpool in the situation where the user has attached the XPRSprob to the XPRSmipsolpool prior to the enumeration run.

Once the enumeration run terminates the MIP solutions are stored in the XPRSmipsolpool and the additional information for the solutions is stored in the XPRSmipsolenum. At this point the solution information is linked only by the solution ID.