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
2 votes
1 answer
297 views

existence of l1 embedding using LP feasibility

hello Let (A, d) be an n-point metric space for $t \geq 1$,the task it to find an integer $m$ and an embedding $f : A \rightarrow R^m$ s.t. $\forall x,y \in A$ : $d(x,y) \leq d_1(f(x), f(y)) \leq t*...
user695652's user avatar
2 votes
1 answer
1k views

Linear Programming Cost Function [closed]

I need to add the following to my LP problem: If the amount of workers hired in period $t$ ($H_t$) is higher than 25, the hiring cost is only 1 instead of 1.2. Example: if 30 workers are hired in ...
Bas Timmermans's user avatar
2 votes
1 answer
200 views

Is matrix B obtained from matrix A?

Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
eternity's user avatar
2 votes
1 answer
450 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$, ...
Mario Giambarioli's user avatar
2 votes
1 answer
773 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 ...
Davide Papapicco's user avatar
2 votes
1 answer
217 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-...
Davide Papapicco's user avatar
2 votes
1 answer
240 views

Does quantifier elimination help here?

Suppose we have a quantified linear program $$\exists z_1,\dots,z_{poly(n)}\in\mathbb R$$ $$\exists u_1,\dots,u_n\in\mathcal P\cap\mathbb R^m$$ $$\forall v_1,\dots,v_n\in\mathcal P\cap\mathbb R^m$$ $$...
VS.'s user avatar
  • 1,816
2 votes
2 answers
394 views

Perturbation of Linear Programs

Consider the linear program, $$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & Ax \leq b\\ & x \geq 0\end{array}$$ I want to study the sensitivity of the optimal $x^*$ ...
rajatsen91's user avatar
2 votes
1 answer
183 views

How can I find the maximum value of this function?

For given values of $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$, how can I find the value of: $$ \max_{x \in [0,1]^n} \|Ax+b \|_1 $$ Or is this problem NP-hard?
OleS's user avatar
  • 23
2 votes
1 answer
672 views

Why does the LP Formulation of the MST Problem need Topology Constraints?

I am looking for an example that demonstrates the necessity of either subtour-elimination or of connectivity constraints in the LP formulation of the MST In the internet I only could find the LP ...
Manfred Weis's user avatar
  • 12.6k
2 votes
3 answers
727 views

Reference Request for Integer factorization with LP/ILP

Have there been attempts to factor integers with Linear Programming? Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...
Manfred Weis's user avatar
  • 12.6k
2 votes
1 answer
1k views

Finding a point farthest away from $k$ points in a polygon

There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized. ...
marc's user avatar
  • 57
2 votes
1 answer
815 views

Algorithm for satisfiability of inequalities.

I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$. In ...
Mark T's user avatar
  • 85
2 votes
2 answers
2k views

Solving a system of equations/inequalities that have trigonometric functions on the left-hand side

Is there any known (symbolic) method that solves a system of equations/inequalities that have trigonometric functions on the left-hand side of the system? Ex) Find $x,y,\theta \in \mathbb{R}$ that ...
SCL's user avatar
  • 23
2 votes
1 answer
126 views

Are there intuitive/classically algorithmic analogues to Semidefinite programs on networks?

Many network optimization algorithms, including shortest path, push-relabel, augmenting path, etc, actually have an interpretation in terms of linear programming. A famous application of semidefinite ...
DoubleJay's user avatar
  • 2,353
2 votes
1 answer
111 views

Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?

According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard. However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
Makogan's user avatar
  • 123
2 votes
1 answer
56 views

Counting the number of pair of d-uplets with upper bounded distance

Consider two d-uplets $u = (u_1,...,u_d)$ and $v = (v_1, ..., v_d)$ both living in $\mathbb{N}^d$ with $d$ a positive integer. They both verify $$(*) \sum_{i=1}^d u_i = \sum_{i=1}^d v_i = k$$ with $k$ ...
Ludwich's user avatar
  • 55
2 votes
1 answer
330 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 ...
Jochen Wengenroth's user avatar
2 votes
1 answer
639 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 $\...
Titouan Vayer's user avatar
2 votes
1 answer
498 views

Intersection of a vector subspace with a cone

Given a set of vectors $S=\{v_1, v_2,...,v_d\} \subset \mathbb{R}^{N}, \, N>d$, is there any algorithm to decide if there exist a vector with all coordinates strictly positive in the generating ...
Marcelo Pedro's user avatar
2 votes
1 answer
466 views

Feasibility Mixed integer Linear programming with quadratic constraints?

