The linear-programming tag has no wiki summary.

**0**

votes

**0**answers

15 views

### Bender's decomposition with overlapping y variables [on hold]

From my textbook, I learned bender's decomposition for 2-stage problems and the y variables is non-overlapping. Indeed, I wish to look into this decomposition further since it is very likely a ...

**-1**

votes

**0**answers

24 views

### Get fractional LP into canonical form [on hold]

I have the following LP problem and I would like get it into canonical form so that I can solve it for the x vector.
min(y) = sum yi/(ci-yi) , where yi = sum over j Lij * xj
st. H x = f
...

**0**

votes

**0**answers

41 views

### quadratic knacksack problem, state of art [on hold]

What is the current status to quadratic knacksack problem? Say, how many variables can the state of art solver handle? Thank you.

**0**

votes

**0**answers

22 views

### unable to use mysql for Python in mac os 10.9 [on hold]

I am very new to python and was trying to work with mysql.
I followed the below link to install the package (OS x 10.9.5)
(http://www.tutorialspoint.com/python/python_database_access.htm)
After ...

**0**

votes

**2**answers

54 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 ...

**10**

votes

**3**answers

616 views

### Deciding membership in a convex hull

Problem: Given points $u,v_1,\dots,v_n\in\mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1,\dots,v_n.$
This can be done efficiently by linear programming (time polynomial in ...

**1**

vote

**1**answer

47 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

**0**answers

85 views

### exponential columns and rows in Linear programming [closed]

In one of my previous post, I mention a Linear programming system with exponentially many constraints and variables Linear programming with exponentially many constraints and variables . It is ...

**2**

votes

**0**answers

67 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 ...

**-4**

votes

**0**answers

14 views

### Direct computation of hyperboloid-line intersection in 3d [migrated]

I was wondering if a solution to this problem that doesn't involve coordinate space transformations.
I have two points in 3d space, and am interested in locations where the difference of the ...

**0**

votes

**1**answer

49 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 ...

**1**

vote

**2**answers

116 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
...

**0**

votes

**1**answer

64 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

**1**answer

157 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
...

**0**

votes

**1**answer

402 views

### eigen-decomposition solution? is it unique?

Assume an N*N covariance matrix (Q) which is a positive definite matrix. The decoder X is assumed to be N*s, where s<=N. X is calculated to be s eigenvectors corresponding to s minimum eigenvalues. ...

**2**

votes

**1**answer

82 views

### optimization of inverse matrix with constraint on matrix elements

everyone! I have this optimization problem with constraint.
D and T are symmetric matrice, where T is known and D is the unknown parameter.
x and v are two known p-dimensional vectors.
The objective ...

**1**

vote

**1**answer

51 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 E1,E2...,Ek such that, for 1<=i<=k, no two edges in Ei share a common ...

**3**

votes

**2**answers

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 ...

**0**

votes

**1**answer

43 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
...

**2**

votes

**1**answer

99 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 ...

**0**

votes

**0**answers

59 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 ...

**0**

votes

**0**answers

26 views

### Find relationships between events

I have a set of Events $(E_i)_i$ which have a probability $(P_i)_i$.
I am able to write each event as a sum of distinct events that form a partition of the space.
My goal is to find all the ...

**2**

votes

**1**answer

67 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

**2**answers

101 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

**0**answers

60 views

### polynomial 0,1 integer programming

IS there a mathematical optimization branch that explicitly tries to optimize this (type) problem?
$$\eqalign{
& \min \cr
& \sum\limits_{i = 1}^N {(J*s[i] + {J_1}*s[i]*s[i + 1] + ...

**0**

votes

**1**answer

76 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 ...

**1**

vote

**1**answer

89 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} ...

**2**

votes

**1**answer

145 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 ...

**4**

votes

**1**answer

788 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:
\begin{equation}
\|R-M\|_F
\end{equation}
Is there a closed form solution for $R$, or is it ...

**2**

votes

**2**answers

235 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

**0**answers

119 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

**2**answers

65 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 ...

**0**

votes

**1**answer

170 views

### $\ell_o$ Minimization (Minimizing the support of a vector)

I have been looking into the problem
$\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time ...

**1**

vote

**2**answers

406 views

### Nonstandard Hessian approximations in Gauss-Newton

The Gauss-Newton algorithm optimizes functions
$$
E(x) = \sum f(x)^2
$$
by approximating f as (locally) linear, in which case the Hessian of $E$ is approximated as
$$
H = 2 \sum {J_f}^T J_f
$$
Now ...

**0**

votes

**1**answer

32 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

**1**answer

131 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

**2**answers

101 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

**0**answers

53 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 ...

**1**

vote

**2**answers

48 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

**0**answers

73 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.
$$
...

**3**

votes

**1**answer

110 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 ...

**2**

votes

**4**answers

358 views

### Efficient algorithm for finding the minima of a piecewise linear function

Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by
$f(x) = \max_i ( a_i + b_i x )$
We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two ...

**1**

vote

**0**answers

54 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 ...

**22**

votes

**2**answers

817 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 ...

**1**

vote

**0**answers

46 views

### Maximize minimum optimization using linear integer programming [closed]

I am trying to solve a maximize minimum optimization. I have four different items that each of them has 10 values of Rates and for each value it has a corresponding weight. Then I have a free table ...

**4**

votes

**2**answers

139 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 ...

**4**

votes

**2**answers

129 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

**1**answer

54 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

**0**answers

55 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?
...

**0**

votes

**0**answers

44 views

### Multi-objective set-cover optimisation problem

I'm looking for an algorithm to solve the following multi-objective set-cover problem.
We start with a 'universe' (set) of items $\mathcal{U}$, along with a partitioning $P = \{p_0,\ldots,p_m\}$ ...