Introduction

Topics covered in this chapter:

Overview

The MIP solution pool (XPRSmipsolpool) stores the column solution values for multiple solutions. No slack or dual information is stored with the solutions. The solutions will usually be for MIP problems although the pool will store any arbitrary length vector of double values. Solutions can be read into the MIP solution pool by the user via the file reader routine XPRS_msp_readslxsol or from memory via the XPRS_msp_loadsol routine. Solutions can also be captured automatically from problems (XPRSprob) as they are found during a search.

Since the XPRSprob problems only store the best MIP solution the MIP solution pool is useful when the user is interested in more than one MIP solution for a problem. This can happen when there are constraints or costs not reflected in the problem that the user wants to use to select a solution from a set that have been found by the FICO Xpress Optimizer.

Once a MIP solution pool contains some solutions the user can query for the solution values and also for more abstract attributes such as the objective value of the solution with respect to a given problem. Apart from querying information for a single solution the user has various options for managing the set of stored solutions. The user can query for lists of stored solutions. They may delete solutions from the pool and output solutions to file. Also, a set of policies are available to the user for automatically handling the exclusion of solutions that are duplicated.

The following sections discuss the MIP solution pool functionality and provide some hints on usage.

Data Model

The UML diagram in Figure outlines the relationships the XPRSmipsolpool has with some other data entities.

Figure 1.1:

Starting from the bottom right the diagram shows that the XPRSmipsolpool contains 0 or more solutions. Solutions are loaded into the MIP solution pool as a dense vector of double values. Solution vectors of varying length can be stored in the same MIP solution pool so each solution stores the number of columns nCols for the solution. When solutions are loaded they are stored with a name and an ID number. The names of the stored solutions are maintained so they are unique among the current set of stored solutions. The IDs are generated using a counter starting from 1 and are therefore unique over all solutions ever to be stored in the MIP solution pool. Note that no mapping of column names to column index values is stored with the solutions. Therefore, the solutions are stored as plain vectors of implicitly indexed values. Note that although the array of solution values Vals is represented in the Solution object in the diagram as a dense array of doubles the solutions are stored in a compact form.

Moving to the top right the diagram shows that the XPRSmipsolpool references 0 or more XPRSprob problems and that an XPRSprob references at most 1 XPRSmipsolpool. This relationship is managed through the "attaching" of problems to the MIP solution pool, which we discuss in section "Attaching problems". Note that by attaching problems it is possible, for example, to automatically capture MIP solutions from the problems as they are found by the solver.

Finally, moving to the top left the diagram shows the object defining the MIP entities for a problem. Clearly the XPRSprob has one of these (even if it is empty in the case of an LP problem). The XPRSmipsolpool may capture one of these from an attached problem and uses it only to detect duplicate solutions. We discuss duplicate solutions in section "Duplicate solutions".

Once the MIP solution pool contains some solutions the user can administer the stored solutions using the following functionality:-

• Solution names can be changed using the routine XPRS_msp_setsolname.
• Solutions can be deleted from the MIP solution pool by calling XPRS_msp_delsol with the ID of the solution to delete.
• A mapping between solution name and ID is provided with the routines XPRS_msp_findsolbyname and XPRS_msp_getsolname.
• Attributes of the solutions can be accessed using routines XPRS_msp_getsol, XPRS_msp_getdblattribprobsol, XPRS_msp_getintattribprobsol, XPRS_msp_getdblattribsol, XPRS_msp_getintattribsol, XPRS_msp_getdblattribprob, XPRS_msp_getintattribprob, XPRS_msp_getdblattribprobextreme and XPRS_msp_getintattribprobextreme.
• Lists of solution IDs can be generated based on attributes of the solutions with respect to a given problem using the routine XPRS_msp_getsollist.

Solution input

Solutions can be input into the MIP solution pool from file, from memory and they can be captured automatically by the MIP solution pool directly from XPRSprob problems. The following two sections discuss this functionality.

