# 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.

432 questions
Filter by
Sorted by
Tagged with
8 views

### Subtour-gluing constaints 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 ...
64 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 ...
31 views

47 views

233 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: ...
23 views

### Analytic formula for $D(x,y) := \sup_{z \in B_p} \|z-x\|_1 - \alpha\|z-y\|_1$, where $\alpha \ge 0$ and $B_p$ is the unit $L_p$-ball

Let $\alpha \in [0,\infty)$ and $p \in [1,\infty]$, and consider the function $D_\alpha:B_p \times B_p\to \mathbb R$ defined by $$D_{\alpha,p}(x,y) := \sup_{z \in B_p} \|z-x\|_1 - \alpha\|z-y\|_1,$$...
102 views

80 views

### How to solve MILP problem on several linear subspaces

I have a set of close mixed-integer programming problems. More exactly, all the problems share the same set of (binary and continuous) variables, the same set of linear inequality constraints, and the ...
37 views

### Notion of distance between linear programs

Consider the linear programming problem \begin{align} \max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1 \end{align} where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
74 views

### What is the relation between different generalizations of linear programming?

Linear programming subsumed by each of Semidefinite programming (SDP) Convex programming (CXP) SOS programming (SSP) Is there any relation between each pair in the three? Are all three equivalent in ...
If we are given a set of real linear inequalities then using elimination theory or just linear programming we can decide. If the program also has inequalities of form $2^x\leq g$ in addition to linear ...