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.

learn more… | top users | synonyms (1)

4
votes
1answer
133 views

Uniform sampling from general simplex with a twist

This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange. Given $0\leq a_1\leq\dots\leq a_D\leq1$ (all strictly positive), I want to draw points ...
1
vote
1answer
40 views

convert absolute form into linear programming problem [closed]

I would like to convert this problem into a Linear Programming Problem : $\min |x|+|y|+|z|$ subject to $x+y \leq 1$ $2x+z=3$. The solution to this problem is given chapter and here. But I still ...
4
votes
1answer
134 views

Existence of Nonnegative Solutions of Linear Systems of Equations and Inequalities with particular constraints

Suppose we have an $n \times m$ nonnegative matrix $A$, where each row sums to $1$. I wonder whether there exists an $m \times n$ nonnegative matrix $X$ that satisfies the following constraints: ...
2
votes
1answer
488 views

optimization of inverse matrix with constraint on matrix elements

everyone! I have this optimization problem with constraint. $D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter. $x$ and $v$ are two known p-dimensional vectors. The ...
2
votes
0answers
47 views

Combination of certain linear-programming topics new?

Consider the combination of the following topics, aimed at a future book on Linear Programming: Generalization of certain parts of the polyhedron theory and of the Simplex Algorithm to arbitrary ...
1
vote
0answers
26 views

Maximize discrete harmonic function at given point

Let $n>0$, and let $S_n$ denote the discrete square $S_n=[|-n,n|]^2$ (so $S_n$ has $(2n+1)^2$ elements). Let $K_n$ denote the set of four corner points $\lbrace (\pm n,\pm n)\rbrace$, and $C_n=S_n\...
1
vote
0answers
31 views

Practical application of envelope theorem for linear programs

Assume that we have solved a (standard) linear program $$ \text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0, $$ and would like to know how sensitive is the optimal ...
0
votes
0answers
13 views

Drawbacks of avoiding crossover after barrier solve in linear program

I am running a large LP (approximately 5M non-zeros) and I want to speed up the solving process. I tried a concurrent solve to test which algorithm solves my problem the quickest and I found that the ...
0
votes
0answers
35 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 ...
2
votes
2answers
84 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^*$ ...
4
votes
2answers
522 views

Bounding the minimal maximum norm of a solution of a linear system.

I would be grateful for pointing me out a reference to some general bound on the $\ell_{\infty}$ norm of a solution of a linear system. To be specific, suppose that we have an underdetermined linear ...
25
votes
6answers
5k views

How to find a closest integer point to intersection of two lines?

Here's a question that originates from StackOverflow (and the SO crowd isn't really qualified to solve it). We're given two lines on the plane, specified by equations ($a x + b y = c$) whose ...
1
vote
0answers
40 views

Separation on discrete set

Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$. Define linear functions $f(x)= a_1x_1+ \...
0
votes
0answers
17 views

Finding orthogonal basis with constraint

Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$ with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$. And is there any condition on $V_i,i\leq ...
2
votes
0answers
42 views

Existence of probability distribution satisfying upper/lower bounds on events

Suppose we have a finite sample space $S$ and some events $A_1, \dots, A_k \subseteq S$. We would like to put a probability distribution on $S$ so that no element has probability greater than a ...
5
votes
2answers
421 views

Multiplicative gradient descent?

The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$? I know ...
2
votes
1answer
65 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 ...
4
votes
0answers
646 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 ...
0
votes
0answers
68 views

Optimization with vectors

I am trying to solve the following optimization problem as a small part of a research project, and I do not know if there exists closed form solutions. My linear algebra is very rusty and I am looking ...
1
vote
1answer
193 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 ...
0
votes
0answers
51 views

About identifying a few diagrams

Please have a look at these beautiful seminar slides, https://math.berkeley.edu/~bernd/coimbra1.pdf Can someone kindly identify the algebraic description of the spectrahedron that is drawn on slide ...
4
votes
0answers
137 views

Closed-form solution of a linear programming question

