Wednesday, February 13, 2013

Finding Multiple Extreme Rays

I've done a few posts relating to extreme rays before: "Finding Extreme Rays in CPLEX"; "Farkas Certificates in CPLEX"; "Infeasible LPs and Farkas Certificates". Today the following question arose: given an unbounded linear program, can we get the solver to provide us with multiple extreme rays in a single operation. (The "dual question" to this is whether, given an infeasible primal problem, we can obtain multiple Farkas certificates in one gulp.)

I'll answer in the context of CPLEX, making no claims as to whether this applies to other solvers (though I suspect it does). I don't think there's any way to get multiple rays from one solution attempt without additional computations, but there is a way to get multiple extreme rays (though possibly not all of them) by modifying the objective function of the original problem, while exploiting the feasibility of the last known primal solution (the one that convinced the solver that the problem is unbounded). Hot-starting from previous solutions should reduce the amount of work involved in finding extra rays, but the additional work will not be zero.

Suppose that we solve the linear program \[ \begin{array}{lrcl} \mathrm{maximize} & & c^{\prime}x\\ \mathrm{s.t.} & Ax & \le & b\\ & x & \ge & 0 \end{array} \] and discover that it is unbounded. The CPLEX getRay method will then provide us with one extreme ray. To find additional rays, we need to modify the objective function so that (a) other recession directions continue to be favorable and (b) the recession directions we have already obtained cease to be favorable. The former suggests that we want a new objective vector acute to the original one; the latter means we need the new direction to be orthogonal or obtuse to the recession directions we have already identified.

Let $\mathcal{D}$ be the set of recession directions we know at any given stage. One way to find a new objective coefficient vector $\tilde{c}$ meeting our criteria is to solve the following auxiliary linear program:\[ \begin{array}{lrclr} \mathrm{maximize} & & c^{\prime}\tilde{c}\\ \mathrm{s.t.} & d^{\prime}\tilde{c} & \le & 0 & \forall d\in\mathcal{D}\\ & -1 & \le\tilde{c}\le & 1 \end{array}. \]The objective function encourages the new direction $\tilde{c}$ to be acute to the original direction $c$, while the constraints ensure that the new objective function ($\tilde{c}^\prime x$), which we maximize subject to the original constraints $Ax\le b,x\ge 0$, does not increase along any of the recession directions we have already identified.

As an example, consider the linear program\[ \begin{array}{lrcl} \mathrm{maximize} & 3x+2y+z\\ \mathrm{s.t.} & 2x-y-3z & \le & 4\\ & x+2y-5z & \le & 3\\ & -4x+2y+z & \le & 6\\ & -x-y+2z & \le & 2\\ & x,y,z & \ge & 0. \end{array} \]Using the approach I just described, I am able to find three extreme directions:

Objective directionRecession direction
(3, 2, 1)(5, 1, 3)
(0.4, 1, -1)(2.2, 1.4, 1.0)
(-0.1818, 1.0, -1.0)(1.0, 1.5833, 0.8333)
(0.2, 0.4, -1.0)OPTIMAL

With the fourth objective vector, the modified LP becomes bounded, and we halt the search.

Did we find all the extreme directions of the original problem? I think not. Since our example lives in $\mathbb{R}^3$, each extreme direction will correspond to an edge, the intersection of two of the seven bounding hyperplanes. (The seven bounding hyperplanes are the hyperplanes corresponding to the four functional constraints, plus the coordinate hyperplanes $x=0$, $y=0$, $z=0$ corresponding to the sign restrictions.) The recession directions in the second column of the table are the intersections of the first and fourth constraint hyperplanes, the first and second, and the second and third respectively. The intersection of the first and third constraint hyperplanes gives a direction $(1, 2, 0)$ which is not a recession direction (movement eventually is blocked by the second constraint). Similarly, the intersection of the second and fourth constraint hyperplanes yields a direction $(-1, 3, 1)$ that is eventually blocked by either the third constraint or the sign restriction on $x$, depending on where in the feasible region you start moving in that direction. The intersection of the third and fourth constraint hyperplanes, however, yields the direction $(5, 7, 6)$, which is not blocked by anything and along which the original objective increases.

So this method is not guaranteed to find all extreme directions of an unbounded linear program, but it will find some. The computational cost is repeated solution of a relatively small auxiliary linear program (the same number of variables as the original LP, but likely considerably fewer constraints in practice) and repeated re-solving of the original problem with modified objective functions (where each previous solution gives a feasible starting solution).

If anyone cares, I have uploaded Java code for this demonstration.


  1. Hi Paul

    I'm trying to implement a benders decomposition on a large scale MIP with 8000 binaries and general integers. However, my issue is that I'm not hitting a feasible subproblem. I'm generating feasibility cuts forever. I'm trying the current approach you mentioned for multiple extreme rays but still can use any useful suggestions.


    1. The first three steps are straightfoward: make sure your original model really is feasible; make sure your Benders formulation is correct; and make sure your feasibilty cuts really do cut off the master solutions that generate them.

      Beyond that it's hard to say much that's useful. Some problems have an underlying structure that allows you to add a few seemingly redundant constraints to the master problem that either force it to find feasible solutions or at least encourage it by weeding out grossly infeasible solutions. For instance, if there is an underlying transportation problem, you can tell the master that all demands must be satisfied or that no source can exceed its supply.

      Finally, there is a paper by Magnanti and Wong on producing deeper optimality cuts. I don't have the reference handy, but search the blog for Magnanti's name and I'm sure you'll find it. The paper only applies to optimality cuts, but (and what follows is conjecture) I think you could exploit it by setting up an auxiliary subproblem in which constraints contain artificial variables and the objective is to minimize their sum. Generate an "optimality" cut for that problem and bound it above by 0 (since the sum of the artificials must be zero in a feasible solution) to get a possibly deeper feasibility cut.

    2. Hi

      Thanks for the reply. I have checked the formulation, it works for small and mid sized problems. However, the issue comes for larger problems. I have applied the cuts given by Magnanti and Wong as well but it has not helped. I also tried the combinatorial cuts by Codato and Fischetti but it did not help much. The current problem structure that I have is that it has three sets of constraints: Purely integer, purely linear and mixed constraints which are mostly indicator constraints for capacities. The Master problem is a profit maximization problem, but all the master variables have negative objective costs (these are cost components). So, by default the master problem tends to push all integers to zero.
      I will try adding the redundant constraints as you mentioned.


  2. This comment has been removed by the author.

  3. Hi Dr. Rubin,
    Thanks for your useful notes.

    Now that we are able to find multiple extreme rays, do you think it is a good idea to add multiple feasibility cuts at the same iteration to the master problem? or will it make the master problem very difficult to solve?

    Also, can we think of a way (similar to Pareto cuts) for comparing the feasibility cuts and select the best one ?


    1. I think the question of adding multiple feasibility cuts at once is an empirical one. It might make things faster on one problem instance and slower on another. (That's just a guess on my part.)

      Your second question is a good one. Magnanti and Wong proposed a method for generating _optimality_ cuts that are, if not deepest, at least deeper than what one might get at first blush. I have a suspicion that by adding artificial variables with penalties (converting a feasibility problem to one of minimizing violation costs), one might do something similar for feasibility cuts, but I have not investigated that.

    2. Thanks for sharing your thoughts.


If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.