All Questions
Tagged with linear-programming linear-programming or
492 questions
2
votes
0
answers
43
views
Partitioning $n$-space based on linear combinations
I'm trying to figure out the approximate number of areas the positive $n$-space will be divided into if we partition it as follows: we have $k$ linear functions $F_1$, $F_2$, ..., $F_k$ on $n$ ...
- 21
4
votes
0
answers
539
views
Using Linear Programming as an iterative procedure
Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
- 391
1
vote
1
answer
185
views
Complexity Measures for Mathematical Programming
Question:
Are there any complexity measures in use, that allow one to compare mathematical programming formulations of optimization problems on basis of the number of variables that must be subjected ...
- 13.2k
4
votes
1
answer
2k
views
Under what conditions does an Integer Programming problem run in polynomial time?
Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in ...
- 13.9k
3
votes
1
answer
327
views
LP Constraints for Connected Subgraphs of Fixed Size
Question:
how can the connectedness-constraint for a subgraph, that is induced by a proper subset $W\subset V$ of the vertices of $G(V,E),\ |V|=n,\ |W|=m$, be formulated in a $LP$ or $ILP$?
...
- 13.2k
1
vote
0
answers
42
views
Computation of sub-gradient for a concave envelope
Let $x_1<\cdots<x_n$ be $n$ points on real line and $g=(g_1,\cdots, g_n)\in\mathbb R^n$ be the scattered data. Let $u_g: [x_1,x_n]\to\mathbb R$ be the linear interpolation of $g_1,\cdots, g_n$, ...
- 345
1
vote
0
answers
81
views
Maximizing sum of homogeneous functions of order one over a polytope
Let $f_i: \mathbb{R}^n\rightarrow \mathbb{R}$ be
concave, increasing (i.e., if $x\geq y$ where the inequality is entry wise, we have $f_i(x)\geq f_i(y)$), and a
homogeneous function of order one for ...
- 393
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
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
0
answers
2k
views
How to find a positive solution to an under-determined linear system (if such a solution exists)?
Like the title says, if an under-determined system of linear equations does have at least one positive solution, how to find it efficiently?
Suppose we have an under-determined system:
$$Ax = b$$
...
- 121
1
vote
0
answers
20
views
Calculating Cost-Optimal 1-Factors in Digraphs
I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}...
- 13.2k
2
votes
0
answers
80
views
Making a polyhedron integral by selecting value for a specific co-ordinate of constraint vector
I am currently trying to solve a binary integer programming(maximization) problem, where the first row of the constraint matrix corresponds to the constraints on the total number of 1's in the vector ...
- 123
2
votes
0
answers
105
views
Optimization over a convex cone generated by a set is equal to optimization over the set
Within my research I found an important doubt and that prevents me from advancing, the context of my doubt is as follows:
We considerer the following optimization problem
$$
\left\{\begin{array}{cl} \...
- 159
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 ...
- 13.2k
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|.$$
...
- 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 ...
- 109k
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 ...
- 283
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~...
- 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{\...
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 ...
- 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 ...
- 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 ...
- 61
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 ...
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 (...
- 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 ...
- 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,\...
- 225
2
votes
2
answers
402
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?
- 23
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 ...
- 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 ...
- 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. ...
- 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\...
- 3
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 ...
- 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 $\...
- 11
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?
...
- 163
2
votes
1
answer
508
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 \...
- 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 ...
- 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\...
- 283
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(...
- 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 ...
- 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 ...
- 133
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 ...
- 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 ...
- 9,720
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 ...
- 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 ...
- 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: \...
- 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 ...
- 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 ...
- 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\...
- 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}...
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