Questions tagged [extreme-rays]
The extreme-rays tag has no usage guidance.
11 questions
12
votes
2
answers
1k
views
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 ...
9
votes
1
answer
314
views
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 ...
7
votes
2
answers
1k
views
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 ...
- 81
7
votes
1
answer
1k
views
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 ...
- 1,731
6
votes
1
answer
480
views
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.) ...
- 411
5
votes
1
answer
234
views
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$ ...
- 75
3
votes
2
answers
1k
views
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\...
- 4,030
2
votes
1
answer
301
views
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 ...
- 327
2
votes
1
answer
152
views
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 ...
- 970
2
votes
1
answer
330
views
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 - ...
- 21
0
votes
0
answers
56
views
How to get an extreme ray in CPLEX
I am trying to get an extreme ray in a Benders decomposition when the primal subproblem is infeasible (so, the dual is unbounded). CPLEX below propose some function but no one works.
If you are using ...
- 1