All Questions
740 questions
3
votes
0
answers
105
views
Are there scenarios under which feasibility bilinear programming is easy?
Given $c\in\Bbb R^{n_1},d\in\Bbb R^{n_2}$, $E\in\Bbb R^{n_1\times n_2}$, $A\in\Bbb R^{m_1\times n_1}$, $B\in\Bbb R^{m_2\times n_2}$ $a\in\Bbb R^{m_1}$, $b\in\Bbb R^{m_2}$ and $t\in\Bbb R$ we know ...
- 13.9k
3
votes
1
answer
368
views
Lot sizing problem: how to add these cuts efficiently
Consider the set of constraints of the uncapacitated lot sizing problem:
$$
\{(x,s,y)\in \mathbb{R}^n_+ \times \mathbb{R}^n_+ \times \mathbb{B}^n \;|\;s_{t-1}+x_t = d_t+s_t,\; x_t \le My_t,\; t=1,\...
- 225
3
votes
0
answers
71
views
Dependence of optimization problem on the linear constraints
Let $I=\{x_1,\cdots, x_n\}\subset \mathbb R$ be fixed. Given two probability distributions $\alpha=(\alpha_i)_{1\le i\le n}$ and $\beta=(\beta_i)_{1\le i\le n}$ on $I$, and a matrix $c=(c_{i,j})_{1\le ...
- 1,835
3
votes
0
answers
359
views
Cubical approximation theorem for cubical complexes
A version of the simplicial approximation theorem states that a continuous map between finite simplicial complexes is homotopic to a simplicial map after subdividing the domain.
I have found a claim ...
- 985
3
votes
0
answers
128
views
Stellar moves on pairs of polyhedra
Let $P$ and $Q$ be polyhedra of $\mathbb{R}^n$ with $Q \subset P$. Let $(M,N)$ and $(M',N)$ be pairs of abstract simplicial complexes.
Consider two triangulations
$$f\colon (|M|,|N|) \to (P,Q)$$
...
3
votes
0
answers
103
views
Is there any connection between Lagrange points and the icosahedron?
Given the Newtonian two-body problem, one can ask if there are any orbits that allow a test particle to maintain a fixed configuration relative to the two bodies. In other words, in a frame that ...
- 1,444
3
votes
0
answers
970
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} + {a}_{1,...
- 31
3
votes
0
answers
133
views
Convex polyhedra jammed in $k$ disjoint holes
For a given convex polyhedron $P \subset \mathbb{R}^3$,
I was imagining finding the optimal "fixing" of $P$ in holes (or jamming them in "mud"),
which led to the following question.
First, scale $P$ ...
- 151k
3
votes
0
answers
3k
views
0,1 solution to system of linear integer equations
I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-matrix and $m$-vector of nonnegative integers (respectively).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
- 149
3
votes
0
answers
220
views
Could SVD be used to optimize the partial inner-products?
Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with
$m-$dimensional coordinates in ...
- 131
3
votes
0
answers
312
views
Linear complementarity problem: principal pivoting algorithm
I'm trying to implement the "Dantzig; van de Panne and Whinston" principal pivoting algorithm for solving symmetric positive semi-definite LCPs from "The Linear Complementarity Problem" book (...
- 151
3
votes
2
answers
1k
views
SDP relaxation vs LP relaxation
I have a question I hope you might be able to answer.
Let's say we have an integer program for the stable set problem (or clique, not principal).
\begin{equation}
\begin{aligned}
& \text{...
- 342
2
votes
2
answers
2k
views
Mathematical tools appropriate to analyse convex polyhedra
What mathematical tools (means: set of areas of mathematical knowledge) are appropriate to begin with to analyse (to enumerate face vectors associated with polyhedron, to calculate the combinatorial ...
2
votes
2
answers
811
views
Surface of a Ideal Tetrahedron in Hyperbolic Space H3
The hyperbolic space $\mathbb{H}^3$, has a boundary $\mathbb{CP}^1$.
A ideal tetrahedron in $\mathbb{H}^3$, is a tetrahedron, where the four vertices are on the boundary $\mathbb{CP}^1$.
The four ...
- 275
2
votes
3
answers
1k
views
Concrete works by Alexandre Grothendieck, other than Dessin d'Enfants?
For me "Dessin d'Enfants" by Alexandre Grothendieck is the more concrete research work he has done. I would like to know if there are others.
When he was teaching at Montpellier University (...
- 85
2
votes
3
answers
2k
views
Better tactics for removing redundant constraints than Linear Programming?
After reading:
Detection of Redundant Constraints
It appears that linear-programming is the most commonly known way to remove ALL redundant constraints from a system of inequalities of the form
$$ ...
- 2,689
2
votes
2
answers
334
views
A Jordan Separation Theorem for Polyhedral Surfaces
Let me begin by defining what a polyhedral surface is.
A path-connected subset $ P $ of $ \mathbb{R}^{3} $ is called a polyhedral surface iff it is the union of a finite collection $ \mathcal{C} $ of ...
- 1,396
2
votes
4
answers
212
views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 157
2
votes
2
answers
640
views
Sorting a binary matrix diagonal in polynomial time while preserving rows
Is there a polynomial time solution to sort an arbitrary binary square matrix in polynomial time by rows so that the diagonal contains a 1 if any row contains a 1 in that column?
For example given ...
- 121
2
votes
3
answers
2k
views
non-convex Polytope definition
I have a simple question. I read that given a vector space $N_{\mathbb{R}}$ over $\mathbb{R}$,
we can define a convex polytope in the following way:
$$P:= \Big\{ \sum_{u\in S} \mu_u u \,\Big| \, \...
- 335
2
votes
3
answers
1k
views
Quadratic Programming With Piecewise Linear Term
The problem I have can be defined as:
$$
\min \frac{1}{2}\mathbf{x}^T\mathbf{Q}\mathbf{x} + \mathbf{c}^T\mathbf{x}
$$
s.t. linear equality constraints:
$$
\mathbf{Ax=b}
$$
and linear inequality ...
- 131
2
votes
3
answers
2k
views
Efficient Algorithm For Projection Onto A Convex Set
Given $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem:
$\underset{\mathbf{p}}{\mathrm{argmin}} \; \|\mathbf{p}-\mathbf{x}\|_2
\;\;
\...
2
votes
2
answers
418
views
Lovasz theta function - uses
Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?
2
votes
4
answers
2k
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 lines:...
- 823
2
votes
2
answers
421
views
Algorithm to determine if a union of half-spaces is all of $\mathbb{R}^d$
I have a collection of closed half-spaces $H_1, \dots, H_n \subseteq \mathbb{R}^d$, each given as $H_i = \{x \in \mathbb{R}^d : a_i \cdot x \geq c_i\}$ for some $a_i \in \mathbb{R}^d$ and $c_i \in \...
- 461
2
votes
1
answer
1k
views
What does the basis of the null space of the constraint matrix of a flow problem look like?
Consider a directed graph $G=(V,\mathbb{A})$ and a set of flow constraints of the following form:
$$ \sum_{(u,v)\in\mathbb{A}}x_{u,v} - \sum_{(v,u)\in \mathbb{A}}x_{v,u} = 0 \forall v \in V$$
...
- 31
2
votes
1
answer
218
views
Polyhedra names question [closed]
So I've been playing around with polyhedra for my own amusement, but I ended up with some that I couldn't find names for. I have been trying to find them on my own by Googling for polyhedra with these ...
- 21
2
votes
1
answer
274
views
Digital topology, animal problem, 2-sphere and torus
I have the following question relating digital topology, surfaces, particularly $S^2$ and torus.
Can a body $B$ constructed with cubes (without cavities or tunnels) and with frontier homeomorphic to ...
2
votes
2
answers
219
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,\; \...
- 23
2
votes
1
answer
171
views
coarser than triangulations "almost partitions" into simplices
The total space $T$ of an embedded into $\mathbb{R}^n$ pure $n$-dimensional simplicial complex (in other words, the union of finitely many $n$-dimensional compact convex polytopes) sometimes admits an ...
- 14k
2
votes
1
answer
304
views
existence of l1 embedding using LP feasibility
hello
Let (A, d) be an n-point metric space
for $t \geq 1$,the task it to find an integer $m$ and an embedding $f : A \rightarrow R^m$ s.t.
$\forall x,y \in A$ : $d(x,y) \leq d_1(f(x), f(y)) \leq t*...
- 239
2
votes
1
answer
1k
views
Linear Programming Cost Function [closed]
I need to add the following to my LP problem:
If the amount of workers hired in period $t$ ($H_t$) is higher than 25, the hiring cost is only 1 instead of 1.2.
Example: if 30 workers are hired in ...
2
votes
1
answer
213
views
Is matrix B obtained from matrix A?
Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
- 49
2
votes
1
answer
165
views
Tangent cone on polyhedral spaces
Let $X$ be an n-dimensional polyhedral space with, say, $n\geq 3.$ Let also $p\in X$ be a vertex on a triangulation $\tau$ of $X,$ so a vertex on the polyhedral space.
The tangent cone (as a metric ...
- 85
2
votes
1
answer
75
views
Generic infinitesimal rigidity of polyhedra
Let $M$ be a 1-skeleton of a triangulation of a sphere with $V$ vertices and $E$ edges.
Definition 1 A polyhedron is a map $M\to \mathbb R^3$ that is affine on edges (and non-degenerate on faces). The ...
- 2,934
2
votes
1
answer
127
views
Distance between two polyhedra that takes incidence structure into account
Suppose that we have two polyhedra $P_1$ and $P_2$ in $\mathbb{R}^3$. I would like to define such a metric $\rho(P_1, P_2)$ that depends on several factors, but currently I don't know how to do it ...
- 123
2
votes
1
answer
485
views
Odd cycle transversal
Suppose we have a graph G. Say B a fundamental basis of the cycle space of G. Say LP a linear programming problem where there is a variable for each vertex of G, each variable can take value $\geq 0$, ...
2
votes
1
answer
871
views
Interior point of a convex polytope
Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
2
votes
1
answer
237
views
Sampling algorithms on convex polytopes
Let $f=\mathbf{c}\cdot\mathbf{x}$ be the optimization objective function whose parameter vector $\mathbf{x}\in\mathbb{R}^n$ is subject to the following constraints in the very well-known linear-...
2
votes
2
answers
242
views
Products of polytopes and the normals of their facets
I need to compute the normals of the facets of certain polytopes that can be represented as products of polytopes in smaller dimensions.
Searching the bibliography I found that the facets of the ...
- 21
2
votes
1
answer
243
views
Does quantifier elimination help here?
Suppose we have a quantified linear program
$$\exists z_1,\dots,z_{poly(n)}\in\mathbb R$$
$$\exists u_1,\dots,u_n\in\mathcal P\cap\mathbb R^m$$
$$\forall v_1,\dots,v_n\in\mathcal P\cap\mathbb R^m$$
$$...
- 1,826
2
votes
1
answer
140
views
Separation of two pointed polyhedral cones using hyperplanes generated by facets
Let $C_1$ and $C_2$ two pointed (that is, with vertex in $0$) polyhedral cones in $\mathbb{R}^n$ with $\dim(C_1)=\dim(C_2)=n$. If
$$\mbox{relative interior}(C_1)\cap \mbox{relative interior}(C_2)=\...
- 131
2
votes
1
answer
123
views
On the realization of a quotient group
Let $P$ be a finite polyhedron and $N$ be a normal subgroup of $G=\pi_1 (P)$. It is known that there exists a covering space $(\tilde{P},p)$ so that $p_* \pi_1 (\tilde{P})=N$. It follows that for the ...
- 139
2
votes
2
answers
438
views
Perturbation of Linear Programs
Consider the linear program,
$$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & Ax \leq b\\
& x \geq 0\end{array}$$
I want to study the sensitivity of the optimal $x^*$ ...
- 275
2
votes
1
answer
186
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?
- 23
2
votes
1
answer
153
views
Polyhedra containing hexagones only [closed]
It is well-known that Euler's theorem gives raison d'être to polyhedra containing exactly 12 pentagons if they are connected by 3 in a vertex. The number of hexagons may be arbitrary (in fact >1). In ...
2
votes
1
answer
689
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 ...
- 13.2k
2
votes
3
answers
752
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 ...
- 13.2k
2
votes
1
answer
2k
views
Finding a point farthest away from $k$ points in a polygon
There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized.
...
- 57
2
votes
1
answer
848
views
Algorithm for satisfiability of inequalities.
I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$.
In ...
- 85