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)

1
vote
1answer
339 views

Computation of extreme rays of rational polyhedral cones - Hemmecke's project and lift algorithm

I am working on an implementation of Raymond Hemmecke's algorithm for finding generating sets of cones: http://arxiv.org/abs/math/0203105 Unfortunately I am struggling to make the algorithm work on ...
2
votes
0answers
66 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, ...
2
votes
0answers
94 views

How to solve the following generalized quadratic programming problem [closed]

I want to solve a generalized form of a quadratic programming problem $$\min_x \left(\sqrt{x^TPx}+\sqrt{x^TQx}\right)^2+c^Tx$$, $$\textrm{ s.t. } Ax\le b.$$ Here, $P$ and $Q$ are both positive ...
2
votes
1answer
142 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)$....
6
votes
0answers
118 views

A specific case of the $p$-center problem

Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...
0
votes
1answer
92 views

accelerate convex optimization by proximal projection

I am using level method to solve non-smooth convex programming problem (where the objective function is given by an oracle from another program ): http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf ...
5
votes
1answer
354 views

Examples of Polyhedra with Large Shadows

Let $P \subseteq \mathbb{R}^n$ be a polyhedron described by $\mathcal{O}(n^{c_1})$ inequalities, where $c_1$ is a constant. Moreover, let $M\colon P \to \mathbb{R}^2$ be a linear mapping. I'm looking ...
1
vote
1answer
144 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 ...
5
votes
1answer
434 views

Algorithm to minimally connect line segments in Euclidean plane

Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?" More formally and generally, what I'm looking for ...
7
votes
1answer
188 views

A polytope with a bound on the sum of any $k$ variables

