Skip to main content

All Questions

Filter by
Sorted by
Tagged with
1 vote
1 answer
111 views

Optimal "Generalization" of Polylines

This question is inspired by a lossy compression technique for polylines, namely to identify a subset of the points of polyline $\mathcal{P}$, whose removal yields a polyline $\mathcal{Q}$ within a ...
Manfred Weis's user avatar
  • 13.2k
8 votes
2 answers
215 views

“Totally transitive” polytopes which are not regular

Is it possible to have an abstract polytope which is vertex-transitive, edge-transitive, face-transitive, etc. (individually transitive on faces of each particular dimension) and yet not flag-...
Sridhar Ramesh's user avatar
17 votes
3 answers
2k views

The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$

Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum: $$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$ ...
TOM's user avatar
  • 2,288
10 votes
0 answers
722 views

Fractional Matching version of Hall's Marriage theorem

Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent: 1) there exist a perfect matching in $G$; 2) there exist non-negative weights on edges such that the sum of ...
Fedor Petrov's user avatar
2 votes
0 answers
344 views

Linear programming with an infinite matrix

I would like to solve the following infinite linear system subject to $x_i \ge 0$ that minimizes $x_3$. The third column contains no additional nonzero values beyond what is shown. Though the first ...
user3433489's user avatar
4 votes
0 answers
124 views

Reference for this fact about perturbed polytopes?

Let $K \subset \mathbb{R}^n$ be a polytope (i.e., an intersection of finitely many halfspaces that has finite volume) and consider $F(K) := \int_K \|x\|^2\, {\rm d}x$, where $\|\cdot\|$ is the ...
Noah Stephens-Davidowitz's user avatar
1 vote
2 answers
83 views

Algorithm for a linear optimization problem

For the vectors $X=(x_1,\cdots, x_n),~ Y=(y_1,\cdots, y_n)$ and $\alpha=(\alpha_1,\cdots,\alpha_n),~ \beta=(\beta_1,\cdots, \beta_n)\in\mathbb R^n_+$ s.t. $\sum_{k=1}^n\alpha_k~~=~~\sum_{k=1}^n\beta_k~...
Higgs88's user avatar
  • 131
1 vote
0 answers
78 views

Family of functions which satisfies $f(\boldsymbol{x}) = 0$ if $\nabla f(\boldsymbol{x})=0$? [closed]

I have a Lagrangian of which I want to find the supremum in the primal variable $\boldsymbol{x}$: $\mathscr{L}(\boldsymbol{x},\boldsymbol{\lambda})=f(\boldsymbol{x})^T\boldsymbol{a} + \boldsymbol{\...
Danilo Socovan's user avatar
1 vote
0 answers
47 views

Linear programs [closed]

Can the optimal value of the primal problem of a linear program ever be less then zero? An example is: minimize $C=2x_1 +3x_2$ Subject to: $3x_1+4x_2 \leq 5$. Obviously, $x_1$ and $x_2$ are free ...
josh's user avatar
  • 11
1 vote
0 answers
93 views

quick hull algorithm detail

When using quick hull algorithm to find the polytope for half space intersection, we are required to provide an interior point to the solver qhalf. In other words, providing $$Ax \le b$$ is not ...
user40780's user avatar
  • 867
1 vote
0 answers
43 views

a question about probabilities on spaces of digraphs

Let $G$ be a directed graph with fixed nodes $s$ and $t$. Assume that each edge $e$ in the graph comes with a number $n(e)\in[0,1]$. We consider probability spaces $S$ whose points are directed ...
Larry Moss's user avatar
3 votes
2 answers
1k views

Equality constraints in mixed-integer optimization

Suppose I have a linear mixed-integer optimization problem of the form $$MIP: min_{(x,y) \in \mathbb{R}^n \times \mathbb{Z}^m} c^\top x + d^\top y \hspace{0.2cm} \text{s.t.} \hspace{0.1cm} Ax+By \leq ...
Christoph Neumann's user avatar
0 votes
1 answer
79 views

algorithms and tools available for a particular polytope computation

Let me define each half space i as: $${H_i}:{c_i}{\bf{x}} \le {b_i}$$ The intersection of all such ${H_i}$ gives a polyhedron (bounded or not). Suppose I am interested in if ${H_i}$ is active (...
user40780's user avatar
  • 867
1 vote
1 answer
73 views

minimize number of unique elements in a vector

I was wondering if there is a simple or known way to minimize the number of unique elements in a decision variable (vector). Note that I'm not asking for minimization of nonzero elements (rank ...
Lorenzo's user avatar
  • 13
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,\...
Kuifje's user avatar
  • 225
2 votes
2 answers
403 views

Is this a linear optimization problem? $Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative

$Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative. What should $A$ satisfy to guarantee the equation set have only zero solution?
ZhongHua Yan's user avatar
2 votes
1 answer
148 views

Fast algorithm for large-scale, asymmetric transportation linear program

I have a large-ish instance of a transportation problem that is very asymmetric, say of dimensions $100\times10000$. I am currently solving it with a stock LP solver, but obviously something like the ...
Tom Solberg's user avatar
  • 4,049
1 vote
1 answer
206 views

Show $0-1$ Knapsack is polynomially reducible to this problem

I have already posted this question here but have not received an answer so I am cross-posting with hope to reach a larger amount of mathematicians: Let $T=\{1,\cdots,n\}$ and consider the ...
Kuifje's user avatar
  • 225
6 votes
2 answers
1k views

Linear programming is continuous

Consider an arbitrary linear program: $$\max \vec c \cdot \vec x$$ subject to: $$\textbf{A}\cdot \vec x = 0, \quad \vec a \le \vec x \le \vec b$$ Assume that this program is feasible and bounded. ...
valle's user avatar
  • 884
0 votes
1 answer
81 views

Can convex combinations of indicator functions for pairwise non-disjoint sets unordered by inclusion dominate one another?

Let $N$ be a finite subset of the naturals. Let $P$ be a set of subsets of $N$ such that: 1) $P\neq \varnothing$, 2) $\forall x\in P, |x| >1$, 3) $\forall x,y\in P,$ if $x\neq y$, then $x\not\...
VMfoobar's user avatar
0 votes
0 answers
68 views

