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
0 answers
27 views

How to find such a Markov matrix?

Suppose A is a m×n Markov matrix, and C is a m×k Markov matrix. How to decide (analytically or numerically) whether there is a n×k Markov matrix such that AB=C? I feel that it is a linear programming ...
user avatar
  • 9
1 vote
1 answer
231 views

Who called Farkas' fundamental theorem a lemma?

Farkas proved his famous result (which, nowadays, is fundamental in optimization theory) in 1902 and called it Grundsatz der einfachen Ungleichung which may be translated as fundamental theorem of ...
user avatar
0 votes
0 answers
60 views

Using the duality theorem for an optimization problem with two variables

I wish to apply the duality theorem to the optimization problem: $$\text{minimize}~~s$$ $$\text{subject to}~~g_j(x)\leq{s},~~\text{for all}~~j=1,...,r,~~x\in{X},~~s\in{\mathbb{R}},$$ where $X\subseteq{...
user avatar
  • 1
1 vote
1 answer
175 views

Finding a special solution in a solution set over F2

given a solution set of a linear system of the following form $$ \{ \begin{bmatrix} x_{1} \\ \vdots \\ x_{n} \end{bmatrix} = \vec{v_1} * x_1 + \dots + \vec{...
user avatar
0 votes
1 answer
52 views

What is the best way to choose initial basis when applying simplex method to an equality form of LP?

Currently I'm trying to write a practically fast LP solver for a sparse instance, which is by simplex method with LU decomposition and eta-matrix update. In the development I realized that I'm not ...
user avatar
4 votes
2 answers
121 views

Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment

I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
user avatar
0 votes
1 answer
78 views

Correct way to conduct equilibrium scaling of linear/integer/MIP program

I would like to scale my linear/integer program and also mixed-integer program using the equilibrium scaling method. I have worked on two research papers and one research book. However, they did the ...
user avatar
  • 21
1 vote
0 answers
28 views

Linear programming robustness to input perturbations

I'm running a linear program whose parametrization depends on the output of a neural network. I was wondering if there exist results on how robust linear programs are towards perturbations in their ...
user avatar
  • 11
1 vote
1 answer
100 views

How to maximise infinity norm of $x$ with constraint $Ax \le b$ using linear program? [closed]

I want to maximise the infinity norm of $x$, subject to constraint: $Ax \le b$. I think you can use a linear program to solve this, but how do you go about formulating it?
user avatar
0 votes
0 answers
43 views

Explicit equation for border of the Minkowski sum of sets

Assume we have sets of the form $$ M_j = \{x\in\mathbb{R}^d : f_j(x) \le 0,x \ge 0\} $$ where $x\ge 0$ means $x_i \ge 0 \quad \forall i=1,\dots, d$. Goal I am looking for an (explicit) representation ...
user avatar
  • 121
1 vote
0 answers
77 views

Solution of a simple optimization problem

Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem? \begin{align} \min_{\mathbf{...
user avatar
  • 129
0 votes
0 answers
21 views

Does the best stochastic stationary policy has the same optimal cumulative reward of an finite horizon MDP as a deterministic stationary policy?

I have this question when reading Gergely et al (2014)'s paper. Let me define the question. Definition: A online learning in MDP problem up to time $T$ consists of $(S,A,P,d_1,R)$ $S$: state space. $...
user avatar
0 votes
0 answers
50 views

The best unitary matrices that approximate a matrix product

Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...
user avatar
  • 129
0 votes
0 answers
13 views

Calculating lower bounds for optimal tours via approximate tours

Let $T=\lbrace t_{i,\pi(i)}\rbrace\subset E,\ S=\lbrace s_{ij}\rbrace =E\setminus T$ denote the set of tour edges, resp. of tour "secants". Let $\lbrace x_{i,\pi(i)}\rbrace \in \lbrace 0,1\...
user avatar
1 vote
0 answers
22 views

How to chose the start vector for the MTZ variables

In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ ...
user avatar
0 votes
0 answers
29 views

Convergence rate for gradient descent approximation algorithms for linear programming

Consider a canonical form for linear programming $$\max_{x} c^Tx \quad s.t. \quad Ax\leq b $$ where $A\in \mathbb{R}^{m\times n}$. If a suboptimal solution is acceptable instead of an exact solution, ...
user avatar
1 vote
0 answers
72 views

Drawing a 3D object in a 3D environment, and converting to math [closed]

So I have been granted a free time and I want to work on a project but first I had to research. As we know, lines have infinite points, and with lines, we can create infinite shapes. I want to let ...
user avatar
0 votes
0 answers
42 views

How to find a set given its support function

Let $\mathcal{U}$ be a convex and compact set. Its support function is defined as $\delta^*(v|\mathcal{U})=\sup_{u\in \mathcal{U}} v^T u$. Assume that we are given the support function $\delta^*(v|\...
user avatar
0 votes
0 answers
39 views

Simplest sensitivity analysis in semi-infinite linear programming

Consider a standard linear program of the form \begin{align*} \min_{x}c^{\top}x & \,\,\text{subject to}\\ Ax & =b\\ b & \geq0\,. \end{align*} It is well-known that if we perturb the right-...
user avatar
  • 3,678
0 votes
0 answers
30 views

Subtour-gluing constraints 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-...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
74 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 ...
user avatar
  • 11
0 votes
1 answer
40 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 ...
user avatar
2 votes
0 answers
70 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. ...
user avatar
0 votes
0 answers
15 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\ ...
user avatar
1 vote
0 answers
33 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 ...
user avatar
0 votes
0 answers
25 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 ...
user avatar
0 votes
0 answers
73 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 ...
user avatar
0 votes
0 answers
124 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 ...
user avatar
0 votes
1 answer
71 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 ...
user avatar
2 votes
0 answers
116 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 ...
user avatar
  • 701
0 votes
1 answer
106 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 ...
user avatar
0 votes
0 answers
44 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}...
user avatar
1 vote
0 answers
79 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^...
user avatar
  • 327
2 votes
0 answers
71 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\|_\...
user avatar
  • 12.9k
1 vote
0 answers
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_{\...
user avatar
  • 12.9k
0 votes
1 answer
97 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 $\...
user avatar
  • 12.9k
0 votes
1 answer
75 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 ...
user avatar
  • 1,351
0 votes
0 answers
80 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 ...
user avatar
  • 12.9k
1 vote
1 answer
65 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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
1 vote
1 answer
63 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 ...
user avatar
  • 1,351
1 vote
0 answers
71 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 ...
user avatar
0 votes
0 answers
339 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: ...
user avatar
  • 101
1 vote
0 answers
121 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 $$ \...
user avatar
  • 111
0 votes
1 answer
71 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 ...
user avatar
  • 1,126
1 vote
1 answer
338 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 ...
user avatar
  • 11
3 votes
0 answers
71 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 $...
user avatar
  • 9,513
1 vote
1 answer
148 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}\...
user avatar
  • 601
1 vote
1 answer
96 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 ...
user avatar
  • 141

1
2 3 4 5
9