The linear-programming tag has no wiki summary.

**-2**

votes

**0**answers

24 views

### Can this specific Mixed-Integer Linear Program constraint be expressed? [on hold]

Thanks for your time.
I have a linear program and no idea how I could express a form of constraint and even if it's possible. Maybe someone here know a solution.
A company assembly and sells a ...

**6**

votes

**2**answers

128 views

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

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

**-3**

votes

**0**answers

31 views

### Operations research and Linear Programming [on hold]

I am working on a linear programming maximization problem and need help in understanding how to reformulate this problem so that it has only two functional constraints and all variables have ...

**0**

votes

**0**answers

19 views

### Bender's decomposition with overlapping y variables [closed]

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

25 views

### Get fractional LP into canonical form [closed]

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

43 views

### quadratic knacksack problem, state of art [closed]

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

28 views

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

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

**-1**

votes

**2**answers

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

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

**2**

votes

**0**answers

70 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

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

**0**

votes

**1**answer

67 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

**2**answers

118 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

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

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

**2**

votes

**1**answer

100 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

68 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

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

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

120 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

69 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

**1**answer

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

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

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

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

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

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

112 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

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

**2**

votes

**1**answer

83 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

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

**22**

votes

**2**answers

819 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

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

55 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\}$ ...

**1**

vote

**1**answer

262 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

**2**answers

133 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

**0**answers

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

**4**

votes

**2**answers

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

**0**

votes

**1**answer

49 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

**1**answer

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