 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Math Forum / Mathematics / Operations Research / July 2009Column generation and analysis of the model
Hello, I have an LP problem which is solved using the column generation method. This results in the optimal master problem (RMP): min F(x) s.t. A x >= b and the corresponding objective value. Assume that the objective value is, say, 1 while the ultimate goal is to get it down to, say, 0. I'm interested in *minimal* sets of constraints (linear inequalities) which prevent the objective value from being zero (or less). Naively I can get at least one such set by repeatedly removing inequalities from RMP and reoptimizing. Unfortunately I'd have to repeat the column generation phase each time I drop a constraint (am I right on that?) which is unacceptable. I'm wondering if it would be possible to exploit some sensitivity data returned by an LP solver in order to determine either: 1) constraints which are irrelevant (inactive) so that can be dropped w/o reoptimizing or 2) constraints which are relevant (active) so that if I drop them the objective value will get below the current value of 1. If I didn't use column generation this would be fairly trivial. I'd simply ask for constraints' dual values and dropped all those with duals = 0 (am I right)? However, if I do that on RMP it seems that I may lose some of the relevant constraints. I guess this is so because the RMP is only optimal for the given fixed set of constraints. I might very well me wrong on any of the points above. The question is: is there any methods of performing this kind of analysis on models solved by column generation? The most important thing is to minimize the number of column generation steps. Thanks! Pavel > Hello, > [quoted text clipped - 30 lines] > Thanks! > Pavel Take a look at the following reference: @ARTICLE{Gleeson1990, author = {John Gleeson and Jennifer Ryan}, title = {Identifying Minimally Infeasible Subsystems of Inequalities}, journal = {ORSA Journal on Computing}, year = {1990}, volume = {2}, pages = {61-63}, number = {1}, month = {Winter}, abstract = {Given an infeasible system of linear inequalities, we show that the problem of identifying all minimally infeasible subsystems can be reduced to the problem of finding all vertices of a related polyhedron. This results in a shorter enumeration than that performed by a previous method to solve this problem.} } Let F(x) = f'x, and suppose that when the column generator gives up, the optimal value of RMP is still strictly positive. Then the linear system (*) given by -Ax <= -b f'x <= 0 is inconsistent. Using one of the theorems from Gleeson-Ryan (I think it's the "cone" version), and assuming I'm doing my matrix algebra correctly (not a given), you can turn the problem of finding an IIS into the LP max b'y s.t. A'y = f y >= 0. The idea is to identify a feasible y with b'y > 0, in which case the nonzero components of y point to an IIS for the linear system (*). HTH, Paul > Let F(x) = f'x, and suppose that when the column generator gives up, the > optimal value of RMP is still strictly positive. Then the linear system [quoted text clipped - 17 lines] > HTH, > Paul Thanks, Paul, this is a much quicker method than my simplistic infeasibility diagnosis. I might ask something really stupid but are you sure that an IIS for the system (*), i.e. RMP, will correspond to an IIS for the complete linear system? By "complete" I mean if I didn't use column generation but rather listed all columns explicitly in the first place. I have a feeling that it will not. What I think I am observing right now is: - Column generation produces the optimal RMP. Objective value is positive. - I compute some IIS for RMP (for the system (*), to be precise). - The objective value of the IIS is positive, as it should. - However, if I run the column generator again, it adds some more columns to the IIS and *then* the objective value gets down to zero. So it seems that one can't that easily discover IISs for the complete system by only running infeasibility diagnosis on RMP. At the same time I can't find any literature on infeasibility diagnosis for RMPs, and this makes me think that I am wrong somewhere. Thanks, pavel >> Let F(x) = f'x, and suppose that when the column generator gives up, the >> optimal value of RMP is still strictly positive. Then the linear system [quoted text clipped - 39 lines] > Thanks, > pavel Maybe I'm misunderstanding your problem. I thought that you were solving the RMP with column generation until you reached optimality (meaning the column generator no longer found new columns worth using -- what I meant above by "when the column generator gives up"), and at that point you had a strictly positive optimal value and wanted to know why it did not reach zero. If you do the infeasibility analysis on (*) at some stage before the column generator is exhausted, all you find out is why the RMP at that stage still had a positive value. But once you get a solution to RMP for which the column generator cannot find a new column with a negative reduced cost, then an IIS of (*) tells you why the optimal value is positive and not zero. /Paul > Maybe I'm misunderstanding your problem. I thought that you were > solving the RMP with column generation until you reached optimality > (meaning the column generator no longer found new columns worth using -- > what I meant above by "when the column generator gives up"), and at that > point you had a strictly positive optimal value and wanted to know why > it did not reach zero. This is exactly right. Then I find an IIS for optimal RMP (as you've said: for which column generator can't find a column with negative reduced cost). But then if drop all constraints from RMP except of those in the IIS, the column generator will be able to find some more improving columns and objective value can go to zero. Is this possible? If no, then there's simply a bug in my code (I hope that's the case). However, If yes, then this IIS is not quite what I need. cheers, pavel PS. Sorry if you got this message multiple times (my previous postings seem to have disappeared). >> Maybe I'm misunderstanding your problem. I thought that you were >> solving the RMP with column generation until you reached optimality [quoted text clipped - 17 lines] > PS. Sorry if you got this message multiple times (my previous postings > seem to have disappeared). (So far it's shown up only once in the group -- two other copies found their way to my mailbox.) If you drop the constraints that are not part of the IIS and then use the column generator on a subproblem containing only the constraints from the IIS (meaning the column generator problem has changed), then I'm pretty sure it is possible to find improving columns. They are improving columns for a different problem, of course. Something else to keep in mind: an infeasible problem can have multiple IISes. In this case, they all must contain the "objective <= 0" constraint, but other than that there is no restriction on how much, if at all, they overlap. I don't know if that bears on your problem, because I don't know what you are trying to do. (I understand what you say you are doing, but not why you are doing it.) If you are looking for constraints that prevent the objective from reaching zero (say, with the intention of loosening some or all of them), then this procedure works, subject to the observation that you might need to identify all possible IISes to be sure that loosening the constraints you chose would get the job done. (If you are looking for a minimal cardinality set of constraints which, if dropped, would let the objective value reach zero, you might be interested in another reference, which finds a minimal cover for all IISes.) Otherwise, I'm in the dark what your goal is. Note that, at the stage where the column generator runs out of cuts, dropping pretty much any binding constraint in the RMP has the potential to reduce the objective value, possibly to zero (or beyond). /Paul > (So far it's shown up only once in the group -- two other copies found > their way to my mailbox.) Oh well, I must have clicked "reply to author". Sorry. > If you drop the constraints that are not part of the IIS and then use > the column generator on a subproblem containing only the constraints > from the IIS (meaning the column generator problem has changed), then > I'm pretty sure it is possible to find improving columns. They are > improving columns for a different problem, of course. Ok, thanks. Otherwise I'd suspect that my RMP simply wasn't optimal in the first place. > Something else to keep in mind: an infeasible problem can have multiple > IISes. In this case, they all must contain the "objective <= 0" > constraint, but other than that there is no restriction on how much, if > at all, they overlap. I don't know if that bears on your problem, > because I don't know what you are trying to do. (I understand what you > say you are doing, but not why you are doing it.) It's absolutely the case - there will be multiple IIS. However at this point I'm only interested to find *some* IIS (just to make it simple). Let's assume for the moment that I don't use column generation and (somehow) produce the system with all columns explicitly listed ("full system"). Then I'd find some IIS as you've explained. What's critical for me is that just the IIS (w/o any other constraints) has a positive objective value. Now, being unable to list all columns explicitly I use column generation and produce optimal RMP. Then, as before, I compute IIS. But now this IIS loses that critical property: if I add enough columns it's objective value may not be positive! This is quite unfortunate since although RMP has the same objective value as the full system, its set of IISs seems to be different (a superset of?) from the set of IISs for the full system. In other words, using column generation does have an impact on infeasibility analysis and I'm slightly surprised that I couldn't find a decent discussion of it in the literature. Of course I need IISs for the full system. I guess the easiest would be just to "test" if a particular IIS for RMP keeps being an IIS no matter how many more columns are added. The reason I'm doing all this is because my constraints represent restrictions on possible probability distributions and IISs will simply indicate which probabilistic facts are in conflict. Definitely there will be many subsets. Then I might do loosening (i.e. repair) by computing some minimum weight IIS cover (I did find good publications on that, thanks). But that's for later, now I'm just trying to get an IIS by invoking my not-amazingly-fast column generator as few times as possible. Thanks, Pavel Check what I write below very carefully, because I'm only half awake today. :-) Assuming that you do column generation the old fashioned way (take the dual solution to the RMP and use it in a subproblem to generate a new column whose reduced cost in the RMP would be negative), I think maybe the dual to the RMP answers your question, at least in part. Let's write your original problem as min z = c'x s.t. A x >= b, x >= 0. Assume that at some point the RMP yields a strictly positive objective value, and the column generator cannot find a column to improve the objective. Lacking proper math fonts (I sooo want to put tildes on things!), I'll use subscripts 1 and 2 to partition the columns into those included in the RMP and those not yet discovered (and therefore destined never to be discovered), respectively. So the RMP is min z = c1'x1 s.t. A1 x1 >= b, x1 >= 0 and its dual is max b'y s.t. A1'y <= c1, y >= 0. Using asterisks to denote the respective optimal solutions to the RMP and it's dual, we have c1'x1* = b'y* > 0 and (importantly) A2'y* <= c2 since the column generator, working with y*, cannot find a "hidden" column with negative reduced cost. Now suppose I drop from the original problem every constraint j whose current dual value y*_j is zero. Let A1r, A2r and br denote the reduced constraint matrices and RHS respectively, and yr the correspondingly reduced dual solution. So the reduced full problem is (*) min c'x s.t. [A1r | A2r] x >= br, x >= 0, the reduced RMP is min c1'x1 s.t. A1r x1 >= br, x1 >= 0, and its dual is max br'yr s.t. A1r'yr <= c1, yr >= 0. Set yr* equal to the nonzero portion of y*; then yr* is a feasible solution to the dual of the reduced RMP with objective value br'yr* = b'y* = c1'x1* > 0. Moreover, A2r'yr* = A2'y* <= c2 as before, so yr* is a feasible solution to the dual of (*), which means (*) has a strictly positive objective value. Thus the rows kept in (*) are enough to force a positive objective. Assuming I did not mess up along the way, that leaves two questions: (a) is this an irreducible set of rows that force a positive objective value; and (b) is there a good way to identify other such sets? Trial- and-error relaxations of original constraints should answer both. Off- hand, I don't see a more efficient way (but with more sleep, who knows?). /Paul |
Reply to this Message |
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2010 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.