Tagged Questions

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.

170 views

Consistency of a system of linear equations

I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...
270 views

Totally Uni-modular Matrices

A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...
274 views

Here is a curiosity question (motivated by the recent revamp of ranked-poset routines in Sage). Let $P$ be a finite poset. We look for a family $\left(a_p\right)_{p\in P}$ of real numbers summing up ...
288 views

Network flows with capacities on pairs of edges

Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$. Now add edge-pair ...
147 views

Continuity of Lexicographic Minimum Solution of a parametrized LP problem

Given a parametrized LP problem find x, that minimizes F*x such that Ax <=Bt+D where t is a parameter. And suppose C(t) is a set of all optimal solutions of LP with parameter t. Let x_L(t) be ...
450 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 ...
183 views

Covering max flow arcs by arc disjoint paths

Let $(N,A,s,t,u)$ be a network with node set $N$, arc set $A$, source $s\in N$, sink $t\in N$ and capacity vector $u\in\{1,2,\ldots,T\}^A$, and let $x=(x_a)_{a\in A}$ be a maximum $(s,t)$-flow. Is it ...
213 views

Is the Simplex Method still polynomial when all inequalities are through the origin?

Hello, I want to solve a linear program using the simplex method, and I know that all my inequalities will pass through the origin (therefore, either my initial solution of (0, ... , 0) is optimal, ...
583 views

I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a more basic ...
243 views

Checking if one polytope is contained in another

Hi, I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other. At the moment I am ...
109 views

Design constraint systems over the reals

This question is inspired by the discussion at this problem. Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called ...
863 views

how to model a linear program with step-like cost function in the objective

I have a large linear program with the following details. d1 to di are the variables, where di is an integer. The constraints are a series of inequalities of the form d1 < d3 < d7 < d23 ...
1k views

How do you tell if a system of linear inequalities has a solution?

A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.
1k views

0,1 solution to system of linear integer equations.

I have the following problem: $A x = b$ where $A, b$ - $m \times n$-maxtrix and $m$-vector of nonnegative intgers (respectivelly). $x \in \{0,1\}^n$ - vector of binary variables, which need to be ...
189 views

Could SVD be used to optimize the partial inner-products?

Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with $m-$dimensional coordinates in ...
282 views

Does the Hirsch conjecture hold for $n < 2d$?

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 ...
1k 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 ...
1k views

Closest 3D rotation matrix in the Frobenius norm sense

Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm: $$\|R-M\|_F$$ Is there a closed form solution for $R$, or is it ...
190 views

678 views

Can one efficiently optimize over the inverse of matrix?

Hello, I have the following problem: Find a non-negative matrix $L$ (i.e. $L_{i,j} \geq 0$ for all $i,j$), $L \neq I$ so that $A(I-L)^{-1}y \geq 0$ (the inequality must hold for each component), ...
113 views

sparsest cut always has solution

Hi! How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset. Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't ...
241 views

Approximate Set Cover Problem by Rounding

Here is the simple algorithm for approximating set cover problem using rounding: Algorithm 14.1 (Set cover via LP-rounding) Find an optimal solution to the LP-relaxation. Pick all sets ...
106 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 ...
385 views

Need help to find an efficient algorithm for the following problem!

Consider $x$ an n-dimensional vector with $x_i$ is integer in the range $[0 \dots k], k\in N$. Given $A_{n\times n}$ is the covariance matrix of $x$. $u$ is a given n-dimensional vector of real ...
254 views

Lovasz theta function - uses

Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?
288 views

Partially optimal solutions in integer linear programming

Linear programs with a totally unimodular system matrix are known to have an optimal integer point. They are therefore solvable via relaxing the integer constraints to intervals. An other interesting ...
595 views

Algorithm for the intersection of a vector subspace with a cone of non-negative vectors

Hi, I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
473 views

Guessing game with guess cost

This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. ...
Please forgive me if this is easy for some reason. Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$. I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ... 0answers 245 views Linear complementarity problem: principal pivoting algorithm I'm trying to implement the "Dantzig; van de Panne and Whinston" principal pivoting algorithm for solving symmetric positive semi-definite LCPs from "The Linear Complementarity Problem" book ... 1answer 319 views Mathematical Programming with other Algebras than Linear Linear Programming is strongly entwined with linear algebra, as are many of its generalizations under the heading of mathematical programming / convex optimization. What analogies are there for ... 2answers 2k views Linear programming - uniqueness of optimal solution Is it possible to build such an objective function for a given set of constraints, so that there will be only one optimal solution? My general problem is to get any vertex of a polytope formed by a ... 3answers 2k views Random Sampling a linearly constrained region in n-dimensions… Hi, So here is my problem: Given a nonlinear, discontinous, cost function$f(x_1,x_2,..,x_N)$along with linear constraints$x_n \ge 0, \forall nx_n \le c_n$and$\sum_{n=1}^N x_n = 1$find an ... 0answers 180 views Number of breakpoints in parametric maximum flow problems The parametric maximum flow problem can be formulated as $$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right),$$ where all$c_{ij}<0$(so that ... 2answers 3k views Linear program to maximize the minimum absolute value of linear functions ? I'd like to compute$\max_{x,t} t$such that$\forall i$,$t < a_i + |x - b_i|$. where$a_i,\ldots, a_n$and$b_1,\ldots,b_n$are fixed and$x \in [0,1]$. Can this be solved with a linear ... 5answers 999 views Circumference of convex shapes Here is a puzzle I found in "Mitteilungen der DMV" (roughly "Letters of the German Society of Mathematicians") issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ... 0answers 184 views A polytope associated with the Hadamard Transform In an investigation of whether or not a subset$V$of "Hamming Space"$M_n = \mathbb{F}_2^n$is a tile (i.e. whether$M_n$can be written as a disjoint partition of translates of$V$) in ... 0answers 604 views Infinite Linear Programming I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility ... 1answer 4k views Detection of Redundant Constraints Suppose I pose the following query to a constraint logic programming system: ?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3. Are there systems that would recognize the last inequality as ... 2answers 450 views Continuous Transportation Problem Hi all, I'm trying to formulate an infinite linear program to prove optimality (via duality) for the Continuous Transportation Problem, e.g. the Kantorovich-Wasserstein distance. This is the ... 2answers 245 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 ... 1answer 995 views solving multiple linear programming problems with the same set of constraints Hi, I need to solve a set of linear programs of the form: Problem$i$:$\quad \max c_i \cdot x$s.t.$ A x \leq b$. The$c_i$'s are different vectors so each problem has a different objective ... 2answers 1k views The cone of positive semidefinite matrices is self-dual? (reference needed) I'm seeking a reference for the following fact. The cone of positive semidefinite matrices is self-dual (a.k.a. self-polar). This result is relatively easy to prove, has been known for a long ... 1answer 180 views Model for shipping widgets in an optimal way I am a programmer and have the following requirement. We are trying to figure out the optimal way to ship widgets. Below is the scenario: We need to ship 1,000,000 widgets We have two different ... 2answers 510 views Set Cover:Greedy vs LP Hi Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches? thanks 1answer 272 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 ...
Given a sum of $l$ integers $r_1+...+r_k+...+r_l$ and an integer $t$. Find indices $1 < p_1 <...< p_h <...< p_{t-1} < l$ such that in sum ...