Questions tagged [linear-programming]

Linear programming is the study of optimizing a linear function over a set of linear inequalities. The Simplex Method, Ellipsoid Method and Interior Point Method are popular algorithms to solve linear programs.

Filter by
Sorted by
Tagged with
3 votes
0 answers
99 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 ...
Turbo's user avatar
  • 13.6k
2 votes
1 answer
954 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$$ ...
Ricardo's user avatar
  • 31
2 votes
0 answers
1k 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$$ ...
KOF's user avatar
  • 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}...
Manfred Weis's user avatar
  • 12.6k
2 votes
0 answers
75 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 ...
A.2's user avatar
  • 123
2 votes
0 answers
103 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} \...
matematicaActiva's user avatar
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
  • 12.6k
14 votes
3 answers
1k 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,218
10 votes
0 answers
644 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
330 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
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
46 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
92 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
76 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
70 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
341 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
371 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
129 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
  • 3,910
1 vote
1 answer
196 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
  • 864
0 votes
1 answer
79 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
  • 491
1 vote
1 answer
107 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
15 votes
3 answers
986 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
462 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
26 votes
5 answers
1k 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,091
2 votes
2 answers
2k 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
109 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,837
3 votes
0 answers
70 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,837
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
879 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
  • 332
2 votes
0 answers
124 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
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
  • 987
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
  • 143
3 votes
1 answer
601 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
674 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
  • 680
1 vote
1 answer
181 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
200 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
190 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
177 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
  • 332
2 votes
1 answer
165 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
512 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
151 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
3 4
5
6 7
10