Questions tagged [extreme-rays]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer

How do you derive the Benders feasibility cuts?

starting off with a MIP that I want to solve using Benders. so in Benders Decomposition, you add feasibility cuts in the following form: $v^j (b - Ax) \geq 0$ with $j \in J$ being the set of extreme ...
Arctic_Skill's user avatar
2 votes
1 answer

Obtaining the dual ray of an infeasible lp to generate a benders feasibility cut

I am struggling to correctly interpret the meaning of a dual ray for an infeasible primal lp. Consider the following example. $$ \min z = y_1 + y_2 -2y_3 $$ s.t $$y_1 -2y_1 -y_3 \ge 3 $$ $$-2y_1 - ...
Kit Searle's user avatar
2 votes
1 answer

general approach to iterating extreme rays of solution cone

Suppose I'm at an optimal solution of an LP relaxation in a MILP branch-and-bound descent. I want to add an additional cut of my own devices. To compute this cut I need the extreme rays of the cone ...
Brannon's user avatar
  • 892
7 votes
2 answers

How to find extreme rays

I am applying Benders decomposition and the dual is unbounded. I need to find the extreme rays to proceed, but I am not sure how to do that. Following is an example problem, can someone explain how ...
John Bolton's user avatar
6 votes
1 answer

Extreme rays of a small polyhedral cone: How do I get them?

In a nutshell I have a small 2-dimensional polyhedral cone. $$C=\{(x_1,x_2): 2x_1-x_2 \leq 0, x_1+3x_2 \leq 0\}$$ I am looking for a simple, illustrative, procedure to get its extreme rays. Any ...
k88074's user avatar
  • 1,641
5 votes
1 answer

Find Extreme direction of equality constraints

I think this is a very basic question, but I failed to find an algorithm for this... When I have a set of inequality constraints, $Ax \leq b$ as my feasible region, I can set $b = 0$ and find $n-1$ ...
PetaGlz's user avatar
  • 75
6 votes
1 answer

Extreme point and extreme ray of a network flow problem

"It is a well-known result in network flow theory that an extreme point and an extreme ray of the polyhedron defined by the convex hull of feasible region corresponds to a path and cycle (resp.) ...
Pramesh Kumar's user avatar
3 votes
2 answers

How to get an extreme ray of an LP from Gurobi

I am working on a problem of form \begin{equation} \begin{array}{l @{\quad} l} \mathrm{max}_{x, u} & p^{\top} u \\ \text{st.} & A u + a x \leq 0 \\ & x \in \{0, 1\...
independentvariable's user avatar
9 votes
1 answer

Extreme rays in polymake

I am trying to find extreme rays of a polyhedral cone using polymake. My understanding is that in a cone, every feasible solution is also a ray and an extreme ray is a ray that cannot be written as ...
Florian Pommerening's user avatar
12 votes
2 answers

Generating all extreme rays

I am trying to understand a problem and would like to generate all extreme rays for a given set of linear constraints. With the Python interface of CPLEX, I was able to generate a single ray (not sure ...
Florian Pommerening's user avatar