Among all the probability matrices \begin{equation*} P = \left(\begin{array}{cccc} p_{00} & p_{01} & \ldots & p_{0,J-1} \\ p_{10} & p_{11} & \ldots & p_{1,J-1} \\ \vdots & \...
1
vote
1answer
113 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,...
0
votes
1answer
112 views

Convert general optimization problem to LP problem

I am trying to convert the following problem into a linear programming problem: There are $M\times N$ matrix $T$ of real numbers between 0 and 1 and $N\times 1$ vector $w$ of real numbers between 0 ...
0
votes
1answer
101 views

Is the linear production game a convex game?

In cooperative game theory, the linear production game (LPG) is defined by letting the characteristic function have the form of a linear programming problem. Does anyone know if the LPG is a convex ...
0
votes
0answers
29 views

Maximisation of a discrete linear function

I am trying to maximise the function $$ Q=\sum_i{\alpha _{i}x_{i}} $$ subject to the constraint $$ W<=\sum_i{\alpha _{i}w_{i}x_{i}} $$ By changing $\alpha _{i}$ subject to $ 0<=\alpha _{i}<=1$...
0
votes
0answers
27 views

Equivalence between multiclass SVMs, power diagrams, and constrained $k$-means

Apologies in advance for the long post: Suppose we have a collection of points $\mathbf{p}_1,\dots,\mathbf{p}_n$ in $\mathbb{R}^d$, and we consider the following three ways of partitioning these ...
3
votes
6answers
1k 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 ...
1
vote
1answer
66 views

Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces

Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by $$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$ $$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$ I wish to find their convex hull, that is a ...
0
votes
0answers
33 views

Linear Program for Single Source Shortest Paths Tree

This question originates in quick, however wrong, idea to calculate a shortest paths tree in the presence of negative cycles. The essential motivation was that a linear program would determine binary ...
2
votes
0answers
111 views

Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function. The answer ...
1
vote
3answers
2k views

How to solve Linear Programming problem with tighter Integer Programming constraints

I want to learn a bit about Linear Programming. After some research, I decided to solve the Cutting Stock problem as an example to learn. After doing some more research, I feel like I finally ...
0
votes
0answers
20 views

Is there a standard technique for overdetermined homogeneous integer programming?

Given $M\in\Bbb Z^{n\times n}$ of $\mathsf{rank}(M)=r\leq n$ consider $MX=\mathsf0_n$ where $X\in\Bbb Z^{n\times 1}$ holds. We also have a $\mathsf{rank}(N)=m\leq n$ matrix $N\in\Bbb R^{m\times n}$ ...
6
votes
1answer
123 views

Algorithm that solves every Mixed Integer Linear Program (to optimality)?

Given a Mixed Integer Linear Program with rational coefficients (both for the objective functions and all constraints), is it always possible to solve it algorithmically? I know that you usually ...
2
votes
0answers
33 views

Pcross-like, nonogram-like in near-linear time [closed]

I have a problem with a puzzle game like pcross in which I have a nxn square: At any index of rows and columns I have an integer that say the maximum numbers of points that I can place in that row/col....
4
votes
1answer
169 views

Constrained optimization (QCLP) over $x$ with the constraint $x = Az$

I have a problem that looks very much like a (norm-constrained) linear program, but with an extra constraint that is unusual for me. The problem is, given a matrix $A$ and a vector $w$, $$ \min_{x \...
2
votes
1answer
87 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}\...
0
votes
1answer
56 views

When to use non-negative-least square and least-square [closed]

What are the typical case we need to use Non-negative least squares NNLS $$ ||Ax - B||^2 $$ instead of least-square $$ Ax-B$$ (or vice versa)? And is there any drawback in applying them on large $A$...
2
votes
1answer
90 views

Better alternative to solve quadratic programming for large matrices

I have the following problem. Let's say we have $x_{jk}$ it is an expression value of gene $j$ in a sample $k$. It is the average of expression levels across the cell types $s_{ij}$, weighted by ...
2
votes
0answers
67 views

Select n vectors from k vectors (in 3D) such that each component of the resultant vector >= each component of a given vector M

this was left unanswered for 1 week on MStackExchange, so I thought MOverflow would be more appropriate. Thanks :) Let $R = (R_x, R_y, R_z)$ be the resultant vector of the n vectors and $M = (M_x, ...
3
votes
2answers
299 views

ILP for minimum edge coloring problem

We know that for a graph $G=(V,E)$, minimum edge coloring is a coloring of $E$, i.e., a partition of $E$ into disjoint sets $E_1, E_2, \dots, E_k$ such that, for $1 \leq i \leq k$, no two edges in $...
0
votes
0answers
70 views

Is there a space in which the $\vec a$ in $\sin(a_1\cdot x)+\sin(a_2\cdot x)$ is linear?

Suppose one has equations of the form $\sin(a_1\cdot x_i)+\sin(a_2\cdot x_i)=y_i$ for $i = 1, \dots, n$ (there are also amplitudes and phase shifts, but let's ignore these for now). I want to solve ...
3
votes
0answers
134 views

Testing if a point is inside a convex polytope formed by halfspaces in n-dimension

Assume we have a convex polytope that is formed by the intersection of $k$-halfspaces in $\mathbb{R}^{n}$. $$ a_{0,0}x^{n-1} + {a}_{0,1}x^{n-2} + ... a_{0,n-1} \leq 0 $$ $$ a_{1,0}x^{n-1} + {a}_{1,...
0
votes
1answer
60 views

Introducton books for ‎$\frak{E}_p(I)$

Are there any good books different from abstract harmonic analysis by hewitt to study ‎$\frak{E}_p(I)$. where ‎$\frak{E}_p(I)$ is: ‎Let $I$ be an arbitrary index set‎. ‎For each $i\in I$ let $H_i$ ...
4
votes
0answers
48 views

How does one go from convexity to submodularity?

If I have a function which is convex in the hypercube, $[-1,1]^n$ then when would it imply that its restriction to $\{-1,1\}^n$ is submodular? It would be helpful is someone can share some specific ...
1
vote
1answer
72 views

approximate diameter of polytopes in high dimensions

I just came across the following problem: Let us consider the unit corner of the n-cube $$ \Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 \...
2
votes
0answers
85 views

Listing all Lattice Points in a Box

Let $B := [-1,1]^n$ be an $n$-dimensional box. Moreover, let $v_1,\ldots,v_n \in \mathbb{R}^n$ form a basis of $\mathbb{R}^n$, where the entries of the $v_i$ are explicitly irrational. We can assume ...
3
votes
2answers
134 views

Has anyone developed a technique to generate a polytope given (possibly redundant) inequality constraints? [closed]

I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm just trying to find the vertices for a feasible region, given a set of inequality ...
1
vote
0answers
69 views

Finding all feasible solutions

Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, 1\}...
1
vote
0answers
61 views

Finding optimal linear transformation for intersection of convex polytopes

I previously posted this on MathSE and am now trying here. I have the following situation, as shown in the following diagram: $W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue)...