Originally posted by: kc78

Hi

I would like to generate say 1000 possible feasible/optimal solutions for an underdetermined MILP, which can be using the same set of binary variables but with different values for the non-binary variables. In a sense, it would be like sampling of the feasible solution space.

I tried to use the solution pool function and it solved the problem once and then it was infeasible to generate any other solution. Is it because there are no other set of values for the binary variables and so the solver doesnt return any other feasible solutions?

Thank you!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

As you have learned, CPLEX's solution pool feature is not designed to help very much with your problem. CPLEX will return only one solution vector for any given combination of the integer variables - potentially there will be an infinite number of combinations for the continuous variables but CPLEX delivers only one.

I think it would be very difficult to design a general algorithm that would sample the feasible space the way you want it to. My first thought was that maybe you could discretize your continuous variables in some way, so that the solution pool feature could be invoked after all, but I suspect that CPLEX might still return a highly clustered set of solutions. The solution pool offers diversity filters that might help in this regard, but unless you could devote essentially infinite time to one problem, there might not be very good guarantees that a sufficient sampling of the feasible space had been completed.

Maybe someone else will have a clever idea to share.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I don't have any first hand experience with the solution pool feature, but AFAIK it does not continue the search beyond optimality. So if your problem is too easy, and the first integer-feasible solution meets the optimality criteria, I think CPLEX stops. You might look at the populate feature for the solution pool and see if you can use that to your advantage. Another possibility is to use an incumbent callback that records and then rejects incumbents, which artificially forces the search to continue.

As John Gregory points out in his reply, the solution pool feature will not give you multiple solutions with the same integer variable values but different continuous variable values. If you believe there are multiple "completions" of an integer solution, what you can do is create an LP subproblem in which the integer variables are fixed at the values from the integer-feasible solution and the original objective function is constrained equal to the optimal value (or within some distance of the optimal value if you're willing to accept suboptimal solutions in your sample). Then optimize randomly generated objective functions using the constraints of that subproblem until you've got a large enough sample of solutions or you find the same solutions repeating too often. (The difficulty with this approach is that in general you will not get all extreme points of the subproblem feasible region, and there is no way of knowing that you have identified all of them, so you're at a guess when to quit sampling.

I believe there are programs available that enumerate all vertices of a convex polyhedron. So you could set up the LP I just described, feed the constraints to such a program, and get a comprehensive list of all optimal/near optimal extreme point solutions given the frozen values of the integer variables.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Just to elaborate on a point Paul brought up: the Solution Pool feature should be thought of mainly as a receptacle for solutions found, and operates essentially the same way whether the standard MIP optimizer call or the Populate call is used, with feasible solutions encountered along the way being deposited in the solution pool. The MIP optimizer does indeed stop when optimality is proved, and on typical models a few solutions will be contained in the pool at the end, but it could be only one, the optimum. By contrast, the Populate call explores but does not fathom nodes in the tree and, depending on the "pool intensity" parameter setting, it can produce an exhaustive list of all feasible integer solutions, as well as less compute-intensive levels that still deliver more solutions than the MIP optimizer. (Of course on any MIP model of substance, the exhaustive list will be too lengthy to be practical to produce.) The pool intensity parameter affects the MIP optimizer too, but to not as extreme a degree.

I'll leave it to the original poster to determine whether the suggestion to compute all vertices, or use quasi-randomly generate objective functions (which likely bring you to vertices as well), will sufficiently mirror the idea of sampling the feasible solutions. If interior solutions are needed, I suppose a collection of these vertices could be used in linear combinations in quasi-random fashion to get inside the interior. Sounds messy and prone to unintended consequences, to me - not truly a random sampling of anything. But, it's a bit random what people sometimes mean by sampling. :)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: kc78

Thank you all for the useful suggestions!
#CPLEXOptimizers
#DecisionOptimization