# 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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**1**answer

31 views

### Do we really need degree constraints for ILP formulations of TSP problems

The Dantzig-Fulkerson ILP-formulation of the symmetric TSP is
$$\min\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n c_{ij}x_{\lbrace i,j\rbrace}\quad\text{s.t.}\\ \sum\limits_{j\ne i,\,j=1}^n x_{\lbrace ...

**2**

votes

**0**answers

65 views

### Reference for Chebyshev centers

Today, I came across the concept of Chebyshev center twice.
In particular, it is the key tool in the very elegant paper "A fixed point theorem for $L^1$ spaces" by Bader, Gelander and Monod.
...

**0**

votes

**0**answers

14 views

### Can the most distant edge-disjoint pair of perfect matchings be calculated efficiently

Question:
has the linear program
\begin{align}
\text{LP:} \\
& \sum_{ij} w_{ij}\cdot(b_{ij}-a_{ij})\ \stackrel{!}{=}\ \max \\
\text{s.t. } & \sum_{ij}a_{ij}\ \le\ \sum_{ij}b_{ij} \\
& 0\ ...

**1**

vote

**0**answers

30 views

### Second-order envelope theorem for linear programming

Consider parameterized linear programming $V(\theta) = \max_x \langle c(\theta),x\rangle$ s.t. $A(\theta)x\leq b(\theta)$, $x\geq 0$. Let's also assume $c,A,b$ are infinitely differentiable with ...

**0**

votes

**0**answers

22 views

### Sum of all integer binary solutions of a TUM linear system

I have the following problem: $A x = b$ where $A$ is a $m \times n$ total unimodular matrix (TUM) with entries in $\{0,1\}$ and $b$ is a $m$-vector of strictly positive integers. Let $\mathcal X$ be ...

**0**

votes

**0**answers

62 views

### Minimum circumscribed ellipsoid of $\mathcal H$-polytope

Given matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^n$, consider the $\mathcal H$-polytope $P$ defined as follows
$$ P := \left\{ x \in \mathbb{R}^n : Ax \leq b \right\} $$
I ...

**0**

votes

**0**answers

119 views

### Any technique for linearization, or linear approximation?

Consider the following Matrix constraint:
$$
\begin{bmatrix} -U+\psi\Sigma_b^{-1} & V \\ V^T & -V^TU^{-1}V+\tau_2 -\psi \end{bmatrix} \leq 0
$$
where $\Sigma_b$ is a known positive definite ...

**0**

votes

**1**answer

57 views

### How hard is a linear programming with a bounded constraint?

Background: I am reading Greg Kuperberg's answer to the question Deciding membership in a convex hull. I am thinking about the complexity of ''Deciding membership in a convex hull''.
Restate the ...

**2**

votes

**0**answers

79 views

### Continuum of Lagrange multipliers, duality gap, and minimax theorem

Suppose I have a linear optimization problem involving random variables on some (infinite) probability space $\Omega$. For example, need to maximize expectation $E[Q]$ of random variable $Q$ subject ...

**0**

votes

**1**answer

67 views

### How do you call a linear programming problem when the solution should be "constrained" to a norm?

(apologies for the n00b question)
Let's say we have a vector of length $n$, with to-be-determined values: $a_1, a_2, ...,a_n$.
And we have information that partial sums of these elements are equal to ...

**0**

votes

**0**answers

43 views

### Geometric of sphere caps with infinite radius $R$ (asymptotic) in dimension $C$

Let $B_C(R)$ be the Ball in $R^C$ with radius $R$, the vectors $w_1,w_2,\dots,w_{C-1}\in R^C$ is the normal vector of hyper half plane, the area
$$\mathcal{K}=\{x:w_1^Tx\leq0, w_2^Tx\leq0,\dots,w_{C-1}...

**1**

vote

**0**answers

47 views

### Optimization problem on trace of complex matrix product

Given a complex rectangular matrix $A$ $(k \times n)$, I am interested in solving the following optimization problem over $(k\times n)$ complex matrices $x$:
$$
\mathrm{arg}\max_X \,\mathrm{trace}(X^...

**2**

votes

**0**answers

68 views

### Polyhedron coordinate bound

Given a polyhedron
$$Ax\leq b$$
where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...

**1**

vote

**0**answers

42 views

### Detecting non-negativity of a single constraint by polyhedral constraints - $II$

Let $$\langle a,x\rangle=b$$ be a linear constraint where $x\in\mathbb R^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\mathbb Z_{\...

**0**

votes

**1**answer

96 views

### Detecting non-negativity of a single constraint by polyhedral constraints - $I$

We consider $$\langle a,x\rangle=b$$ (linear constraints) where $x\in\mathbb R_{\geq0}^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\...

**0**

votes

**1**answer

65 views

### Iterations of Dantzig-Wolfe Decomposition for a Simple Linear Programming problem

This arises from an engineering problem I am working on. Let $\mathbf{c}_i,\mathbf{a}_i,\mathbf{b}_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the ...

**0**

votes

**0**answers

22 views

### Characterizing a variant of completely-Q matrices in linear complementarity problems

Given an $(n\times n)$-matrix $A$ (over the reals) and a vector $q \in R^n$, the linear complementarity problem $LCP(A,q)$ is the following problem:
Find $w,z \in R^n_+$ such that
$$w = q + Az,$$
and
$...

**0**

votes

**0**answers

75 views

### Number of vertices in a polyhedron

Consider polytopes
$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$
$$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$
$$B[z_{1},z_{2},z]'\leq c$$
having vertex count $v_1,v_2$ and $v$ respectively.
We ...

**1**

vote

**1**answer

48 views

### $\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves

$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...

**1**

vote

**0**answers

152 views

### continuity of linear programming

I have the following conjecture:
Given a closed convex set $S \subseteq \mathbb{R}^n$ and one of its exposed face $F=\{x \in S \mid \pi x = \pi_0\}$, where $\pi x =\pi_0$ is the supporting hyperplane ...

**0**

votes

**0**answers

40 views

### Karush-Kuhn-Tucker in discrete time dynamic optimization

I need to solve the following problem:
$\max_{p_t\in [\phi_1(s_t),\phi_2(s_t)]} \sum_{t=0}^\infty p_t\times(a+\alpha s_t-p_t)$, subject to $s_0$ given and $s_{t+1}=\beta(s_t+\eta(a+\alpha s_t-p_t))$.
...

**1**

vote

**1**answer

58 views

### Optimality gap between a joint linear program and decoupled sub programs

Let $\mathbf{c}_i,\mathbf{s}_i$ be given entry-wise positive $n\times 1$ vectors for $i\in[1,\dots,d]$. Let $\tau, \alpha_1,\dots, \alpha_d$ be given positive constants.
Consider the linear ...

**1**

vote

**0**answers

70 views

### Algorithm for deciding feasibility of linear programs [closed]

Suppose I have the simple linear program
$$Ax \geq 0, \quad x \geq 0$$
We know that this system has a solution (for example, $x=0$). But, what if we made this rule for this system?
$$Ax \geq 0, \quad ...

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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,
$$...

**1**

vote

**0**answers

102 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
$$ \...

**0**

votes

**1**answer

70 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

**1**answer

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

**3**

votes

**0**answers

68 views

### Additional symmetries of the Traveling Salesman Polytope

Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...

**1**

vote

**1**answer

142 views

### Constructing representations of probability revision functions

Let $P$ be a probability distribution over a finite Boolean algebra $\mathfrak{B}$, and fix a parameter $t_{P} \in (\frac{2}{3}, 1)$. Define the `revision function of $P$', $R_{P}: \mathfrak{B}\...

**0**

votes

**0**answers

11 views

### Identifying essential degree constraints for ILP formulations of combinatorial optimal graph problems

Many combinatorial graph problems impose degree constraints on vertices; e.g. that the degree of every vertex in the solution to the TSP must be 2.
In all LP-formulations I have encountered so far, ...

**1**

vote

**1**answer

89 views

### Allowing an "OR" option between equations in a linear program

I am looking for a way to express an "or" option in a system of linear inequalities for a linear program I am working on.
I will explain what I mean precisely: Lets say I have a set of ...

**8**

votes

**1**answer

452 views

### Minesweeper as a linear algebra problem

I've written a computer program to generate and solve minesweeper games. Once I've eliminated the obvious mines and safe squares I look at each remaining connected setsin turn and formulate a linear ...

**0**

votes

**0**answers

56 views

### Convex optimization under asymmetric loss in infinite dimensional space

The following problem is common in financial economics
$$ \min_{m \in L^2} \mathbb{E}[ \phi(y(\theta)-m)] \quad \text{s.t. } \mathbb{E}[ mx ]= q $$
That is, given a random variable $y(\theta)$ ($\...

**2**

votes

**1**answer

120 views

### linear programming with $n$ choose $r$ variables

Given parameters $r < n$, define $m = {n \choose r}$ and let $A$ be the $n\times m$ matrix whose columns are all the vectors with $r$ $1$'s and $n-r$ $0$'s. Let $b$ be a positive $n$-vector. Is ...

**0**

votes

**1**answer

286 views

### Integer solution of optimal transport

Let us consider two vectors $\mathbf{a}=(a_1,...,a_n)$ and $\mathbf{b}=(b_1,...,b_m)$ so that each quantity is an integer $a_i,b_j \in \mathbb{N}$. It represents for example supply and demand. Let $\...

**1**

vote

**1**answer

610 views

### How to minimize l1-norm constrained by "infinity norm"

Let $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m $. I have the following two problems:
P.1.
\begin{equation}
\underset{x\in\mathbb{R}^n}{\text{minimize}} \| Ax-b \|_1 \\
\text{s.t. } \| x \...

**0**

votes

**1**answer

88 views

### An otherwise linear matrix equation with the presence of a signum function : reference request

Consider the equation $$\pmb{c}+\text{sign}(G\pmb{c}) = L$$
$\pmb{c}$ is a $n\times1$ matrix.
$G$ is a $n\times n$ matrix which is also positive definite.
matrices $G$ and $c$ are real.
$L$ is a $n\...

**3**

votes

**0**answers

91 views

### Convex optimization upper bound for a non-linear optimization

Is there any good convex optimization problem based upper-bound for the following non-linear optimization problem?
\begin{align}
\max_{x_1,\ldots,x_N}&\quad \sum_{n=1}^{N} \log(1+\frac{x_n}{1+\...

**0**

votes

**0**answers

59 views

### Solutions to matrix equations in the non-negative integers

For an integer matrix $S$, and an integer vector $y$, I'm looking for solutions to $xS = y$ where the entries in $x$ are in the non-negative integers.
I've been doing this with Sage's mixed integer ...

**1**

vote

**0**answers

16 views

### Fundamental regions in convex programming

Fundamental regions of linear programming are polyhedra (since those are the objects of intersection of linear inequalities) and for semidefinite programming it is spectrahedra (https://math.berkeley....

**1**

vote

**0**answers

86 views

### Convergence of infinite linear programming

Suppose we have the following linear program (LP1),
$$\min_{f \in \mathcal{C}} \int_{\mathbb{R}} f(t) \cos(2 \pi x_0 t) dt \\ \text{subject to } \int_{\mathbb{R}}f(t)dt = 1 \\\forall x\in [0,1]: \int_{...

**-1**

votes

**1**answer

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

**2**

votes

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

26 views

### Reference for the algorithm to find the intersection between a subspace and positive orthant

I came across this algorithm, in this question Algorithm for the intersection of a vector subspace with a cone of non-negative vectors ;
Is there any reference for the algorithm described in the ...

**0**

votes

**1**answer

106 views

### Linear programming with exponential inequalities and rational variables

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