**-1**

votes

**0**answers

21 views

### Optimization Problem - Log-term loan [closed]

I have to write the following problem as an optimization problem:
The city of Berlin need for the construction of a tunnel in the next 6 years the following financial resources:
1996 : 20 million DM ...

**0**

votes

**0**answers

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

**0**

votes

**1**answer

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

**2**

votes

**1**answer

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

**-1**

votes

**0**answers

43 views

### Constrained optimization with known first and second derivatives

I am looking for methods (and potentially numerical implementations) designed for optimization of the type:
$$ \min_{x \in R^n} f(x) \mid g(x) \geq 0 $$
where I know $f$, $\left({{\partial f}\over ...

**2**

votes

**0**answers

107 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

**1**answer

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

**1**

vote

**3**answers

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

**0**answers

18 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

**1**answer

91 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

**0**answers

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

**4**

votes

**1**answer

111 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

**1**answer

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

**0**

votes

**1**answer

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

**2**

votes

**1**answer

78 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

**0**answers

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

**3**

votes

**2**answers

232 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

**0**answers

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

**2**

votes

**0**answers

73 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} + ...

**0**

votes

**1**answer

59 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

**0**answers

41 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

**1**answer

71 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

**0**answers

76 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

**2**answers

102 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

**0**answers

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

vote

**0**answers

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

**1**

vote

**0**answers

42 views

### The column generation technique on a Train Unit Assignment Problem [Linear Programming]

I am doing an assignment where I need to implement a mathematical model that I can't wrap my head around. For the technique of column generation, one would need to my understanding, a master problem ...

**3**

votes

**1**answer

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

**3**

votes

**1**answer

259 views

### Find the minimum distance between two convex hulls

We work over $\mathbb{R}^N$. Let $\mathbf{P}_1$ denote the hyperplane constructed using $N$ points, each of which is on a different axis (there are $N$ axes). We denote by $\mathbf{P}_2$ the convex ...

**5**

votes

**1**answer

104 views

### Resource Constrained Routing with Refueling

What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...

**4**

votes

**1**answer

103 views

### Basic result in semi-infinite linear programming

Consider a standard linear program of the form $$\textrm{minimize}_x~~~~ c^Tx~~~~ s.t. \\ Ax = b \\ x \geq 0$$ with $x\in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$. It is well known that, if ...

**0**

votes

**0**answers

47 views

### Finding a movement taking out of a convex set

There is a convex set $S$ as the hull of M points in an D-dimensional Euclidean space and a point $\vec P$ in the set. Then, there is a set of vectors $\vec W$ taking the form $\vec W=\sum_{i=1}^N ...

**2**

votes

**1**answer

169 views

### How can I find the maximum value of this function?

For given values of $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$, how can I find the value of:
$$
\max_{x \in [0,1]^n} \|Ax+b \|_1
$$
Or is this problem NP-hard?

**7**

votes

**3**answers

3k views

### Solving a system of linear inequalities — what is the dimension of the solution set?

It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$?
For the applications I have in mind the ...

**2**

votes

**1**answer

58 views

### Algorithm to find the vertices of the equidistant lines between N closed polygonal lines

I have a set $\{C_1, C_2, \ldots, C_N\}$ of $N$ nonintersecting closed piecewise linear curves on the Euclidean plane. For every point $x \in \mathbb{R}^2$ we say it belongs to a territory serviced by ...

**1**

vote

**0**answers

64 views

### Smallest sum of original column entries in 2d matrix [closed]

I have an interesting optimization problem I am trying to solve now and I thought I'd share it here in order to find the best answer. The problem itself is not complicated and it is stated like this:
...

**3**

votes

**1**answer

262 views

### How to implement linear constraints that include several absolute values

Dear all,
I am trying to implement a linear constraint that includes several absolute values in the form: Abs(A) + Abs(B) + Abs(C) + Abs(D) + ... = 1
Since the minimization problem includes quite a ...

**1**

vote

**1**answer

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

**3**

votes

**1**answer

260 views

### Constrained vs Unconstrained Optimization

I'm currently working on an optimization problem with a linear objective with linear and nonlinear constraints, i'm facing difficulties reaching a good solution, so i was advised to move the nonlinear ...

**4**

votes

**3**answers

595 views

### Algorithm for the intersection of a vector subspace with a cone of non-negative vectors

Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...

**1**

vote

**1**answer

196 views

### Computing probability that $Ax\geq0$ where $x$ is a vector of iid gaussians and $A$ is matrix of $1$s and $0$s

This question came up in my research: What is the probability that $Ax\geq0$ where $x$ is a vector of iid gaussians and $A$ is matrix of $1$s and $0$s?
So far I only figured out that I can do Monte ...

**5**

votes

**0**answers

66 views

### Finding the optimal mixture of two convex functions

I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where ...

**2**

votes

**0**answers

58 views

### Derivation of gradient of SSE in Geodesic Regression

On page 79 (or page 5) of this this paper the gradient of the SSE of the Geodesic model is described explicitly. My question is how are these equitations derived in detail; where can I find the ...

**2**

votes

**0**answers

84 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

**1**answer

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

**6**

votes

**1**answer

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

**6**

votes

**0**answers

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

**2**

votes

**1**answer

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

**5**

votes

**1**answer

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

**0**

votes

**1**answer

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