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

395
questions

**-1**

votes

**0**answers

21 views

### Linear programming question, [closed]

enter image description here
A farmer has several hectares of land on which, corn, tomatoes, or peas can be grown. The gross income resulting from planting 1 hectare of each crop is shown below, ...

**0**

votes

**0**answers

24 views

### What is the effect of adding uniqueness constraints to linear programs

Question:
If it is known that the optimal solution to a linear program isn't unique and it is possible to enforce uniqueness by means of additional constraints, what is the impact of adding those ...

**0**

votes

**0**answers

12 views

### Constrained maximin optimisation problem

Let
i) $\mu = [\mu_1,\mu_2,\mu_3]\in\mathbb{R}^3$, such that $\mu_2 > \mu_1$, $\mu_2 >\mu_3$ fixed,
ii) $\lambda = [\lambda_1,\lambda_2,\lambda_3] \in \mathbb{R}^3$ such that $\lambda_1 \geq \...

**0**

votes

**0**answers

16 views

### Derivation of dual for infinite linear program

I'm reading the section on Linear Programming in Barbu and Precupanu's Convexity and Optimization in Banach Spaces, and had a couple of questions concerning their derivation of the dual problem for ...

**0**

votes

**1**answer

41 views

### Fractional values in linear programming

Consider the linear programming problem
\begin{align}
f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1
\end{align}where $p$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ ...

**0**

votes

**0**answers

30 views

### Sub optimal algorithm for linear programming

Consider the linear programming problem
\begin{align}
f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1
\end{align}where $c$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ ...

**2**

votes

**0**answers

44 views

### Proving the existence of a dual for an infinite linear program

I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-...

**0**

votes

**1**answer

60 views

### Maximize function on rotation matrices [closed]

Let $A$ be a fixed 3-by-3 matrix and $Q$ be a rotation matrix whose yaw, pitch, and roll angles are $\phi\in[0,\pi]$, $\theta\in[0,\pi]$, and $\psi\in[0,\pi/2]$, respectively:
\begin{equation}
Q=
\...

**0**

votes

**0**answers

20 views

### Does the polytope of solutions to this modified vertex cover LP relaxation have half-integer vertices?

Given a graph $G$, one can consider the vertex cover LP relaxation
$x_v\in\mathbb{R}$, $v\in V(G)$
$x_v\geq 0$ $\forall v$
$x_v+x_w\geq 1$ for all edges $vw\in E(G)$,
where we want to minimize
$\...

**1**

vote

**0**answers

163 views

### Minimum vertex cover and linear programming

Suppose we have a graph G. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $v_{i}...

**3**

votes

**0**answers

121 views

### A new “adversarial” Wasserstein distance?

Let us consider $\mu_1, \mu_2$ and $\mu_3$ three probability measures living on $[0,1]^{k_1}, [0,1]^{k_2}$ and $[0,1]^k$respectively, with $k_1 +k_2=k$. Let us denote by $\Gamma(\mu,\nu)$ the set of ...

**8**

votes

**2**answers

385 views

### Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?

Sphere packing problem in $\mathbb R^n$ asks for the densest arrangement of non-overlapping spheres within $\mathbb R^n$. It is now know that the problem is solved at $n=8$ and $n=24$ using modular ...

**2**

votes

**1**answer

177 views

### Odd cycle transversal

Suppose we have a graph G. Say B a fundamental basis of the cycle space of G. Say LP a linear programming problem where there is a variable for each vertex of G, each variable can take value $\geq 0$, ...

**1**

vote

**2**answers

72 views

### Integer linear programming (ILP) formulation of connectivity of induced subgraph

Can anyone assist me to find out what should be the ILP formulation of a case when I try to label vertices by say $0$, $1$ and $2$ and want the subgraph of graph $(V,E)$ made by same vertex set but ...

**1**

vote

**1**answer

70 views

### Interior point of a convex polytope

Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...

**2**

votes

**1**answer

81 views

### Sampling algorithms on convex polytopes

Let $f=\mathbf{c}\cdot\mathbf{x}$ be the optimization objective function whose parameter vector $\mathbf{x}\in\mathbb{R}^n$ is subject to the following constraints in the very well-known linear-...

**0**

votes

**0**answers

36 views

### Minimizing along independent directions, nonlinear programming

Good afternoon, I am studying the book Nonlinear Programming: Theory and Algorithms (by Mokhtar S. Bazaraa, Hanif D. Sherali, C. M.) particularly the Theorem $7.3.5$. I'm not sure I understand this ...

**0**

votes

**0**answers

43 views

### Linear programming over a permutohedron