A seemingly easy integer programming question

Let $k, m \in \mathbb{Z}_{ > 1}$. Let $a \in \mathbb{Z}_{> 0}^m$ and $t \in \mathbb{Z}^k$. Let $\varepsilon = (\varepsilon_{i,j})_{1 \leq i \leq m \\1 \leq j \leq k}$ be a matrix with entries in ...
Alex's user avatar
  • 501
1 vote
1 answer
113 views

Are convex combinations of 0-1 Pareto efficient vectors efficient?

Let $Y$ be any subset of $\{0,1\}^n$ for $n\geq3$. A vector $\alpha\in$ $Y$ is Pareto efficient if there is no $\beta\in$ $Y$ such that $\beta_i$ $\geq$ $\alpha_i$ for each $i\in\{1,...,n\}$ and $\...
econ-math's user avatar
16 votes
3 answers
1k views

Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?

Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets. Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$. Can $\text{Proj}(P)$ have more than $f$ facets? ...
Pedro Ruiz's user avatar
2 votes
1 answer
509 views

Under what condition does Courant–Fischer–Weyl min-max principle hold in general?

From Wikipedia: Let $A$ be an $n \times n$ Hermitian matrix. As with many other variational results on eigenvalues, one considers the Rayleigh–Ritz quotient $R_A : \mathbf C^n \setminus \{0\} \to \...
Fraïssé's user avatar
  • 155
27 votes
5 answers
2k views

Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?

Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows: $$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$ For example, if $m=3$, the matrix is $$\begin{pmatrix}6 & 20 & 6& 0 ...
user42804's user avatar
  • 1,121
2 votes
2 answers
3k views

Linear programming with infinitely many constraints

I wish to study the following linear program $$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathrm x \geq 0\...
user3433489's user avatar
0 votes
2 answers
120 views

Reference request: dependence on linear constraints

Excuse me if my question is stupid. I'm seeking the references on the dependence of the (linear) optimization problem on (linear) constraints. Namely, consdier the following optimization problem: $$P(...
CodeGolf's user avatar
  • 1,835
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 ...
CodeGolf's user avatar
  • 1,835
2 votes
1 answer
1k views

Complementary slackness for approximately optimal Dual solution

Given a Primal LP (P) and it Dual LP (D) we know that the optimal solutions to P ($x_{opt}$) and D $(y_{opt})$ satisfy complementary slackness condition, i.e. under optimal solutions either a ...
Soumya Basu's user avatar
0 votes
0 answers
890 views

Maximum shortest path problem

I have the following problem. You have a graph and every edge has a certain set of possible weights. The question is to find the assignment of those weight which will maximize the shortest path. In ...
Eugene's user avatar
  • 342
2 votes
0 answers
126 views

Unveiling hidden structures

