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.

Filter by
Sorted by
Tagged with
-1
votes
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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$? ...

1
2 3 4 5
8