Attaching problems

Of the more useful features of the MIP solution pool type has the ability to 'attach' XPRSprob problems to a MIP solution pool with a call to XPRS_msp_probattach. Once a problem is attached to a MIP solution pool they interact automatically with useful functions. For example, when an attached problem finds a solution it automatically stores the solution into the MIP solution pool.

As illustrated in the UML data model diagram a MIP solution pool can have one or more attached problems although a problem can only be attached to at most one MIP solution pool. The attached problems do not need to be copies of each other and they do not need to have the same number of columns.

The MIP solution pool ensures each solution is automatically loaded to all attached problems with the same number of columns as the solution. Solutions are loaded to a problem when the solver is running the problem with XPRSlpoptimize/XPRSmipoptimize. The solver can then use the loaded solutions to update the best solution and/or as a seed for heuristic searches.

Solutions loaded directly from attached problems (compared with solutions loaded by the user from file or from memory) are marked with the MSP_SOL_ISUSERSOLUTION solution attribute set to 0.

Note that problems are automatically detached from their MIP solution pool when they are destroyed (with a call to XPRSdestroyprob. A MIP solution pool automatically detaches all problems when it is destroyed (with a call to XPRS_msp_destroy).

Example:-

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

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

  XPRSinit(NULL);

  XPRScreateprob(&prob);

  XPRSreadprob(prob, sProblem, "");

  XPRS_msp_create(&msp);

  XPRS_msp_probattach(msp, prob);

  XPRSmaxim(prob, "g");

  XPRS_msp_getintattrib(msp, XPRS_MSP_SOLUTIONS, &nSols);

  if(nSols) {

    XPRS_msp_getdblattribprobextreme(msp, prob, 0, &iSolutionId, XPRS_MSP_SOLPRB_OBJ,
                                     &dObj);

    printf("Optimal Solution ID: %i\n", iSolutionId);
    printf("Optimal Objective  : %12.5f\n", dObj);

    XPRS_msp_getintattribsol(msp, iSolutionId, &iSolutionIdStatus, XPRS_MSP_SOL_COLS,
                             &nCols);

    for(i = 0; i < nCols; i++) {
      XPRS_msp_getsol(msp, iSolutionId, &iSolutionIdStatus, &dSol, i, i, NULL);
      printf("%3i = %12.5f\n", i, dSol);
    }

  }

  XPRSdestroyprob(prob);

  XPRS_msp_destroy(msp);

  XPRSfree();
}

Input from file and from memory

Solutions can be input into the MIP solution pool via the file reader routine XPRS_msp_readslxsol or from memory via the XPRS_msp_loadsol routine. When solutions are loaded in these ways the user is returned the ID(s) of the stored solutions. When solutions are input from memory via XPRS_msp_loadsol only one solution is stored per call and the user is returned the ID of the stored solution each time. When solutions are input from file via XPRS_msp_readslxsol the user is returned the first and last ID of the set of solutions that were successfully stored.

Note that solutions are not stored with a mapping of column name to solution index. Therefore, once a solution is stored the user is responsible for mapping the solution values against any column names. The indexing of the solution values is determined when the solution is loaded. When loading solutions from memory with a call to XPRS_msp_loadsol, the solution values are indexed by their position in the dense array. Similarly, solutions loaded automatically to the MIP solution pool from a problem are also indexed in this way.

When loading solutions from .slx file using XPRS_msp_readslxsol the file format has column name/solution value pairs. Solution values may be mapped to solution index using a runtime supplied name map object of type XPRSnamelist passed in the call to XPRS_msp_readslxsol. The XPRSnamelist object is typically obtained from an XPRSprob by calling XPRSgetnamelistobject on the problem to get the column name list (type 2). If the XPRSnamelist object is passed as NULL the solution values are indexed by the order they are encountered in the file.

Solutions loaded by the user from file or from memory (compared with solutions loaded directly from attached problems) are marked with the MSP_SOL_ISUSERSOLUTION solution attribute set to 1.

