Originally posted by: amindehghanian

Hello,

Is there any procedure in CPLEX to identify all basic optimal solution or all basic feasible solutions of a linear program? Something like the solution pool for MILP?

Thanks

Originally posted by: EdKlotz

There are no specific procedures to do this.    If you are using the C API, you can use the CPXpivot routine from the optimal basis to start moving to other alternate optimal solutions by pivoting non basic variables with 0 reduced costs into the basis, but I don't see how to do this in a way that guarantees you will find all optimal basic solutions.    You could also try to leverage the solution pool algorithm by creating the appropriate MILP and instructing it to enumerate all MILP feasible solutions.   I suspect this will be quite time consuming except for models of very modest size, but here's what I have in mind.   Suppose your LP is

min c'x

Ax = b

x >= 0

Solve this to optimality; let z* be the optimal objective value..   Now create the following MIP with a zero objective and the following constraints.   Here m is the number of constraints in the model, i.e. the number of rows of the A matrix.

c'x = z*

Ax = b

xj - Uj zj <= 0                                             // Uj an upper bound on xj, preferably not too bi; consider calling CPXPbasicpresolve to get these bounds..

sum zj = m

zj binary, x >= 0

Each solution of this MIP contains an optimal solution of the original LP with exactly m of the x variables allowed (but not required) to be >= 0.   So enumeration of all such feasible solutions should give you what you need.

Note that you can reduce the size of the formulation with some reduced cost fixing.   After solving the LP to optimality, fix all the variables with nonbasic reduced costs that are positive to 0 and remove them from the problem.   That reduces the number of xj - Uj zj  constraints and the number of binary variables.   But, even with that reduction, I am pessimistic that this will work well on fairly large models.   The number of optimal basic solutions for your LP can be arbitrarily large.

What exactly do you want to do with all these solutions if you get them?   Maybe there's a more efficient way to get what you need.

Do you really need all optimal BFSs, or just a bunch of them (maybe the bulk of them)? A technique I've used in the past to get a collection of optima is the following (explanation based on a minimization problem, but maximization is essentially the same):

1. solve the model and get the optimal objective value (z*), recording the solution;
2. add the constraint f(x) <= z* + tol, where f() is the original objective function, x is the vector of decision variables and tol is some small tolerance value;
3. randomly generate a coefficient vector c of the same dimension as x (I like to choose each coefficient uniformly over [-1, 1]);
4. first maximize, then minimize c'x subject to the original constraints plus the constraint added in step 2, recording the solutions;
5. repeat steps 3 and 4 until you get the urge to stop (elapsed time, failure to find a new solution, fixed iteration count, ...).

You will likely get the same solution more than once, so you need to check for duplications when recording solutions.

Originally posted by: EdKlotz

Note also that the reduced cost fixing I mentioned where you fix all nonbasic variables with unfavorable optimal basis reduced costs to 0 (or their bound if you have nonstandard bounds) will accomplish step 2 in Paul's procedure.    It has the advantage of avoiding an often dense constraint associated with the objective function, although if numerous variables have reduced costs just above or below the optimality tolerance, it can be challenging to decide which of those nonbasic variables to fix and which to leave alone.

Originally posted by: amindehghanian

Thanks for the reply!  

This could help, but I was trying to avoid an MIP formulation.

Following your question "What exactly do you want to do with all these solutions if you get them?   Maybe there's a more efficient way to get what you need.": 

I have many linear functions, and I am looking for modeling the maximum of these linear functions. However, many of the  functions are redundant in the sense that they cannot be the maximum in any point of the domain. I want to identify the non-redundant functions? 

Clearly, I prefer to solve this by LP rather than MIP if possible?

If you have N functions, you could solve N linear programs, one for each function, maximizing that function over the original domain with the added constraints that it must be >= every other function at the chosen point. If the LP is infeasible, you can discard the chosen function.

Originally posted by: amindehghanian

Thanks Paul for your reply! 

Actually, there are many lines, and I am trying to be more efficient about it rather than the enumeration. 

Originally posted by: EdKlotz

