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 global component of the solution matches i.e., matches within tolerance. Duplicates solutions are discarded.
• Rounded only: Solution pairs are the same if the global 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 global component of the solutions is determined by the global model of one of the 'attached' problems. The attached problem that defines the global model is the first problem to be attached to the MIP solution pool once the global model is undefined. The global model is undefined when the MIP solution pool is first created and after the problem currently defining the global model is 'detached'.

When comparing the global 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 global component of a solution (assuming it is MIP feasible with respect to the global 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 global 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 global 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 global 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 global 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 global model used by the pool but are not considered duplicates by the other global model.