# 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

0
votes

0
answers

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

1
answer

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

0
votes

0
answers

60
views

### Using the duality theorem for an optimization problem with two variables

I wish to apply the duality theorem to the optimization problem:
$$\text{minimize}~~s$$
$$\text{subject to}~~g_j(x)\leq{s},~~\text{for all}~~j=1,...,r,~~x\in{X},~~s\in{\mathbb{R}},$$
where $X\subseteq{...

1
vote

1
answer

175
views

### Finding a special solution in a solution set over F2

given a solution set of a linear system of the following form
$$
\{ \begin{bmatrix}
x_{1} \\
\vdots \\
x_{n}
\end{bmatrix} = \vec{v_1} * x_1 + \dots + \vec{...

0
votes

1
answer

52
views

### What is the best way to choose initial basis when applying simplex method to an equality form of LP?

Currently I'm trying to write a practically fast LP solver for a sparse instance, which is by simplex method with LU decomposition and eta-matrix update. In the development I realized that I'm not ...

4
votes

2
answers

121
views

### Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment

I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...

0
votes

1
answer

78
views

### Correct way to conduct equilibrium scaling of linear/integer/MIP program

I would like to scale my linear/integer program and also mixed-integer program using the equilibrium scaling method. I have worked on two research papers and one research book. However, they did the ...

1
vote

0
answers

28
views

### Linear programming robustness to input perturbations

I'm running a linear program whose parametrization depends on the output of a neural network. I was wondering if there exist results on how robust linear programs are towards perturbations in their ...

1
vote

1
answer

100
views

### How to maximise infinity norm of $x$ with constraint $Ax \le b$ using linear program? [closed]

I want to maximise the infinity norm of $x$, subject to constraint: $Ax \le b$. I think you can use a linear program to solve this, but how do you go about formulating it?

0
votes

0
answers

43
views

### Explicit equation for border of the Minkowski sum of sets

Assume we have sets of the form
$$
M_j = \{x\in\mathbb{R}^d : f_j(x) \le 0,x \ge 0\}
$$
where $x\ge 0$ means $x_i \ge 0 \quad \forall i=1,\dots, d$.
Goal
I am looking for an (explicit) representation ...

1
vote

0
answers

77
views

### Solution of a simple optimization problem

Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem?
\begin{align}
\min_{\mathbf{...

0
votes

0
answers

21
views

### Does the best stochastic stationary policy has the same optimal cumulative reward of an finite horizon MDP as a deterministic stationary policy?

I have this question when reading Gergely et al (2014)'s paper.
Let me define the question.
Definition: A online learning in MDP problem up to time $T$ consists of $(S,A,P,d_1,R)$
$S$: state space. $...

0
votes

0
answers

50
views

### The best unitary matrices that approximate a matrix product

Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...

0
votes

0
answers

13
views

### Calculating lower bounds for optimal tours via approximate tours

Let $T=\lbrace t_{i,\pi(i)}\rbrace\subset E,\ S=\lbrace s_{ij}\rbrace =E\setminus T$ denote the set of tour edges, resp. of tour "secants".
Let $\lbrace x_{i,\pi(i)}\rbrace \in \lbrace 0,1\...

1
vote

0
answers

22
views

### How to chose the start vector for the MTZ variables

In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ ...

0
votes

0
answers

29
views

### Convergence rate for gradient descent approximation algorithms for linear programming

Consider a canonical form for linear programming
$$\max_{x} c^Tx \quad s.t. \quad Ax\leq b $$
where $A\in \mathbb{R}^{m\times n}$.
If a suboptimal solution is acceptable instead of an exact solution, ...

1
vote

0
answers

72
views

### Drawing a 3D object in a 3D environment, and converting to math [closed]

So I have been granted a free time and I want to work on a project but first I had to research.
As we know, lines have infinite points, and with lines, we can create infinite shapes. I want to let ...

0
votes

0
answers

42
views

### How to find a set given its support function

Let $\mathcal{U}$ be a convex and compact set. Its support function is defined as $\delta^*(v|\mathcal{U})=\sup_{u\in \mathcal{U}} v^T u$. Assume that we are given the support function $\delta^*(v|\...

0
votes

0
answers

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

0
votes

0
answers

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

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

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

0
votes

1
answer

40
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

70
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

15
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

33
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

25
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

73
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

124
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

71
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

116
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

106
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

44
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

79
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

71
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

97
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

75
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

80
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

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

1
vote

1
answer

63
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

71
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

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

0
answers

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

0
votes

1
answer

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

1
answer

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

3
votes

0
answers

71
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

148
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}\...

1
vote

1
answer

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