Solution querying

Generally, users will want to query stored solutions for their solution values. The values for solutions can be written to file or passed to the user in memory using the XPRS_msp_writeslxsol and XPRS_msp_getsol calls, respectively.

The user may be interested in abstract attributes of the solutions and the MIP solution pool itself. For example, the user may want to know the number of solutions stored in the solution pool or the number of non-zero values in a solution. They may also be interested in the objective value of a solution with respect to a given problem or they may want to know how many feasible solutions the MIP solution pool contains for a given problem. The user may perhaps also want to get the list of solutions that are feasible for a given problem. The following sections discuss the various classes of these attributes and how they are accessed.

Solution value output to file and memory

The solution values are accessed in two ways. They are written to file using the routine XPRS_msp_writeslxsol and they are retrieved in memory using the routine XPRS_msp_getsol.

The routine XPRS_msp_writeslxsol allows one or more solution to be written to file. If XPRS_msp_writeslxsol is passed with a problem (XPRSprob) pointer then the user can specify that (i) a particular solution is written out, (ii) the best solution for the problem is written out or (iii) all feasible solutions for the problem are written out. If no problem pointer is provided then the user can specify that (i) a particular solution is written out or (ii) all solutions are written out. The output .slx file has a format based on the MPS format. Each solution has a section in the .slx file starting with the string 'NAME' followed on the same line by the name of the solution. The records of each section each correspond to the solution value at the associated position in the solution array. If a problem is provided in the call then the column name is taken from the given problem for the index position and is written out followed by the solution value; otherwise column names are generated automatically based on a one-based indexing of the solution values.

The routine XPRS_msp_getsol provides in memory access to the values of a particular solution. The routine can return all solution values or solution values over a range of indices.

Attributes

A MIP solution pool and its set of stored solutions have various attributes the user can query. For example, the user can query the number of solutions stored in the solution pool or the number of non-zeros in a solution. They may also, for example, query the objective value of a solution with respect to a given problem or how many feasible solutions the MIP solution pool contains for a given problem.

There are four classes of attributes:-

• MIP solution pool attributes.
• Solution attributes.
• Solution and problem pair attributes.
• Problem attributes.

Each class relates to a different set of entities in the data model of the MIP solution pool and has a particular associated routine for accessing the attribute values. The following sections discuss the attributes.

MIP solution pool attributes

These are attributes relating to the MIP solution pool as a whole. For example, the number of solutions stored in the solution pool. These attributes are accessed using routines XPRS_msp_getintattrib and XPRS_msp_getdblattrib.

Solution attributes

These are attributes relating to a particular solution. For example, the number of non-zero values in a solution. These attributes are accessed using routines XPRS_msp_getintattribsol and XPRS_msp_getdblattribsol.

Problem attributes

These are attributes relating to the set of solutions with respect to a particular problem. For example, how many solutions the MIP solution pool contains that have the same number of columns as a given problem. These attributes are accessed using routines XPRS_msp_getintattribprob and XPRS_msp_getdblattribprob.

Solution and problem pair attributes

These are attributes relating to a solution and problem pair. For example, the objective value of a solution with respect to a given problem. These attributes are accessed using routines XPRS_msp_getintattribprobsol and XPRS_msp_getdblattribprobsol.

The attributes here are a function of a solution and problem pair. However, the user may be interested in the maximum or minimum value of an attribute over all solutions for a given problem. For example, the minimum objective value of any stored solution with respect to a given problem. The values for the attributes in this case are accessed using routines XPRS_msp_getintattribprobextreme and XPRS_msp_getdblattribprobextreme. These routines are special in that, as well as the returning attribute value, they also return the ID of a solution that achieves the attribute value.

Getting lists of solutions

Apart from just getting an attribute value for a given solution and problem (using the functions XPRS_msp_getintattribprobsol and XPRS_msp_getdblattribprobsol) the user may also be interested in how an attribute behaves over a set of solutions. For example, the user may want the objective function values for the solutions with respect to a given problem. Another example may be that the user wants the MIP infeasibilities of the solutions with respect to a given problem.

