The linear-programming tag has no wiki summary.

**0**

votes

**1**answer

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

54 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

25 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

65 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

98 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,\; ...

**1**

vote

**0**answers

56 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

74 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

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

**0**

votes

**2**answers

60 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

85 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

143 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

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

**1**

vote

**1**answer

126 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

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

44 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

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

**1**

vote

**0**answers

53 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

43 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

209 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

128 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

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

**0**

votes

**1**answer

48 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

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

**1**

vote

**1**answer

152 views

### Minimizing sum of absolute deviations

Suppose we want to find coefficients $b$ in $\underset{b}{\operatorname{argmin}} \displaystyle\sum\limits_{i=1}^n | y_{i}-b_{1}x_{i}-b_{0}\mid$.
If we rewrite this problem in terms of linear ...

**20**

votes

**4**answers

1k views

### Why are optimization problems called “programming”?

Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...

**4**

votes

**2**answers

367 views

### Simplified knapsack problem

There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...

**2**

votes

**1**answer

143 views

### For interior point methods of linear programming, what is the “L” in the computational complexity $\mathcal{O}(n^3 L)$?

My question is about interior point methods of linear programming. Suppose the constraint matrix $A$ has $m$ rows and $n$ columns, and $m<n$. The state-of-the-art methods, like primal dual interior ...

**1**

vote

**0**answers

79 views

### Interior point optimisation using big M for L1 norm on linear system using Dikin's Affine method

I am a 4th year undergrad surveying student studying computations, specifically $L_{1}$ norm minimisation of residuals in large data sets. To start with (and probably to finish with) I'm using a set ...

**4**

votes

**2**answers

199 views

### point in polytope

Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...

**2**

votes

**1**answer

287 views

### Finding integer points inside of a parallelogram

Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...

**1**

vote

**0**answers

128 views

### Equal maximum and minimum in a large-scale linear programming

For a linear optimization of an integral (with integral constraints), I perform a linear programming for the equivalent series. Maximum and minimum of the LP problem tend to be equal as I increase the ...

**3**

votes

**1**answer

152 views

### Explicit formula for an LMI solution

Suppose we have a linear matrix inequality (aka LMI aka spectahedron aka linear matrix pencil):
$$A_{0}+x_{1}A_{1}+x_{2}A_{2}+\ldots+x_{m}A_{m} \succeq 0.$$
(The notation $X \succeq Y$ means that ...

**2**

votes

**0**answers

25 views

### In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?

I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...

**2**

votes

**0**answers

124 views

### existence of lattice point in polytope

This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...

**2**

votes

**1**answer

208 views

### Why does the LP Formulation of the MST Problem need Topology Constraints?

I am looking for an example that demonstrates the necessity of either subtour-elimination or of connectivity constraints in the LP formulation of the MST
In the internet I only could find the LP ...

**0**

votes

**2**answers

116 views

### Rewrite optimization objective

Hi,
I wanted to ask, under which conditions can one rewrite the optimization objective
$\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$
as
$\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$
I have particular ...

**1**

vote

**2**answers

172 views

### Name of operations on two vectors

Suppose we have two vectors $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^m$.
I could define the mapping
$$
T: \mathbb{R}^n\times \mathbb{R}^m \rightarrow \mathbb{R}^{n\times m}
$$
as follows
$$
T(x,y) = ( ...

**2**

votes

**2**answers

94 views

### LP constraint enconding

I have an objective function to be maximized
$obj(x) = \sum_i \gamma_i x_i$ with $x_i \in \mathbb{R}$
With multiple constraints of the form:
$\min_{y \in 0,1} (\sum_{i \in A} \alpha_i x_i + \sum_{i ...

**0**

votes

**1**answer

486 views

### What does “Vertex Solution” mean?

Hello!
I come across the word "vertex solution" in the context
" We can also assume that x and y are vertex solutions,so that the sequence {x,y} remains in a finite set."
Could anybody know any ...

**2**

votes

**0**answers

39 views

### Put positive polynomial in finite intersection of half-spaces

This is a cross-posting of a MSE question (which did not attract any attention there so far).
Denote by $V={\mathcal P}_{n,d}$ the space of polynomials in $n$ variables with degree at most $d$, ...

**2**

votes

**0**answers

68 views

### Fastest 'Oracle' Algorithm for satisfying a single linear constraint on a convex set?

In this paper by Arora, Hazan, and Kale (http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf) a method is given for using the Multiplicative Weights Update algorithm to quickly solve Linear Programs ...

**1**

vote

**1**answer

343 views

### Reference Request for Integer factorization with LP/ILP

Have there been attempts to factor integers with Linear Programming?
Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...

**0**

votes

**2**answers

353 views

### Efficient algorithm finding 'a' solution of system of linear inequalities

I'm working on rational number field $\mathbb{Q}$.
Is there an efficient algorithm finding a solution of system of linear inequalities?
In many computer algebra systems like Sage or Maple,
there ...

**1**

vote

**2**answers

111 views

### complexity of finding optimal matchings of given fixed size

It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in ...

**1**

vote

**0**answers

553 views

### Robust optimization in matlab using fmincon [closed]

I am trying to implement the following optimization (from this paper) in Matlab using fmincon:
$\min_\omega\omega'\Sigma\omega$ subject to $\min_Ur_p \geq r_0$
where $\Sigma$ is a positive definite ...

**0**

votes

**1**answer

308 views

### Find edge weights that fit given node weights

Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes.
Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node ...

**10**

votes

**2**answers

748 views

### Is the tensor product of polyhedra a polyhedron?

Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...