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_HEURSTRATEGY, 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.