One way to unveil a hidden structure of a undirected graph - given as an adjacency matrix - is to permute the rows and columns until a pattern with a maximal geometrical symmetry is found. (The ...
Hans-Peter Stricker's user avatar
6 votes
1 answer
2k views

Approximation of convex hull in high dimension

What are efficient methods (polytime) to compute an approximation of the convex hull in high dimension (say, $30000$) for a given set of points? Edit: I am looking for an algorithm for getting the ...
test100's user avatar
  • 61
19 votes
4 answers
1k views

Applications of linear programming duality in combinatorics

So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
amakelov's user avatar
  • 997
1 vote
0 answers
1k views

Number of different combinations in a 0-1 knapsack problem with integer weights [closed]

My question is actually very similar to this other one: Given a vector of positive integers, count the number of combinations which have a sum that produces a different value. But, since this previous ...
Vicent's user avatar
  • 153
3 votes
1 answer
634 views

Properties of one dimensional null space

Let $\mathcal{G}$ be denote the set of all $3 \times 3$ real symmetric matrices and let $\mathcal{G}^+$ denote the set of all $3 \times 3$ positive semidefinite matrices (see definition). Let $S: \...
ashok's user avatar
  • 31
4 votes
2 answers
722 views

Minimum number of rectangles in a polygon

Given a polygon and dimension $d$, find a minimum partition of rectangles that has either of its dimensions equal to $d$. Example: Consider the following diagram: I want to cover maximum shaded ...
ubaabd's user avatar
  • 175
1 vote
0 answers
1k views

Analytic formula for minimizing the maximum inner product of a set of vectors

Given $x_j\in\mathbb{R}^n$, $j=1,\ldots,p$, find $$ \widehat{w} \in \arg\min_{\Vert w\Vert=1}\max_{1\le j\le p} |\langle w,x_j\rangle|. $$ I am also interested in the special case where we further ...
JohnA's user avatar
  • 710
1 vote
1 answer
184 views

Do doubly infeasible Linear Programming problems always have doubly infeasible bases?

Consider a Linear Programming problem in dictionary form, $$\max\Big\{f^\pi+\!\!\!\sum_{j\in D(\pi)}\!\! d^\pi_jx_j~\Big|~\forall~i\!\in\!B(\pi)~~~ b^\pi_i+\!\!\!\sum_{j\in D(\pi)}\!\! G^\pi_{ij}x_j\...
Goswin's user avatar
  • 21
0 votes
1 answer
201 views

Recursive linear programming on a linear subset of a simplex

The problem I am working on is: Given an $n$ dimensional vector $r \in \mathcal{R}^n$, and a convex set $G=\{\mu \in \mathcal{R}^n | \mu_i \ge 0, ~ \mu^T \mathbf{1}=1, ~ A\mu =0 \}$ where $\mathbf{1}...
Sungjoon Choi Samuel's user avatar
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 ...
TMS's user avatar
  • 131
0 votes
1 answer
212 views

How to find out if a polytope contains a sphere?

Given a polytope described by linear inequalities $Ax \le b, x \in \mathbb R^n$, how do you find out if there exist a (non degenerate) sphere of dimension $n-1$ contained in the polytope? Thanks!
maroxe's user avatar
  • 225
1 vote
0 answers
187 views

Strong Duality of Mixed Integer Linear Program

The problem at hand is to optimize a mixed-integer linear program closely related to the maximum flow problem. I would like to reformulate the problem with its dual and I'm concerned with the ...
Amitai G's user avatar
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{...
Eugene's user avatar
  • 342
2 votes
1 answer
171 views

Maximization of Binary Multilinear Fractional Function

Problem: Let $a_{i,j}$, $b_{i,j}\in\mathbb{R}$ for all $(i,j)\in\left[m\right]^2$ such that $a_{i,j}=a_{j,i}$ and $b_{i,j}=b_{j,i}$. Let $z_k\in\{0,1\}$ for $k\in\left[m\right]$. We wish to maximize, ...
Joseph Zambrano's user avatar
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 $$ ...
Sidharth Ghoshal's user avatar
2 votes
1 answer
529 views

Integer programming and Groebner basis

I enjoyed reading different papers about using Groebner basis to solve integer programming. Is there any literature about the complexity and/or comparison with other (more classical) methods like ...
teller's user avatar
  • 337
1 vote
1 answer
155 views

Derive a vertex representation of a permutohedron from its linear-inequalities form

Let us define the $n$-permutohedron $P_n$ as the set of all $x\in\mathbb{Q}^n$ such that $$\sum_{i=1}^n x_i = \binom{n{+}1}{2}\ \ \ \land\ \ \ \forall\,\text{nonempty}\ S\subsetneq\mathbb{N}_n\colon\ ...
user avatar
1 vote
0 answers
46 views

Non-negative polynomials $f(p), p\in P$ from Polynomial ideal where $P$ compact polytope?

Partially related to Non-negative Polynomials from Polynomial Ideal? where focus on graph theory but now I want to understand more generally how to determine non-negativity in more general case. A. ...
hhh's user avatar
  • 143
1 vote
1 answer
1k views

convert absolute form into linear programming problem [closed]

I would like to convert this problem into a Linear Programming Problem : $\min |x|+|y|+|z|$ subject to $x+y \leq 1$ $2x+z=3$. The solution to this problem is given chapter and here. But I still ...
roni's user avatar
  • 113
9 votes
1 answer
2k views

Uniform sampling from general simplex with a twist

This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange. Given $0\leq a_1\leq\dots\leq a_D\leq1$ (all strictly positive), I want to draw points ...
Juanito's user avatar
  • 221

1
5 6
7
8 9
13