**0**

votes

**0**answers

18 views

### LP or IP necessary? Network Flow Problem with no cycle-condition (unimodularity?) [on hold]

I need your help with a optimization problem.
Recap:
Normal mincost flow networks optimization problems have a constraint matrix which is total unimodular. This is a nice feature since a linear ...

**4**

votes

**2**answers

502 views

### Bounding the minimal maximum norm of a solution of a linear system.

I would be grateful for pointing me out a reference to some general bound on the $\ell_{\infty}$ norm of a solution of a linear system. To be specific, suppose that we have an underdetermined linear ...

**2**

votes

**1**answer

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

**25**

votes

**6**answers

5k views

### How to find a closest integer point to intersection of two lines?

Here's a question that originates from StackOverflow (and the SO crowd isn't really qualified to solve it).
We're given two lines on the plane, specified by equations ($a x + b y = c$) whose ...

**0**

votes

**0**answers

36 views

### Separation on discrete set

Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ ...

**0**

votes

**0**answers

14 views

### Finding orthogonal basis with constraint

Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$
with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$.
And is there any condition on $V_i,i\leq ...

**2**

votes

**0**answers

35 views

### Existence of probability distribution satisfying upper/lower bounds on events

Suppose we have a finite sample space $S$ and some events $A_1, \dots, A_k \subseteq S$. We would like to put a probability distribution on $S$ so that no element has probability greater than a ...

**5**

votes

**2**answers

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

**1**

vote

**0**answers

65 views

### Existence of Nonnegative Solutions of Linear Systems of Equations and Inequalities with particular constraints

Suppose we have an n by m nonnegative matrix A, where each row sums to 1. I wonder whether there exists an m by n nonnegative matrix X that satisfies the following constraints: each row of X sums to ...

**2**

votes

**1**answer

60 views

### Minimum cover for sets in which each element appears in exactly 2 sets?

Is there an algorithm for finding minimal covers of a set of sets in which each element of the universe appears in exactly 2 sets? I realize that LP relaxation approximates this to within a factor of ...

**4**

votes

**0**answers

642 views

### Infinite Linear Programming

I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility ...

**1**

vote

**1**answer

44 views

### Perturbation of Linear Programs

Consider the linear program,
\begin{align}
& \max c^Tx \\
& \mbox{such that }Ax \leq b \\
& \mbox{ and } x \geq 0
\end{align}
I want to study the sensitivity of the optimal $x^*$ ...

**0**

votes

**0**answers

60 views

### Optimization with vectors

I am trying to solve the following optimization problem as a small part of a research project, and I do not know if there exists closed form solutions. My linear algebra is very rusty and I am looking ...

**1**

vote

**1**answer

192 views

### Covering max flow arcs by arc disjoint paths

Let $(N,A,s,t,u)$ be a network with node set $N$, arc set $A$, source $s\in N$, sink $t\in N$ and capacity vector $u\in\{1,2,\ldots,T\}^A$, and let $x=(x_a)_{a\in A}$ be a maximum $(s,t)$-flow. Is it ...

**0**

votes

**0**answers

47 views

### About identifying a few diagrams

Please have a look at these beautiful seminar slides,
https://math.berkeley.edu/~bernd/coimbra1.pdf
Can someone kindly identify the algebraic description of the spectrahedron that is drawn on slide ...

**4**

votes

**0**answers

132 views

### Closed-form solution of a linear programming question

Among all the probability matrices
\begin{equation*}
P =
\left(\begin{array}{cccc}
p_{00} & p_{01} & \ldots & p_{0,J-1} \\
p_{10} & p_{11} & \ldots & p_{1,J-1} \\
\vdots & ...

**1**

vote

**1**answer

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

**0**

votes

**1**answer

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

**0**

votes

**1**answer

100 views

### Is the linear production game a convex game?

In cooperative game theory, the linear production game (LPG) is defined by letting the characteristic function have the form of a linear programming problem.
Does anyone know if the LPG is a convex ...

**0**

votes

**0**answers

28 views

### Maximisation of a discrete linear function

I am trying to maximise the function
$$
Q=\sum_i{\alpha _{i}x_{i}}
$$
subject to the constraint
$$
W<=\sum_i{\alpha _{i}w_{i}x_{i}}
$$
By changing $\alpha _{i}$ subject to $ 0<=\alpha ...

**0**

votes

**0**answers

26 views

### Equivalence between multiclass SVMs, power diagrams, and constrained $k$-means

Apologies in advance for the long post:
Suppose we have a collection of points $\mathbf{p}_1,\dots,\mathbf{p}_n$ in $\mathbb{R}^d$, and we consider the following three ways of partitioning these ...

**3**

votes

**6**answers

1k views

### Circumference of Convex Shapes

Here is a puzzle I found in Mitteilungen der DMV (roughly, "Letters of the German Society of Mathematicians"), issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ...

**1**

vote

**1**answer

63 views

### Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces

Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by
$$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$
$$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$
I wish to find their convex hull, that is a ...

**0**

votes

**0**answers

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

**2**

votes

**0**answers

111 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

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

19 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

117 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

32 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

152 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

85 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

53 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

86 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

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

**3**

votes

**0**answers

113 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

47 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

82 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

123 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

67 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

59 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

51 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

368 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

115 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

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