0
votes
0answers
5 views

Show that every extreme point in Q is either an extreme point of P or a convex combination of two adjacent extreme points of P

P is a bounded polyhedron in $\mathbb{R}^n$, $a$ a vector in $\mathbb{R}^n$, and $b$ some scalar. Define $$Q = {x \in P | a'x = b}$$. Show that every extreme point in Q is either an extreme point of P ...
1
vote
0answers
47 views

Linear programming - Textbook recommendations

Next term, I will attend a course on linear programming. Due to the assignments, we will have to write many thorough proofs. I anticipate that we will be supposed to cope with in-depth background ...
0
votes
2answers
26 views

LP: An algorithm to decide whether a polyhedron is a subst of another polyhedron

I've encountered the following question which I am unable to solve: $$ P = \{\vec x | A\vec x \geq \vec a\} \\ Q = \{\vec x | B\vec x \geq \vec b\}\\ P, Q \subseteq R^n $$ Find an algorithm to ...
1
vote
1answer
48 views

Minimum distance of extreme points of polyhedra

Let $P = \{x \in \mathbb{R}_{\geq0}^n \colon Ax \leq b\}$ with $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R^m}$. Let $E \subseteq P$ be the extreme points of $P$. Can anything be said about ...
0
votes
1answer
42 views

Polyhedron's Representations and spanning the Euclidian space

Let's say you have to different representations of the same polyhedron $P\neq \emptyset$: $$P=\{x\in \mathbb{R}^n\;|\;h_i^Tx\leq c_i, i=1,...,k \} =\{x\in \mathbb{R}^n\;|\;g_j^Tx\leq d_i, j=1,...,l ...
2
votes
1answer
118 views

Dimension of polyhedron defined by inequalities and rank of implied equalities

I'm looking at "Optimization Over Integers" by Bertsimas and Weismantel and I have a question about one of the examples in the book. I'm getting a conflicting answer and I'm not sure what I'm ...
1
vote
1answer
61 views

Integral Polyhedra: Integer on each face

The general topic is unimodular matrices and integral polyhedra. I am really new to this field and I am studying for an exam in an advanced operations research course. In this case we are always ...
1
vote
0answers
33 views

$X$ is a point in a bounded polyhedron $\ \in R^n $ with $n-1$ active constraints

Lets take a vector $d$ which is orthogonal to the active constraint. Since the polyhedron is bounded: We'll move to a point $x+\alpha*d$ where we will activate another constraint let's name it j. ...
1
vote
1answer
160 views

How tell if a polyhedron contains a lattice point

So given a polyhedron $Ax \le b$ Is there an Algorithm or formula to determine whether said polyhedron contains a lattice point (integer point) I was thinking a couple things: brute force ...
4
votes
0answers
52 views

Mappings preserving convex polyhedra

It is known that linear mappings between euclidean spaces map convex polyhedra to convex polyhedra. Can you give a characterization of the class of mappings that preserve convex polyhedra?
0
votes
2answers
151 views

Is an unit-cube polyhedron? What about other platonic solids?

Definitions According to my linear programming course and screenshot here (Finnish), a polyhedron is such that it can be constrained by a finite amount of inequalities such that $$P=\{\bar x\in ...
0
votes
1answer
90 views

Does max { $w^Tx$ subject to $x$ is a point on a given polyhedron } optimize at an extreme point?

Is it necessary that the linear program max { $w^Tx$ subject to : $x$ is a point on a given polyhedron } attain its maximum at an extreme point of the polyhedron for any arbitrary w ? Let $c$ = ...