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
0
votes
0answers
8 views

Subtour-gluing constaints for ILP formulation of TSPs

If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
0
votes
0answers
6 views

Bounds on number of subtour elimination constraints needed for solving TSPs to optimality

Question: what is the "subtour complexity" of the TSP, that measures how the number of subtour constraints the ILP, that finally solves a TSP instance to optimality, can have in the worst ...
0
votes
0answers
64 views

Why is Gaussian distribution always chosen for smoothed analysis?

I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...
0
votes
1answer
31 views

Do we really need degree constraints for ILP formulations of TSP problems

The Dantzig-Fulkerson ILP-formulation of the symmetric TSP is $$\min\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n c_{ij}x_{\lbrace i,j\rbrace}\quad\text{s.t.}\\ \sum\limits_{j\ne i,\,j=1}^n x_{\lbrace ...
2
votes
0answers
65 views

Reference for Chebyshev centers

Today, I came across the concept of Chebyshev center twice. In particular, it is the key tool in the very elegant paper "A fixed point theorem for $L^1$ spaces" by Bader, Gelander and Monod. ...
0
votes
0answers
14 views

Can the most distant edge-disjoint pair of perfect matchings be calculated efficiently

Question: has the linear program \begin{align} \text{LP:} \\ & \sum_{ij} w_{ij}\cdot(b_{ij}-a_{ij})\ \stackrel{!}{=}\ \max \\ \text{s.t. } & \sum_{ij}a_{ij}\ \le\ \sum_{ij}b_{ij} \\ & 0\ ...
1
vote
0answers
30 views

Second-order envelope theorem for linear programming

Consider parameterized linear programming $V(\theta) = \max_x \langle c(\theta),x\rangle$ s.t. $A(\theta)x\leq b(\theta)$, $x\geq 0$. Let's also assume $c,A,b$ are infinitely differentiable with ...
0
votes
0answers
22 views

Sum of all integer binary solutions of a TUM linear system

I have the following problem: $A x = b$ where $A$ is a $m \times n$ total unimodular matrix (TUM) with entries in $\{0,1\}$ and $b$ is a $m$-vector of strictly positive integers. Let $\mathcal X$ be ...
0
votes
0answers
62 views

Minimum circumscribed ellipsoid of $\mathcal H$-polytope

Given matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^n$, consider the $\mathcal H$-polytope $P$ defined as follows $$ P := \left\{ x \in \mathbb{R}^n : Ax \leq b \right\} $$ I ...
0
votes
0answers
119 views

Any technique for linearization, or linear approximation?

Consider the following Matrix constraint: $$ \begin{bmatrix} -U+\psi\Sigma_b^{-1} & V \\ V^T & -V^TU^{-1}V+\tau_2 -\psi \end{bmatrix} \leq 0 $$ where $\Sigma_b$ is a known positive definite ...
0
votes
1answer
57 views

How hard is a linear programming with a bounded constraint?

Background: I am reading Greg Kuperberg's answer to the question Deciding membership in a convex hull. I am thinking about the complexity of ''Deciding membership in a convex hull''. Restate the ...
2
votes
0answers
79 views

Continuum of Lagrange multipliers, duality gap, and minimax theorem

Suppose I have a linear optimization problem involving random variables on some (infinite) probability space $\Omega$. For example, need to maximize expectation $E[Q]$ of random variable $Q$ subject ...
0
votes
1answer
67 views

How do you call a linear programming problem when the solution should be "constrained" to a norm?

(apologies for the n00b question) Let's say we have a vector of length $n$, with to-be-determined values: $a_1, a_2, ...,a_n$. And we have information that partial sums of these elements are equal to ...
0
votes
0answers
43 views

Geometric of sphere caps with infinite radius $R$ (asymptotic) in dimension $C$

Let $B_C(R)$ be the Ball in $R^C$ with radius $R$, the vectors $w_1,w_2,\dots,w_{C-1}\in R^C$ is the normal vector of hyper half plane, the area $$\mathcal{K}=\{x:w_1^Tx\leq0, w_2^Tx\leq0,\dots,w_{C-1}...
1
vote
0answers
47 views

Optimization problem on trace of complex matrix product

Given a complex rectangular matrix $A$ $(k \times n)$, I am interested in solving the following optimization problem over $(k\times n)$ complex matrices $x$: $$ \mathrm{arg}\max_X \,\mathrm{trace}(X^...
2
votes
0answers
68 views

Polyhedron coordinate bound

Given a polyhedron $$Ax\leq b$$ where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
1
vote
0answers
42 views

Detecting non-negativity of a single constraint by polyhedral constraints - $II$

Let $$\langle a,x\rangle=b$$ be a linear constraint where $x\in\mathbb R^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\mathbb Z_{\...
0
votes
1answer
96 views

Detecting non-negativity of a single constraint by polyhedral constraints - $I$

We consider $$\langle a,x\rangle=b$$ (linear constraints) where $x\in\mathbb R_{\geq0}^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\...
0
votes
1answer
65 views

Iterations of Dantzig-Wolfe Decomposition for a Simple Linear Programming problem

This arises from an engineering problem I am working on. Let $\mathbf{c}_i,\mathbf{a}_i,\mathbf{b}_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the ...
0
votes
0answers
22 views

Characterizing a variant of completely-Q matrices in linear complementarity problems

Given an $(n\times n)$-matrix $A$ (over the reals) and a vector $q \in R^n$, the linear complementarity problem $LCP(A,q)$ is the following problem: Find $w,z \in R^n_+$ such that $$w = q + Az,$$ and $...
0
votes
0answers
75 views

Number of vertices in a polyhedron

Consider polytopes $$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$ $$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$ $$B[z_{1},z_{2},z]'\leq c$$ having vertex count $v_1,v_2$ and $v$ respectively. We ...
1
vote
1answer
48 views

$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves

$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
1
vote
0answers
152 views

continuity of linear programming

I have the following conjecture: Given a closed convex set $S \subseteq \mathbb{R}^n$ and one of its exposed face $F=\{x \in S \mid \pi x = \pi_0\}$, where $\pi x =\pi_0$ is the supporting hyperplane ...
0
votes
0answers
40 views

Karush-Kuhn-Tucker in discrete time dynamic optimization

I need to solve the following problem: $\max_{p_t\in [\phi_1(s_t),\phi_2(s_t)]} \sum_{t=0}^\infty p_t\times(a+\alpha s_t-p_t)$, subject to $s_0$ given and $s_{t+1}=\beta(s_t+\eta(a+\alpha s_t-p_t))$. ...
1
vote
1answer
58 views

Optimality gap between a joint linear program and decoupled sub programs

Let $\mathbf{c}_i,\mathbf{s}_i$ be given entry-wise positive $n\times 1$ vectors for $i\in[1,\dots,d]$. Let $\tau, \alpha_1,\dots, \alpha_d$ be given positive constants. Consider the linear ...
1
vote
0answers
70 views

Algorithm for deciding feasibility of linear programs [closed]

Suppose I have the simple linear program $$Ax \geq 0, \quad x \geq 0$$ We know that this system has a solution (for example, $x=0$). But, what if we made this rule for this system? $$Ax \geq 0, \quad ...
0
votes
0answers
233 views

Maximizing a piecewise-linear convex function

Crossposted on Operations Research SE. I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables: ...
0
votes
0answers
23 views

Analytic formula for $D(x,y) := \sup_{z \in B_p} \|z-x\|_1 - \alpha\|z-y\|_1$, where $\alpha \ge 0$ and $B_p$ is the unit $L_p$-ball

Let $\alpha \in [0,\infty)$ and $p \in [1,\infty]$, and consider the function $D_\alpha:B_p \times B_p\to \mathbb R$ defined by $$ D_{\alpha,p}(x,y) := \sup_{z \in B_p} \|z-x\|_1 - \alpha\|z-y\|_1, $$...
1
vote
0answers
102 views

Decomposition of Polyhedral - An example

There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system $$ \...
0
votes
1answer
70 views

A question on graph partitioning

Given a connected un-directed simple graph $G=(V,E)$, is there a polynomial time algorithm to find the smallest subset $S$ of $V$ such that each node in $V \setminus S$ has at least 50% of its ...
1
vote
1answer
178 views

Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]

Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
3
votes
0answers
68 views

Additional symmetries of the Traveling Salesman Polytope

Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...
1
vote
1answer
142 views

Constructing representations of probability revision functions

Let $P$ be a probability distribution over a finite Boolean algebra $\mathfrak{B}$, and fix a parameter $t_{P} \in (\frac{2}{3}, 1)$. Define the `revision function of $P$', $R_{P}: \mathfrak{B}\...
0
votes
0answers
11 views

Identifying essential degree constraints for ILP formulations of combinatorial optimal graph problems

Many combinatorial graph problems impose degree constraints on vertices; e.g. that the degree of every vertex in the solution to the TSP must be 2. In all LP-formulations I have encountered so far, ...
1
vote
1answer
89 views

Allowing an "OR" option between equations in a linear program

I am looking for a way to express an "or" option in a system of linear inequalities for a linear program I am working on. I will explain what I mean precisely: Lets say I have a set of ...
8
votes
1answer
452 views

Minesweeper as a linear algebra problem

I've written a computer program to generate and solve minesweeper games. Once I've eliminated the obvious mines and safe squares I look at each remaining connected setsin turn and formulate a linear ...
0
votes
0answers
56 views

Convex optimization under asymmetric loss in infinite dimensional space

The following problem is common in financial economics $$ \min_{m \in L^2} \mathbb{E}[ \phi(y(\theta)-m)] \quad \text{s.t. } \mathbb{E}[ mx ]= q $$ That is, given a random variable $y(\theta)$ ($\...
2
votes
1answer
120 views

linear programming with $n$ choose $r$ variables

Given parameters $r < n$, define $m = {n \choose r}$ and let $A$ be the $n\times m$ matrix whose columns are all the vectors with $r$ $1$'s and $n-r$ $0$'s. Let $b$ be a positive $n$-vector. Is ...
0
votes
1answer
286 views

Integer solution of optimal transport

Let us consider two vectors $\mathbf{a}=(a_1,...,a_n)$ and $\mathbf{b}=(b_1,...,b_m)$ so that each quantity is an integer $a_i,b_j \in \mathbb{N}$. It represents for example supply and demand. Let $\...
1
vote
1answer
610 views

How to minimize l1-norm constrained by "infinity norm"

Let $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m $. I have the following two problems: P.1. \begin{equation} \underset{x\in\mathbb{R}^n}{\text{minimize}} \| Ax-b \|_1 \\ \text{s.t. } \| x \...
0
votes
1answer
88 views

An otherwise linear matrix equation with the presence of a signum function : reference request

Consider the equation $$\pmb{c}+\text{sign}(G\pmb{c}) = L$$ $\pmb{c}$ is a $n\times1$ matrix. $G$ is a $n\times n$ matrix which is also positive definite. matrices $G$ and $c$ are real. $L$ is a $n\...
3
votes
0answers
91 views

Convex optimization upper bound for a non-linear optimization

Is there any good convex optimization problem based upper-bound for the following non-linear optimization problem? \begin{align} \max_{x_1,\ldots,x_N}&\quad \sum_{n=1}^{N} \log(1+\frac{x_n}{1+\...
0
votes
0answers
59 views

Solutions to matrix equations in the non-negative integers

For an integer matrix $S$, and an integer vector $y$, I'm looking for solutions to $xS = y$ where the entries in $x$ are in the non-negative integers. I've been doing this with Sage's mixed integer ...
1
vote
0answers
16 views

Fundamental regions in convex programming

Fundamental regions of linear programming are polyhedra (since those are the objects of intersection of linear inequalities) and for semidefinite programming it is spectrahedra (https://math.berkeley....
1
vote
0answers
86 views

Convergence of infinite linear programming

Suppose we have the following linear program (LP1), $$\min_{f \in \mathcal{C}} \int_{\mathbb{R}} f(t) \cos(2 \pi x_0 t) dt \\ \text{subject to } \int_{\mathbb{R}}f(t)dt = 1 \\\forall x\in [0,1]: \int_{...
-1
votes
1answer
80 views

How to solve MILP problem on several linear subspaces

I have a set of close mixed-integer programming problems. More exactly, all the problems share the same set of (binary and continuous) variables, the same set of linear inequality constraints, and the ...
2
votes
0answers
37 views

Notion of distance between linear programs

Consider the linear programming problem \begin{align} \max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1 \end{align} where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
1
vote
0answers
74 views

What is the relation between different generalizations of linear programming?

Linear programming subsumed by each of Semidefinite programming (SDP) Convex programming (CXP) SOS programming (SSP) Is there any relation between each pair in the three? Are all three equivalent in ...
1
vote
0answers
26 views

Reference for the algorithm to find the intersection between a subspace and positive orthant

I came across this algorithm, in this question Algorithm for the intersection of a vector subspace with a cone of non-negative vectors ; Is there any reference for the algorithm described in the ...
0
votes
1answer
106 views

Linear programming with exponential inequalities and rational variables

If we are given a set of real linear inequalities then using elimination theory or just linear programming we can decide. If the program also has inequalities of form $2^x\leq g$ in addition to linear ...

1
2 3 4 5
9