# Tagged Questions

Questions on linear programming, the optimization of a linear function subject to linear constraints.

360 views

### Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
98 views

### Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture states that the graph (i.e. $1$-skeleton) of a $d$-dimensional polytope with $n$ facets has diameter at most $n - d$. It was known for a long time that it sufficed to prove it ...
43 views

67 views

### I'm walking towards my car - when should I try the remote, in an optimal sense?

I'm interested to learn about how discrete/'event' based elements are incorporated into optimisation problems. Hopefully this is an interesting problem in its own regard, it's inspired by a daily ...
72 views

### Parameterizing equilateral polygons

I'm not exactly sure how to describe what I want, so if I butcher terms, please forgive me :) I want to "parameterize" the space of simple irregular equilateral polygons with n sides, or at least a ...
78 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?
560 views

70 views

### Is $K =\{ S: \exists \text{ positive diagonal} D, D^TSD \;\text{diagonally dominant}\}$ convex?

I am doing some convex cone optimization and wonder whether the following set $K_1$ is convex or not. Assume the following matrices are all in $\mathbb{R}^{n\times n}$ and symmetric. Let the set of ...
86 views

The objective is to find the greatest lower bound of the variable $\mu$. The lower bound is resulting from the positive-semidefinite (PSD) constraint $$\tilde{\mathbf{T}}:=\left( \begin{array}{ccc} ... 0answers 207 views ### A basic question related with the solutions of linear programming problems I have to select one option from the problem statement given below. Which of the following statements is true in case of linear programming. 1: An optimal solution exists at extreme points of a ... 0answers 370 views ### Nested optimization problems solving using mixed integer linear programming Let us have two vectors of decision variables, \mathbf{x} and \mathbf{y}, two linear objective functions, F \left( \mathbf{x}, \mathbf{y} \right) and f \left( \mathbf{x} \right), and two sets ... 0answers 109 views ### The importance of the full-row-rank assumption for the simplex method Consider a linear programming model in the usual form ready for applying the simplex method. I understand that having the constraint equations' coefficient matrix A be of full row rank means not ... 0answers 63 views ### Convexity in oriented matroid theory: proof on closure operator? I would like to try to solve the following problems. Problem from the Oriented Matroids book by Bjorner, Las Vergnas, Sturmfels, White, and Ziegler. It is problem 3.9 on page 152. Attempt ... 0answers 316 views ### fundamental theorem of linear inequalities Do you know a proof for the fundamental theorem of linear inequalities, which does not employ an implicit use of the simplex algorithm? Let a_1, \dots, a_n, b \in \mathbb R^m. Then either b is a ... 0answers 62 views ### finding the largest p components of x Given an n \times n matrix A, and an n \times 1 vector b, the conventional way of computing an n \times 1 vector x such that x=Ax+b is to use the following iterations:$$x_{k+1}=Ax_{k}+b....
I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$: $$\max_j c' x_j$$ Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...