Consider the mixed integer program $$Ax\leq b$$ $$By\leq c$$ $$\begin{bmatrix}x&y\end{bmatrix}C\begin{bmatrix}x\\y\end{bmatrix}+D\begin{bmatrix}x\\y\end{bmatrix}\leq d$$ where $x$ are integer ...
Turbo's user avatar
  • 13.6k
2 votes
2 answers
2k views

Linear programming with infinitely many constraints

I wish to study the following linear program $$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathrm x \geq 0\...
user3433489's user avatar
2 votes
1 answer
1k views

Complementary slackness for approximately optimal Dual solution

Given a Primal LP (P) and it Dual LP (D) we know that the optimal solutions to P ($x_{opt}$) and D $(y_{opt})$ satisfy complementary slackness condition, i.e. under optimal solutions either a ...
Soumya Basu's user avatar
2 votes
1 answer
146 views

Minimum cover for sets in which each element appears in exactly 2 sets?

Is there an algorithm for finding minimal covers of a set of sets in which each element of the universe appears in exactly 2 sets? I realize that LP relaxation approximates this to within a factor of ...
Victor Rielly's user avatar
2 votes
1 answer
512 views

Complexity of Deciding Feasibility of a system of linear inequalities over restricted variables

I am working out an interesting problem and would like some help with this particular sub problem: Suppose we have a matrix $ M =\left\lbrace a_{ij}\right\rbrace $ of size $n\times m$ where $ a_{ij}\...
Alex's user avatar
  • 21
2 votes
1 answer
272 views

An optimization problem in complex space

Consider the following optimization problem $$ \min \| \textbf{Ax-B}\| $$ $$ s.t.|x_i|=1,i=1,...,n $$ where $\textbf{x}\in \mathbb{C}^{n}$ is the optimization varaible, $x_i$ is the $i$-th ...
Denny's user avatar
  • 21
2 votes
1 answer
132 views

Find base of kernel with as many 0 as possible

I have a 400x132 rectangular matrix with only 0 and 1. I am looking for the linear combinations of the columns of the matrix that sum to 0. For example C1 + C2 - C3 = 0. I want to find the linear ...
Robert's user avatar
  • 83
2 votes
1 answer
186 views

Optimization problem whose cardinality never exceeds 7 for some reason

I am working on a problem in which I have a collection of $n$ points, $x_1,\dots,x_n$, in the plane, as well as a positive definite matrix $\Sigma$ and another point $\mu$ in the plane. I am trying ...
Nathaniel V. Barnes's user avatar
2 votes
1 answer
224 views

Arrangements of hyperplanes

Fix $n>0$ and $X\subseteq\mathbb{R}^n$. A function $f:X\longrightarrow\mathbb{R}$ is linear if it is of the form $$ f(\bar{x})=a_1x_1+\ldots+a_nx_n+b $$ for some $a_i,b\in\mathbb{R}$. Suppose we ...
Gabe Conant's user avatar
  • 3,204
2 votes
1 answer
123 views

Fastest 'Oracle' Algorithm for satisfying a single linear constraint on a convex set?

In this paper by Arora, Hazan, and Kale (http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf) a method is given for using the Multiplicative Weights Update algorithm to quickly solve Linear Programs ...
Sam Stern's user avatar
  • 121
2 votes
1 answer
126 views

Is it possible to represent non-linear ranking type constraints as equivalent linear constraints?

I have formulated a linear program with binary indicator variables $z_i(a)$ which is equal to $1$ if the $i^{th}$ document is of rank $a$ and $0$ otherwise. The other variables in the linear program,...
stressed_geek's user avatar
2 votes
2 answers
400 views

Maximization of a matrix product by iterative methods

This might not be very difficult, but I think I may have gotten a little confused. Suppose we are given a matrix A, and would like to find the vector x of modulus 1 which maximises the product xt A x ...
BharatRam's user avatar
  • 939
2 votes
1 answer
222 views

Solving linear programming without solving linear programming

Let $v_1, \cdots, v_n$ be vectors in $\mathbb R^k$, and let $M$ be the Gram matrix of them. It's possible to determine from $M$ and $k$ whether the only vector that has nonnegative inner product with ...
LeechLattice's user avatar
  • 9,411
2 votes
1 answer
514 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?
Minute street's user avatar
2 votes
1 answer
136 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 ...
David T.'s user avatar
2 votes
1 answer
255 views

What optimization problems have solutions with few nonzeros?