The function XPRS_msp_getsollist is used to query for a list of solutions based on an attribute. The solutions are returned as a list of solution IDs. The user can choose to rank the returned solutions by their attribute values and they may also choose to return solutions in a range of the ranked ordering of the solutions. The user can, for example, get the objective functions of the solutions ranked in ascending order so they can find the one (or more) solutions that have the minimum objective value.

Note that XPRS_msp_getsollist will only return solutions for which the attribute is relevant. For example, if the user queries on the objective function values then only feasible solutions of the problem are returned. If, for example, the users queries on MIP infeasibilities then only those solutions with any MIP infeasibilities are returned.

A function XPRS_msp_getsollist2, similar to XPRS_msp_getsollist, provides the user with additional filtering control on the returned list of solution IDs.

Control options

Duplicate solutions

Handling solution duplicates is an issue of particular relevance to the storage of solutions. Firstly, it is an issue with regards to the efficient use of the storage memory. It is also an issue with regards to how the set of stored solutions for a problem reflects the properties of the problem. For example, consider that we query, using XPRS_msp_getsollist, the solution pool looking for MIP solutions of a problem and we find 10 solutions with the same, optimal MIP objective for the problem. We may believe that the problem has multiple optimal MIP solutions. However, if these solutions are all duplicates then there is only one solution and we do not have proof the problem has multiple optimal solutions.

The MIP solution pool provides a set of policies the user can choose as an integer control parameter MSP_DUPLICATESOLUTIONSPOLICY for automatically handling the exclusion of solutions that are duplicated. These are:-

• Keep all: There is no checking for duplicate solutions.
• Exact: Solution pairs are the same if all variables have exactly the same value. Duplicates solutions are discarded.
• Exact and rounded: Solution pairs are the same if all continuous variables have exactly the same value and the discrete component of the solution matches i.e., matches within tolerance. Duplicates solutions are discarded.
• Rounded only: Solution pairs are the same if the discrete components of the solutions match. Duplicates solutions are discarded.

When the policy requires duplicate solutions be discarded the MIP solution pool compares all pairs of solutions to determine duplicates. If a solution is found to be duplicated by another solution then the solution with the larger solution id value is discarded i.e., a solution that is stored earlier is kept in place of a later, duplicate solution.

The discrete component of the solutions is determined by the MIP model of one of the 'attached' problems. The attached problem that defines the MIP model is the first problem to be attached to the MIP solution pool once the MIP model is undefined. The MIP model is undefined when the MIP solution pool is first created and after the problem currently defining the MIP model is 'detached'.

When comparing the discrete component of two solutions there are two types of tolerance used. The MIPTOL tolerance is used to define the rounded values of the variables and the FEASTOL tolerance is used to define when solution values are zero. Each solution has a control for each of these tolerances identified by MSP_SOL_MIPTOL and MSP_SOL_FEASTOL. The user can access these control values for a solution using XPRS_msp_getdblcontrolsol and XPRS_msp_setdblcontrolsol.

The discrete component of a solution (assuming it is MIP feasible with respect to the MIP model) is insensitive to small floating point variations in the values of the double solution variables e.g., a binary variable in a solution pair is compared as if the double solution value was rounded to 0 or 1. Therefore, comparing the discrete components of two solutions will match more readily than comparing the variable values with exact matches. As a result there will be no fewer solutions discarded using the discrete components comparison than there will be discarded using exact value matches (and likely there will be more solutions discarded). For this reason it is important to use care when using the policies that include discrete component comparisons since it is possible that solutions of interest may be deleted from the pool. Note that this may be a problem in the case where there is more than one MIP model for the solutions being stored in the MIP solution pool. We may delete solutions that are considered to be duplicates with regards to the MIP model used by the pool but are not considered duplicates by the other MIP model.