# Questions tagged [linear-programming]

Linear programming is the study of optimizing a linear function over a set of linear inequalities. The Simplex Method, Ellipsoid Method and Interior Point Method are popular algorithms to solve linear programs.

447 questions
Filter by
Sorted by
Tagged with
27 views

### How to find such a Markov matrix?

Suppose A is a m×n Markov matrix, and C is a m×k Markov matrix. How to decide (analytically or numerically) whether there is a n×k Markov matrix such that AB=C? I feel that it is a linear programming ...
1 vote
231 views

### Who called Farkas' fundamental theorem a lemma?

Farkas proved his famous result (which, nowadays, is fundamental in optimization theory) in 1902 and called it Grundsatz der einfachen Ungleichung which may be translated as fundamental theorem of ...
60 views

39 views

### Simplest sensitivity analysis in semi-infinite linear programming

Consider a standard linear program of the form \begin{align*} \min_{x}c^{\top}x & \,\,\text{subject to}\\ Ax & =b\\ b & \geq0\,. \end{align*} It is well-known that if we perturb the right-...
30 views

### Subtour-gluing constraints for ILP formulation of TSPs

If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
6 views

### Bounds on number of subtour elimination constraints needed for solving TSPs to optimality

Question: what is the "subtour complexity" of the TSP, that measures how the number of subtour constraints the ILP, that finally solves a TSP instance to optimality, can have in the worst ...
74 views

### Why is Gaussian distribution always chosen for smoothed analysis?

I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...
40 views

1 vote
79 views

339 views

### Maximizing a piecewise-linear convex function

Crossposted on Operations Research SE. I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables: ...
1 vote
121 views

### Decomposition of Polyhedral - An example

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  \...
71 views

### A question on graph partitioning

Given a connected un-directed simple graph $G=(V,E)$, is there a polynomial time algorithm to find the smallest subset $S$ of $V$ such that each node in $V \setminus S$ has at least 50% of its ...
1 vote
338 views

### Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]

Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...