I'm a bit confused here.   First of all, what exactly do you mean by maximum of these linear functions?   Are you looking for the one linear function that attains the highest single value among all points in your feasible region, or are your looking for the linear function that is maximal relative to all the others for the highest percentage of points in the domain?   Or some other notion of maximality?    Second, given what you are trying to find, what do you mean by identifying all optimal basic solutions?   Optimal basic solutions relative to which of your N linear functions?   I don't see how having all optimal basic solutions to any one of your objective gets you much in terms of concluding anything about the maximality (whatever your specific criterion for maximality is) of all N of these functions.

Originally posted by: amindehghanian

Sorry for the confusion!

For your first question, I am looking to find the maximum function over a specific domain. So, at any point, one of those linear functions may attain the maximum value. As there are many linear functions, some of them are redundant in the sense that they never attain the maximum value at any point of the domain. So, they can be discarded for further processing. I hope this clarifies it!

Regarding your second question, I will briefly say that finding all the BFSs of  a certain polytope is a reformulation of the above problem. Providing the reason behind this will be very long.

Thanks

Originally posted by: EdKlotz

I'm still confused.   As you say, at any point, one function may attain the maximum value (although actually more than one could attain the same value).   But different functions can attain the maximum at different points in the domain.   So while I agree that you may have functions that never attain the maximum, I still don't understand what you mean when you apparently refer to a maximum single function over a specified domain.   Or do you break up the original domain into subsets on which a single function is a maximum over that subset?

Suppose we have a simple example.   Let the domain of x be [0,10] and let f1(x) = 5 - 1/2 x, f2(x) = 1/2 x and f3(x) = 1 + 1/5 x.    If you draw this, f1(x) is the maximum function over [0,5], f2(x) is the maximum over [5,10] and f3(x) never attains the maximum, but takes on values > f1(x) in part of the domain, and takes on values > f2(x) in other parts of the domain.     So what is your maximum function in this simple example?

Regarding discarding linear functions for processing, you can do some preprocessing by looking for functions that are completely dominated by some other function, i.e. if one function has all coefficients < another function, it is dominated and can be discarded from consideration.  Then after that preprocessing, you could apply Paul's linear programming approach to hopefully fewer than N functions.   You could probably construct some sort of hashing function to avoid having to compare N*(N-1) pairs of functions to look for dominated ones.  

Note that this type of domination does not exist in the simple example I described.   In that simple case where the domain involves simple bound constraints, perhaps you could do something by looking at the infimum and supremum values for each linear constraint.   But in the more general case where the domain is described by full blown linear constraints rather than simple bound constraints, I'm not sure you can do anything without solving LPs, which means you might as well just go with Paul's approach.   But maybe there's another way.

Ed:

I think the idea is that f(x) = max {f_i(x) : i = 1, 2, ..., whatever}. So in your small example, f(x) is the pwl function with critical (?) points (0, 5), (5, 2.5) and (10, 5). If you jack up the dimension of the space (and the number of functions), it's plausible that one might represent this not by some piecewise linear surface but by a numerical function that, given x, evaluates all the candidates and chooses a winner. If you're going to do this often enough, and if many of the functions are never going to be the winner, it makes sense to look for a way to weed them out before going live ... IF you can weed them out "cheaply" (and safely).

I was initially confused about this too ... and still am, if that's the wrong interpretation. :-)

Paul

Originally posted by: EdKlotz

Paul,

         Given that this question initially involved enumerating a set of basic feasible solutions, your interpretation sounds quite plausible.   Returning to my simple example, if you then consider the LP

min t

s.t.

t >= 5 - x

t >= 1/2 x

t >= 1 + 1/5 x

0 <= x <= 10

The basic feasible solutions are precisely the critical points (0, 5), (5, 2.5) and (10, 5)  that you mentioned.  So enumerating those BFSs (different from BFFs) would have some value in terms of providing info about which function is the maximum at any given point, and also which functions never attain a maximum. 

I think will extend to higher dimension but I haven't checked carefully.

Ed,

I think it will generalize -- but the number of BFSs could be pretty large (much larger than the number of my BFFs), and finding all of them might be tricky, and maybe more work than just solving one LP per original function.

Paul

Originally posted by: amindehghanian

Thanks Paul! Yes, this is exactly what I meant.

Originally posted by: T_O

Ed,

I think this domination rule is only true for positive domains.

E.g. 2*x is not dominated by 3*x on [-2,-1].

Best regards.
Thomas

Originally posted by: EdKlotz

Yes, that is correct; I was assuming standard variables bounds of [0, +inf) as in my initial post on this thread, but should have stated that explicitly.