Skip to main content

Questions tagged [polyhedra]

For questions on the set of points that satisfy a finite set of linear inequalities.

12 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6 votes
0 answers

Characterization for total dual integrality

A problem I study reduces to whether the polyhedron $P=\{\mathbf{x}\mid A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0\}$ is integral ($A$ is a matrix with coefficients in $\{0,1\}$). I know that the ...
Surpass2019's user avatar
6 votes
0 answers

What are the top three applications (in terms of number of citations) of the "reverse search" algorithm of David Avis?

I can see that this algorithm is quite popular, and that one of the original papers now has 820 citations on Google Scholar. However, what are the most highly cited applications of it? If in Google ...
Nike Dattani's user avatar
  • 1,278
5 votes
0 answers

Polyhedra to Simplex by using convex combination of vertices

Optimization problems over linear constraints (defining a convex polyhedron) can be written as optimization over a simplex in a higher dimension. Let $\mathcal{P}$ be a bounded polyhedron, and the ...
independentvariable's user avatar
4 votes
0 answers

Any recommendations for learning about polyhedra and integer programming?

My knowledge on convex polyhedra and systems of linear inequalities (facets, edges, Farkas Lemma, projections, duality, etc.) is very scattered, and I'l like to go through a book to solidify it. I'm ...
user56202's user avatar
  • 233
3 votes
0 answers

Appropriate Rotation Matrix in Nonconvex Optimization with Barrier

Let $ x \in \mathbb{R}^n_+$ be a variable such that $\sum_{i=1}^n x_i = 1$. In other words, $x$ is in a probability simplex. I am working on barrier-like functions in nonconvex optimization over such ...
independentvariable's user avatar
3 votes
0 answers

Theoretical aspect of using extended formulation

If I can show a polyhedron Y is an extended formulation of polyhedron X and every extreme point in Y is integral, does that automatically imply the projection of Y onto the variable space of X gives ...
Octavia's user avatar
  • 31
2 votes
0 answers

The facet-defining inequalities for a single resource scheduling problem

Suppose, there exists a scheduling problem $S$, in this case a single resource, with the following descriptions: $$ \text{conv(S)} = \{x \in \mathbb{R}^n \ | \ \forall \lambda_{i} \in \mathbb{R}^{n+}, ...
A.Omidi's user avatar
  • 8,960
2 votes
0 answers

System Stability constraints formulation

I am working with a system having a massless 2D plane and on that plane there is a rigid object with some mass placed on it. I want to support the plane with wooden sticks such that the system is ...
Ken Adams's user avatar
1 vote
1 answer

How to generate random bounded polytope by MATLAB defined by Ax=b, x≥0

How can one create a random bounded polytope in MATLAB, specified by the conditions $‎\lbrace‎x:~ Ax = b,~ x \geq 0‎\rbrace‎$
Optimization Online's user avatar
1 vote
0 answers

Decomposition of Polyhedra

There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system $$ \...
holala's user avatar
  • 111
1 vote
0 answers

Vertices of Polytope using Gurobi

Is there any way I can obtain all the vertices of a polytope using Gurobi? If this isn't possible, can I log all the intermediate vertices that Simplex finds before it hits the optimal one?
Grigoris Velegkas's user avatar
0 votes
0 answers

Supremum of a probabilistic function with ambiguity distribution set using Wasserstein metric

There is a proof of how to derive distributionally robust chance constraints with ellipsoid bound. $$\inf_{\mathbb{P}\in\mathcal{D}^{WD}} \mathbb{P}\{\|\mathbf{A\zeta-b}\|_2 \leq 1\} \geq 1-\epsilon$$ ...
Kaiming Zhang's user avatar