I am trying to solve the following linear programming problem: Given two vectors $\mathbf{b},\mathbf{c}\in\mathbb{R}^n_+$, solve $$\text{minimize}~~ \mathbf{c}^T\mathbf{x}$$ subject to $$f\left(\sum_{...

**0**

votes

**0**answers

119 views

### Can we find a minimizer of this linear smooth integral functional?

Let
$(E,\mathcal E,\lambda)$ be a measure space;
$f:E\to[0,\infty)^3$ be $\mathcal E$-measurable with $\|f\|\in\mathcal L^2(\lambda)$;
$\tilde p:=\alpha_1f_1+\alpha_2f_2+\alpha_3f_3$ for some $\...

**2**

votes

**0**answers

44 views

### A linear program where coordinate descent works pretty well

I am working with a polytope $P\subset \mathbb{R}_+^n$ with the property that there are at about $n!$ minimizers of $\sum_{i=1}^n x_i$, in the following sense:
Select any coordinate $j$ and set $...

**1**

vote

**1**answer

47 views

### Perturbation of the value of a general-sum game at a equilibirium

Consider a general-sum game with $N$ players. Let $u_i(a_1, \ldots, a_N)\colon \prod_{i=1}^N A_i \rightarrow \mathbb{R} $ be the payoff of the player $i\in \{ 1, \ldots, N \}$ when each player takes ...

**0**

votes

**0**answers

28 views

### Face computation and support function minimisation of polytope projection

Let $P \subset {\mathbb R}^m$ be a convex polytope containing 0, given by system of inequalities $Ay \leq b$. Let ${\mathbb R}^n$, $0<n<m$, be a subspace of ${\mathbb R}^m$ given by first $n$ ...

**1**

vote

**0**answers

58 views

### total unimodularity of a matrix

Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...

**6**

votes

**1**answer

528 views

### Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers

Let $a(n)$ be the Dirichlet inverse of the Euler totient function:
$$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
and let the matrix $T(n,k)$ be:
$$T(n,k)=a(\gcd(n,k)) \tag{2}$$
It has been ...

**1**

vote

**1**answer

98 views

### find a PSD matrix that that verify matrices sum of equality

$A $, $ C$ $(n,n)$ are symmetric PSD matrices,
$B$ is PD symmetric matrix, and $H_i$ $\; $ $(i=[1,m])$ represent $ m $ complex matrices. $H_i$ are all one rank matrix
Our objectif is to find ...

**2**

votes

**2**answers

112 views

### Algorithm to determine if a union of half-spaces is all of $\mathbb{R}^d$

I have a collection of closed half-spaces $H_1, \dots, H_n \subseteq \mathbb{R}^d$, each given as $H_i = \{x \in \mathbb{R}^d : a_i \cdot x \geq c_i\}$ for some $a_i \in \mathbb{R}^d$ and $c_i \in \...

**0**

votes

**1**answer

116 views

### Computing discrete optimal transport

I am trying to find a combinatorial approach to solve the following optimization problem.
\begin{align}
&\max_{x_{ij}} C_{ij} x_{ij}, \\
&\text{such that},\\
&\sum_{j} x_{ij} \leq r_i~\...

**3**

votes

**1**answer

128 views

### Reference: Packing under translation is in NP

I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...

**5**

votes

**1**answer

177 views

### If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?

I have just learned that a general framework in constrained optimization is called "proximal gradient optimization". It is interesting that the $\ell_0$ "norm" is also associated with a proximal ...

**0**

votes

**0**answers

17 views

### Quantiles of the Q values of an unknown MDP

Consider an MDP with $n$ states, $k$ actions, and discount factor $\gamma \in [0,1)$. We are uncertain of its reward function $R \in \mathbb{R}^{n \times k}$ and transition function $T \in \mathbb{R}^{...

**1**

vote

**0**answers

71 views

### Can we reduce the maximization of this integral to the maximization of the integrand?

I would like to know whether we are able to reduce the following optimization problem to the pointwise optimization of the integrand (or how we can solve it otherwise): Maximize $$\sum_{i\in I}\sum_{j\...

**0**

votes

**1**answer

41 views

### Finding dual of a scheduling LP formulation

Suppose I have an LP formulation as such:
$\min\ \ \sum\limits_{i,j,t}\ w_{ij}x_{ijt} (\frac{t-r_j}{p_{ij}}+0.5)$
$\sum\limits_{i,t}\frac{x_{ijt}}{p_{ij}}=1\,\forall\ j$
$\sum\limits_{j}x_{ijt}\leq ...

**0**

votes

**1**answer

60 views

### How do I solve this integer programming problem with non convex constraints?

I am not sure if this is the right place to post this question, please point me to the correct forum if I posted in a wrong place.
I have an optimization problem like this
...

**0**

votes

**0**answers

67 views

### How can we analytically solve this max-sum-min problem?

Let $I$ be a finite set, and $A_{ij},B_{ij},x_i,y_j\ge0$. I want to find the choice of $x_i,y_j$ maximizing $$\sum_{i\in I}\sum_{j\in J}A_{ij}\min\left(x_i,B_{ij}y_j\right)\tag1$$ subject to $$\sum_{i\...

**0**

votes

**1**answer

47 views

### Variant of the linear programming problem

Good afternoon, my experience in mathematical programming is low. I would like to know if there is any general method to address the following problem:
$$\text{Minimize }\sum_{i=1}^n d_i(x_j)$$
$$s.a....

**2**

votes

**0**answers

92 views

### Generalization of Farkas' Lemma to Hermitian Matrices

I recently stumbled upon a well-known version of Farkas' Lemma which, roughly speaking, I would like to generalize from real vectors to hermitian matrices, as it seems promising for something else I ...

**0**

votes

**0**answers

28 views

### Converting a vector in a cone statement to inequality constraints

I would like to convert the following condition for $x$
\begin{align}
x = N \lambda, \lambda \geq 0
\end{align}
to a pure linear inequality form, i.e. find an $L$ and eliminate $\lambda$
\begin{...

**1**

vote

**0**answers

17 views

### Weird subspace/equality-constrained LP problem/variant of change-making problem

Assume that we have a set, $\mathscr{R}$ containing $m$-dimensional vectors. Solve
$$\sum_{i=1}^n c_i\leq\delta$$
$$\text{subject to } \sum_{i=1}^n r_i c_i=x^\prime \text{ for all }x^\prime$$
where
$0\...

**5**

votes

**1**answer

126 views

### Is Binary Integer Linear Programming solvable in polynomial time?

The paper Solving the Binary Linear Programming Model in Polynomial Time claims that Binary Integer Linear Programming is in P. However, it seems that no subsequent literature in the mainstream has ...

**1**

vote

**1**answer

312 views

### Finding the closest special orthogonal matrix in Frobenius norm sense

Given a $3\times3$ matrix $M$, if we would like to get the closest $\mathrm{SO}(3)$ matrix $R$ that minimizes
\begin{equation}
\|R-M\|_F
\end{equation}
then $R$ = $UV^{T}$ where $U$ and $V^{T}$ are ...

**0**

votes

**0**answers

21 views

### Relatively prime polytope extension complexity

What is the extension complexity of the $0/1$ vertexed polytope in $2d$ dimensions with property that integer represented by first $d$ coordinates is coprime to integer represented by second $d$ ...

**0**

votes

**0**answers

29 views

### Feasibility Criteria in Integer Linear Programming

Consider an integer linear programming problem:
For $A\in M(m, n, \mathbb{Z})$ and $b\in \mathbb{Z}^m$
find $x=(x_1,\ldots,x_n)^T\in \mathbb{Z}^n_{\geqslant0}$ such that $Ax=b$.
Sometimes one ...

**1**

vote

**1**answer

76 views

### Sufficient conditions for a system of linear inequalities to admit a solution

I am looking for sufficient conditions such that a system of linear inequalities of the type $A x >0$ admits a non-negative solution $x \in \mathbb{R}^n_+$. I know a few properties of the $m \times ...

**3**

votes

**1**answer

208 views

### Uniqueness of l1 minimization

Let $A \in \mathbb{R}^{m \times n}$.
Is it true that $$\min \limits_{Q \in \mathbb{R}^{n \times m}}|I - QA|_{\infty} < \frac{1}{2}$$ is criteria for the uniqueness of the 1-sparse solution to
$\...

**1**

vote

**0**answers

103 views

### Prove that these linear programming problems are bounded by $O(k^{1/2})$ [closed]

The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this set of linear programming problems:
$$\begin{array}{ll} \text{minimize} &...

**0**

votes

**0**answers

125 views

### What do square roots as minimums have to do with Harmonic numbers?

In an earlier question where I conjectured (and GH from MO confirmed) that the von Mangoldt function is the limit at s=1 of a certain Dirichlet series:
$$\Lambda(m)=\lim_{s\to 1+}\zeta(s)\sum_{d\mid ...

**3**

votes

**0**answers

73 views

### Uniqueness of projection under spectral norm

I am considering
$$
\min_{M\in \mathcal{M}} \|X - M\|:=x \neq 0,
$$
where $X$, $M$ are $m\times n$ matrices, $\|\cdot\|$ is spectral norm and $\mathcal{M}$ is a matrix subspace. I wonder to what ...

**5**

votes

**1**answer

174 views

### On optimal dual solutions for the minimum weight perfect matching problems in the case of metric weights

Following Lovasz-Plummer (Matching theory, North-Holland 1986, Theorem 9.2.1),
the minimum weight perfect matching problem on a complete graph
$G$ with even number of vertices and weight $w:E(G)\to
\...

**3**

votes

**1**answer

148 views

### What importance does the Hirsch conjecture have to Simplex Complexity?

The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.
After being open for decades, Francisco Santos has ...

**1**

vote

**0**answers

32 views

### Linear programming with a convergent coefficient

The following linear programming problem
$x_n = \arg\min c_n'x \mbox{ subject to } Ax<b$
has a changing coefficient $c_n$. We have that $c_n\rightarrow c_*$. What happens to the solution $x_n$? ...