Consider the following optimization problem, with $n$ variables and $m$ linear constraints: \begin{align} \text{maximize} && c_1 x_1 + \cdots + c_n x_n & \\ \text{subject to} && a_{...
Erel Segal-Halevi's user avatar
2 votes
1 answer
88 views

Linear program with one quadratic condition convex in domain of interest polynomial time solvable?

$c\leq xy$ is not a convex condition. However we know $c\leq xy$ is convex in domain $x,y>0$ in $\mathbb R^2$ for any fixed $c\in\mathbb R$. Is $c\leq x_1y_1+\dots+x_ny_n$ with $0\leq x_1,\dots,...
Turbo's user avatar
  • 13.6k
2 votes
2 answers
371 views

Is this a linear optimization problem? $Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative

$Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative. What should $A$ satisfy to guarantee the equation set have only zero solution?
ZhongHua Yan's user avatar
2 votes
1 answer
129 views

Fast algorithm for large-scale, asymmetric transportation linear program

I have a large-ish instance of a transportation problem that is very asymmetric, say of dimensions $100\times10000$. I am currently solving it with a stock LP solver, but obviously something like the ...
Tom Solberg's user avatar
  • 3,910
2 votes
1 answer
462 views

Under what condition does Courant–Fischer–Weyl min-max principle hold in general?

From Wikipedia: Let $A$ be an $n \times n$ Hermitian matrix. As with many other variational results on eigenvalues, one considers the Rayleigh–Ritz quotient $R_A : \mathbf C^n \setminus \{0\} \to \...
Fraïssé's user avatar
  • 155
2 votes
1 answer
165 views

Maximization of Binary Multilinear Fractional Function

Problem: Let $a_{i,j}$, $b_{i,j}\in\mathbb{R}$ for all $(i,j)\in\left[m\right]^2$ such that $a_{i,j}=a_{j,i}$ and $b_{i,j}=b_{j,i}$. Let $z_k\in\{0,1\}$ for $k\in\left[m\right]$. We wish to maximize, ...
Joseph Zambrano's user avatar
2 votes
1 answer
512 views

Integer programming and Groebner basis

I enjoyed reading different papers about using Groebner basis to solve integer programming. Is there any literature about the complexity and/or comparison with other (more classical) methods like ...
teller's user avatar
  • 337
2 votes
1 answer
3k views

max-flow at max-cost

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
lrleon's user avatar
  • 121
2 votes
1 answer
224 views

Algorithm to find the vertices of the equidistant lines between N closed polygonal lines

I have a set $\{C_1, C_2, \ldots, C_N\}$ of $N$ nonintersecting closed piecewise linear curves on the Euclidean plane. For every point $x \in \mathbb{R}^2$ we say it belongs to a territory serviced by ...
vkrouglov's user avatar
  • 329
2 votes
1 answer
384 views

Network flows with shared capacities

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as: $$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$ where $f(1, 2)$ denotes the flow through arc $(1, 2)$....
robertdg's user avatar
2 votes
1 answer
104 views

Standard names and methods for this type of fitting minimization

In material science research, we have come across the following type of problem. Given a m by n matrix A, a m vector b, and error tolerance $\varepsilon$, we want to do this minimization $$\eqalign{ ...
user40780's user avatar
  • 867
2 votes
1 answer
290 views

books on very large scale linear optimization

Recently in my material science research, I have encountered problems of very large scale linear optimization. I read the introductory book "Introduction to Linear Optimization (Athena Scientific ...
user40780's user avatar
  • 867
2 votes
1 answer
130 views

Integer point in a non-empty polytope

I have a high-dimensional, non-empty polytope $Ax\geq b$ sitting inside the cube ($0\leq x_i \leq 1$). Is there any general theory or technique to show that this polytope contains an integer point, ...
Richard's user avatar
  • 243
2 votes
2 answers
704 views

Finding the maximum of a multivariate polynomial of degree one

I need to find the global maximum of the function \begin{align} f\left(x\right) & = p_1 \max\left(\sum a_{1i} x_{1i}, \sum b_{1i} x_{1i}\right) - \sum c_{1i} x_{1i} \\ &+\ldots \\ &+ p_n ...
user avatar
2 votes
2 answers
731 views

Survey on Compared Running Time: Ellipsoid Method vs. Simplex Method

If you look through papers on the Ellipsoid Method, there is a large agreement, that the Ellipsoid Method, although theoretically polynomial, is in practice way slower than the Simplex Method. ...
Skrodde's user avatar
  • 329

1 2 3
4
5
10