14
$\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.

Improve this question
$\endgroup$
9
  • 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, 2019 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, 2019 at 5:19
  • $\begingroup$ Have you ever tried the "populate_solution_pool()" or "solution.pool.get_num()" methods? $\endgroup$
    – Mohammad Namakshenas
    Jun 3, 2019 at 5:59
  • 1
    $\begingroup$ @hardmath can you be more specific about what your question is? $\endgroup$
    – LarrySnyder610
    Jun 3, 2019 at 13:19
  • 1
    $\begingroup$ @hardmath, if you are still searching for an answer concerning the search of feasible solutions for ILP problem, I invite you to take a look at this answer: or.stackexchange.com/questions/2914/… $\endgroup$
    – campioni
    Oct 30, 2019 at 15:30

3 Answers 3

Reset to default
14
$\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.

Improve this answer
$\endgroup$
3
  • $\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, 2019 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, 2019 at 13:10
  • 3
    $\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, 2019 at 23:48
14
$\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\mid y_j = 1\}$ and $T$ is the set of indices where $y_j = 0$, i.e. $T = \{t\mid 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 added is the number of feasible binaries in your problem.

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

As @Richard said, one of the possible ways to find multiple solutions is using the specific cut. There is a nice topic has been described by Erwin Kalvelagen to find all optimal LP solutions using specific cuts which implementation into GAMS software.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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