Let $2\le k\le n-1$ and define the polytope $$P_k(n) = \lbrace (x_1,\ldots,x_n) \in \mathbb{R}^n : -1\le x_{i_1}+\cdots +x_{i_k} \le 1 \text{ for all } 1\le i_1\lt\cdots\lt i_k\le n\rbrace.$$ There ...
2
votes
1answer
92 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{ ...
7
votes
2answers
195 views

Are sums of 0-1 Pareto efficient vectors Pareto efficient?

Does there exist $m,n\ge1$, an $m \times n$ matrix $A$, and a vector $x \in \mathbb{R}^n$ such that: The entries of $A$ are $\in \{0, 1\}$. For all pairs of columns $u, v$ of $A$ the entries of $u - ...
0
votes
2answers
106 views

Inner Product of Given Sum Positive Sequence

Let $$A = \Big\{(a_1,a_2,\dots)\ \Big|\ a_i\ge 0, \sum_{i=1}^\infty a_i=1\Big\},$$ $$v(x)=\sup\left(\bigg\{\sum_{i=1}^\infty a_ib_i\ \bigg|\ (a_i)_{i=1}^\infty,\, (b_i)_{i=1}^\infty \in A,\,\sup\...
2
votes
1answer
163 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 ...
0
votes
1answer
2k views

Convert linear programming problem into its standard form [closed]

all, I met a question that, the cost function of the linear programming problem is a function with absolute value. Here is the problem: min 3x1+|6x2+3| st. |x1+4|+|2x2|<=3 How can I deal with ...
0
votes
1answer
363 views

Linear programming with exponentially many constraints and variables [closed]

From class, I learnt that problems like traveller salesman have a Linear programming representation with exponentially many constraints. Using method of separation, this problem is solved rather ...
1
vote
2answers
128 views

investigating positivity/negativity of a function [closed]

I'm investigating if and how the positivity or negativity of a multivariable function can be proved. Consider $y_{1},y_{2},y_{3}\in\mathbb{R}$ and the following function $$f\left(y_{1},y_{2},y_{3}\...
0
votes
1answer
95 views

Generalized assignment problem with no integrality gap

Suppose I am solving the generalized assignment problem, so that I am given matrices $U$ and $W$ and a vector $c$ (all three of which have, say, positive entries), and I want to solve $$\text{...
3
votes
2answers
290 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 $...
5
votes
2answers
411 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 ...
6
votes
1answer
304 views

Speed up Linear programming

I have a linear programming problem like this: minimize $c^t X$ under the constraint that $AX \ge b$. I will need to solve this linear programming problem online many times. I need it to be as fast ...
2
votes
1answer
94 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 ...
2
votes
2answers
129 views

Boundedness of ratio of linear functions

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; \...
0
votes
1answer
117 views

Solution of infinite dimension linear system

Suppose that ${a_n}$ and $b_n$ is decreasing sequence such that $a_0=A$, $lim_{n->\infty}a_n=0$ and $b_0=B$, $lim_{n->\infty}b_n=0$. For fix n, we can construct n dimension linear equation ...
2
votes
2answers
287 views

convex polytope integer points

is there a simple proof for the following lemma: An unbounded convex polytope (defined by linear constraints) has either zero integer points or infinite many integer points.
1
vote
0answers
131 views

Reduce a Combinatorial problem

It is given n sets with k vectors. (k is element-wise positive or zero) Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal. What i also know but is ...
0
votes
2answers
279 views

Approximate solution to large mixed integer programming problem

What are the available approaches to find an approximate solution to a large mixed integer programming problem? I ran my problem in the Gurobi MIP solver. It can find a feasible solution in ...
1
vote
1answer
238 views

a closed form lower bound solution for linear programming

Given a linear objective function and a system of linear constraints, is there any known closed form lower bounds for it? to clearly express the problem assume that $$ z(\mathbf{a,B,c})=\mathop {\inf} ...
3
votes
1answer
330 views

Name search for special Linear Integer Program

I am looking for a name for the following question in literature! (and if you know it, then it would be great) I couldn't find it and due to wide audience here, presumably you know more. Thank you $...
2
votes
1answer
152 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 ...
0
votes
1answer
77 views

Large scale least squares of non symmetric and non square problems

Given a system like $b=Ax$ with an non symmetric and non square $A$ I would like to solve it having many elements in $x$ (lets say $10^7$). There is a large amount of algorithms for symmetric ...
1
vote
1answer
60 views

Heuristic for choosing n-vectors from n-sets

my given problem is: choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm ...
2
votes
1answer
196 views

Calculate the discrete set of points B which are in the convex hull of the set of points A

This problem is likely best described with the following picture: Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
2
votes
2answers
145 views

sensitivity analysis in conic optimization

I have a conic optimization of the form: $\min_x \langle c, x \rangle$, s.t. $Ax = b$, $x \in K$. Where $x \in \mathbb{R}^{n}$, $A$ is an $m \times n$ matrix, $b \in \mathbb{R}^m$, $K$ is a self ...
2
votes
0answers
74 views

Algorithms to find the solutions of a homogenous matrix equations for non-commutative rings

In one paper from 1980 I found a note that there are no known algorithms for solving homogenous matrix equations $x \cdot M = 0$ for matrices which elements belong to a non-commutative ring. (The non-...
1
vote
2answers
64 views

Linear Programm with matrix [closed]

Is there a name for problems like this min norm(Cx) Ax = b where C is a matrix and norm is the maximum norm. This is kind of like a linear Programm. Could this be rewritten as linear programm? Or Any ...
0
votes
0answers
189 views

Inverse problem with a rank-1 update

I hope you can help me out with this. I have to find the solution x to an inverse system $$ x=A^{-1}b $$ This inverse problem is basically a least square problem with a rank-1 update. $$ x=[uv^{T}...
3
votes
1answer
246 views

submatrix of a given size with maximum frobenius norm

Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...
1
vote
0answers
84 views

integrality of a linear program — binary equality constaints

Consider the following linear program: $\left\{ \begin{array}{l} \underset{x}{max} \;\;c^Tx\\ [I, \;B]x = \mathbf{1}\\ x\geq 0 \end{array} \right.$ where $c$ is a vector ...
2
votes
1answer
479 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 ...
24
votes
2answers
992 views

An Interesting Optimization Problem

You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
4
votes
2answers
149 views

combinatorial and linear duality

Let $S$ be a finite set, and let $W$ be a nonempty set of subsets of $S$; we will identify every subset of $S$ with its characteristic function, a 0-1 vector in $\mathbb R^S$. The combinatorial dual $\...
2
votes
1answer
74 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, ...
1
vote
0answers
65 views

Are there any known bounds on the value of solutions of linear integer programming?

Given a linear objective function and a system of linear constraints; are there any known bounds on the values of (positive) integral solutions in terms of the coefficient matrix of the constraints? ...
1
vote
1answer
2k views

Maximizing linear objective function with absolute values

This has be asked on other forums, though couldn't find authoritative answer. I have a linear program over the reals and don't want to introduce integer or binary variables. The objective function ...
2
votes
2answers
331 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 ...
1
vote
0answers
183 views

Complexity of Nested Linear Optimization

My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint: $$\max(\...
4
votes
2answers
307 views

Minimax theorem on a non convex domain

A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$: $$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in \mathcal{...
0
votes
1answer
61 views

generalization from linear programming solution [closed]

I have a series of similar linear programs that depend on an input vector $a\in A$ and whose solution is an output vector $b\in B$. I can solve them individually, but this is wasteful. I suspect that ...
6
votes
1answer
338 views

Has this generalization of a determinant (assigning multiplicities to the rows) been studied?

I'm working on some questions in tropical geometry, and my problem led me to create the following generalization of a determinant: Let $A$ be an $m \times n$ matrix with $m \le n$, and positive ...