9
$\begingroup$

Some problems call for a count of the number of integer "lattice" points contained in a feasible region (rather than for locating the minimum or maximum objective function value in that region). See for example the SO Question "Counting solutions to linear inequalities" or this previous Math.SE Question "Uniform lattice sample inside a particular convex polytope".

As a general proposition this counting is difficult (NP-hard as the corresponding decision problem is NP-complete), but it is sometimes possible to count by writing custom code, as I did for this previous SciComp.SE Question "Python solvers for mixed-integer nonlinear constrained optimization".

What solvers or software packages can be used for the purpose of counting (or estimating the count of) feasible integer solutions? My understanding is that the MILP solver CPLEX has an option to collect a "solution pool" of the integer portion of feasible points it encounters in a run.

I'd also appreciate a basic example of using this feature to count or estimate the number of feasible points of an ILP. Links to such examples would be more helpful if accompanied by a discussion of the limitations or difficulties of that task. As a comment points out, CPLEX will only report the feasible points it locates during a search for optimizing an objective function, but the number of feasible points is independent of the objective function. Therefore the sampling in such solution pools is biased and incomplete. Nevertheless it might be possible to collect a representative sample by varying the objective function.

It might also be that better tools are available for the purpose, as another comment suggests.

$\endgroup$
  • 2
    $\begingroup$ I don't believe the solution pool is helpful for estimating the number of feasible integer solutions, if that's your question. It collects (near-)optimal found during the search, but in general this will be a tiny fraction of all solutions, and not a good estimator for the total number. $\endgroup$ – Marcus Ritt Jun 3 at 5:08
  • $\begingroup$ @MarcusRitt: Thanks for this observation. While a fixed objective function will produce a limited (and biased) sample of feasible points, the possibility of varying objective functions might help overcome that limitation. $\endgroup$ – hardmath Jun 3 at 5:19
  • $\begingroup$ Have you ever tried the "populate_solution_pool()" or "solution.pool.get_num()" methods? $\endgroup$ – Moh_NA_X Jun 3 at 5:59
  • 1
    $\begingroup$ @hardmath can you be more specific about what your question is? $\endgroup$ – LarrySnyder610 Jun 3 at 13:19
  • $\begingroup$ I edited slightly to highlight what your two specific questions are. See if you agree with the edits and if not, revise as you like. $\endgroup$ – LarrySnyder610 Jun 3 at 20:17
10
$\begingroup$

@prubin has this neat (possibly slightly dated) series of blog posts, Finding All Solutions (or Not), Finding "All" MIP Optima: The CPLEX Solution Pool Solution Pool: "All" Is Not All, which deals with the hassle of collection all MIP solutions in CPLEX's solution pool.

While this doesn't exactly answer your question, it still might provide helpful insights where to start -- and which problems to expect.

$\endgroup$
  • $\begingroup$ Thanks for your response. I saw that the one blog post I linked in the Question was six years old, but the additional information should be relevant. $\endgroup$ – hardmath Jun 3 at 12:30
  • $\begingroup$ @hardmath Upps ...completely missed the fact that you already linked to the 2nd blog post; my bad. $\endgroup$ – fbahr Jun 3 at 13:10
  • 2
    $\begingroup$ I don't think anything has changed since I did those posts (unless there's a new parameter related to the pool in CPLEX; I'm not aware of one). Finding all feasible solutions is equivalent to finding all optimal solutions when the objective function is a constant. $\endgroup$ – prubin Jun 5 at 23:48
10
$\begingroup$

The only way (to my knowledge) to get all feasible points for the binary components of a MIP is as follows:

  1. Solve the problem. Let $y$ denote the optimal solution

  2. Add the following integer cut to your model: \begin{equation} \sum_{j\in J}y_j - \sum_{t\in T}y_t \leq |J|-1 \end{equation} where $J$ is the set of indices where $y_j = 1$, i.e. $J = \{j|y_j = 1\}$ and $T$ is the set of indices where $y_j = 0$, i.e. $T = \{t|y_t = 0\}$. This will exclude the found solution from the MIP.

  3. Resolve the model, and add another integer cut.

  4. Repeat until the model becomes infeasible. The number of integer cuts addded is the number of feasible binaries in your problem.

$\endgroup$
  • 1
    $\begingroup$ In SCIP, there is a special command to run a version of this algorithm for you: counter. $\endgroup$ – Robert Schwarz Jun 3 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.