## 1 Introduction
### Problem Motivation  
This project was primarily motivated by a problem in cancer genomics for which we implemented the software MadHitter, version 1 [1], which uses Gurobi or SCIP to solve variations of the classical combinatorial optimization problem _minimum hitting set_[2]. Taking as input single-cell mRNA data from patient tumors, MadHitter finds an optimal combination of target genes to treat either an individual patient or a cohort of multiple patients, and suggests different genes and their encoded proteins as future targets for cancer drug development. For the modeling in MadHitter, we treat each targetable gene equivalently, such that any solution targeting \(g\) genes is advantageous to any solution targeting \(g+1\) genes, regardless of what may be known about the genes. MadHitter does not choose between two optimal gene sets of the same minimum size. Clinically, most genes cannot be targeted by existing drugs, suggesting that solutions with more \"druggable\" genes are preferable. Moreover, biochemists and drug developers have expert knowledge as to which genes will be easier to target chemically with future drugs. Therefore, they are interested in identifying multiple optimal solutions to choose a solution containing genes that may be targeted for the treatment of future patients. Gurobi offers a solution pool method that finds multiple optimal solutions of a linear program. Technically, if model stores the Gurobi problem instance, then one specifies the intent to collect multiple solutions with a command such as:  
model.setParam(GRB.param.PoolSolutions, num_solutions)  
and then one retrieves the \(i^{th}\) solution with a command such as:  
select_solution(model, i). We tested the solution pool method within MadHitter, but regrettably found that many solutions were frequently missed when sampling 50-100 optimal solutions. Many of the optima returned were 'copies' of the same optimal hitting sets, differing only in the values of variables that appear exclusively in the model constraints. However, only solutions that differ in the objective function variable values are of interest for MadHitter. Indeed, in most other MIP applications, only the variables in the objective function have practical importance for decision making. Variables that appear only in the constraints are typically needed to formulate the problem rigorously and precisely as an MIP. If one is interested in distinguishing solutions that differ in constraint-only variables, one can add the constraint-only variables to the objective function multiplied by tiny coefficients, so that they are effectively lower-order terms. The difficulties in using solution pool motivated us to design and implement a novel method, MORSE, to generate distinct optimal solutions. There are two available methods that aim to find all optimal solutions of integer programs. Both methods modify the use of the branch-and-bound tree in finding a single optimal solution. The unrestricted subtree method is implemented via the functions SCPcount and SCPgetNCountedSols in SCIP [3]; the first function finds the distinct solutions, and the second function returns the number of distinct solutions found. The SCP documentation provides more information on these functions. The one-tree method is implemented via the function populate in CPLEX [4]. Associated with the function is a parameter denoted by either CPX_PARAM_MIP_POOL_CAPACITY, SolnPoolCapacity, or PopulateLim (depending on the programming language interface) that sets an upper bound on the number of solutions stored. The function populate allows the user to specify that suboptimal solutions within some percentage of the optimal objective function value should also be returned. For more information, see the CPLEX documentation. Both methods are inherently sequential, and the solutions are unavailable until the respective functions have fully completed their execution. Both methods are yet to be implemented in Gurobi, as indicated by the current Gurobi documentation (accessed on 31 December 2024).