Questions tagged [linear-programming]

Mathematical and computational method for finding the best outcome in a given mathematical model where the list of requirements is represented as linear relationships.

Filter by
Sorted by
Tagged with
0 votes
0 answers
60 views

Is there an algorithm that finds a minimum vertex cover with an approximation factor of 3/2 for a planar graph?

Is there an algorithm that finds a minimum vertex cover with an approximation factor of 3/2 for a planar graph?
John Stuart's user avatar
3 votes
1 answer
150 views

Is there a high level (functional) language compiling to Mixed Integer Linear Programming problems?

Many different kinds of optimization problems can be expressed as Mixed Integer Linear Programming (MILP). The translation is usually very direct, and one has to encode invariants as constraints in a ...
Turion's user avatar
  • 616
0 votes
1 answer
112 views

Complexity of simplex method

What is the complexity of the simplex method in terms of Big O in the general case? I saw two variants: O(2^n) and O(2^(n+m)), where n is the number of variables and m is the number of constraints
Kitty's user avatar
  • 1
0 votes
1 answer
68 views

Solving non-linear programming with large number of variables

Let $n \in \mathbb{N}, [n] = \{1,2,\ldots,n\}$ and consider the following optimization problem: $$\max \sum_{i \in [n]} \sum_{j \in [n]} x_i \cdot x_j \cdot c_{i,j}$$ $$s.t.~~~~~~~~~~~~~~~~~~~~~~~~~~~~...
John's user avatar
  • 385
6 votes
0 answers
279 views

Techniques for solving huge linear programs

During the solution of some computational problem, we have arrived at a linear program of the following form: \begin{align*} \text{maximize} ~~ c x \\ \text{subject to} ~~ A x \leq b, x \geq 0 \...
Erel Segal-Halevi's user avatar
2 votes
2 answers
129 views

Linear Programming Sensitivity to Matrix

Consider a linear program in the following standard form: \begin{align*} &\max c^T x &\\ &\mbox{subject to:}\\ &A x \preceq b\\ &x \succeq 0 \end{align*} Its dual is \begin{align*}...
sd234's user avatar
  • 575
4 votes
0 answers
132 views

Which variant of the ellipsoid method was used for the Santa Claus problem?

As one of the steps in the article The Santa Claus problem (Bansal and Sviridenko, 2006) the following linear problem was considered (at the end of the second page, as the dual): \begin{align*} &\...
eden hartman's user avatar
3 votes
0 answers
75 views

Are there applications of Hyperbolic Programming other than Linear Programming and Semidefinite programming?

Title. It seems the most important special cases are LPs and SDPs. Are there other interesting special cases/applications for hyperbolic programming? (Apart from being super cool math on of itself) I ...
user3508551's user avatar
  • 1,153
3 votes
0 answers
60 views

Verifying LP solutions using primal-dual hybrids

We wish to solve an LP in the standard form Choose vector $x$ to maximize $c^T x$ subject to $Ax \le b$. Let $x^*$ be a feasible point. By LP duality, $x^*$ solves the LP iff we can write the ...
GMB's user avatar
  • 2,403
2 votes
0 answers
99 views

What kind of solver should I use for this hypergraph problem?

I have to list the solutions to the following hypergraph problem: There is a set of nodes, linked by edges that are 2-to-1 and bidirectional. The possible directions are either direct: 2 sources and 1 ...
Denis's user avatar
  • 8,843
0 votes
0 answers
125 views

Ensuring the connectivity of an undirected graph through linear programming

I am trying to solve a linear programming problem that deals with finding an optimal subgraph as a function of several parameters. The case is I am trying to model a constraint that ensures that the ...
AdCerros's user avatar
3 votes
1 answer
124 views

"Market" intuition for the dual of the max-weight matching LP

I recently learned about the Hungarian algorithm for maximum-weight matching in bipartite graphs and the "market" interpretation of the primal and dual LPs. (See also these notes.) The setup:...
Noah Singer's user avatar
3 votes
1 answer
220 views

Can the ellipsoid method be used with a randomized separation oracle?

Suppose we are trying to solve the following optimization problem: $$ \text{maximize } ~~ c\cdot y \\ \text{subject to } ~~ y\in S $$ where the region $S$ is described by an exponential number of ...
eden hartman's user avatar
0 votes
0 answers
95 views

How to prove that a given class of convex programs cannot be solved by linear programming?

Given the following program, where $f, g$ are convex functions: $$ \text{minimize}~~ f(x) \\ \text{subject to}~~ g(x)\leq 0 $$ the problem can be solved by convex programming algorithms, but it would ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
194 views

Solving linear programs with special structure

We have an application and at some point we need to solve a linear programming problem that looks like this: $$ \min\ w_{1,2} + w_{3,4} + w_{5,6}\\ x_i - x_j \leq c_{ij},\ \forall\ (i,j) \in C\\ x_1 - ...
Maltus's user avatar
  • 73
1 vote
0 answers
98 views

Max-flow while restricting flow on subsets of edges to be equal

Consider a max-flow network $G(V,E,c)$. Consider disjoint subsets of the arcs $R_1,…, R_k$. I want to find the maximum $s-t$ flow such that all the edges in the $R_i$ have equal flow. Obviously, this ...
user3508551's user avatar
  • 1,153
2 votes
0 answers
77 views

Parallel complexity of fixed dimension fixed constraints integer programming

Papadimitriou in https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf shows ILP is fixed parameter tractable in number of constraints and Lenstra in https://people.csail.mit....
Turbo's user avatar
  • 12.9k
0 votes
0 answers
45 views

What is the tightest lower bound known for the integrality gap of the Gilmore–Gomory LP for Bin Packing?

I know that it has been conjectured that the Gilmore–Gomory LP for 1-D BP (also known as configuration LP) has Modified Integer Roundup Property, i.e., Opt ≤ ⌈Opt_f⌉ + 1. However, I could not find the ...
John's user avatar
  • 385
0 votes
0 answers
114 views

Separation oracle for breaking cycles in directed graph

I am working on a directed graph problem and am collaterally interested to know whether there is a separation oracle for the following set of linear constraints. We are given a directed graph $G$ ...
reservoir's user avatar
3 votes
1 answer
161 views

Is there an approximate version of the strong duality theorem for linear programming?

Consider the following dual linear programs: $$ \min \mathbf{c^T x} ~~ \text{s.t.} ~~ A \mathbf{x} \geq \mathbf{b}, \mathbf{x}\geq 0; \\ \max \mathbf{b^T y} ~~ \text{s.t.} ~~ A^T \mathbf{y} \leq \...
Erel Segal-Halevi's user avatar
6 votes
1 answer
363 views

Is there a simplex-like algorithm that can be used with a separation oracle?

Linear programs can be solved in polynomial time using the ellipsoid method, but in practice the Simplex method is much more efficient, and the smoothed analysis framework of Spielman and Teng ...
Erel Segal-Halevi's user avatar
5 votes
1 answer
243 views

What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?

What is known about the LP gap of (the natural Held-Karp relaxation of) the (symmetric) Travelling salesman in special instances? I'm only aware of one special case where the extreme points are all ...
Hao S's user avatar
  • 228
5 votes
0 answers
130 views

Why is the ellipsoid method numerically unstable?

In the Ellipsoid method wikipedia entry under the performance section, it is mentioned that the Ellipsoid method often times is numerically unstable in practice: "On even "small"-sized ...
user3508551's user avatar
  • 1,153
0 votes
1 answer
234 views

Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?

Often, we can model combinatorial optimization problems with an Integer Program. Then there is an associated Linear Relaxation which drops the integrality constraints on the variables. Let's say we ...
Karagounis Z's user avatar
1 vote
0 answers
116 views

Is this proof of $LP$ being in $coNP$ correct?

I am referring to the natural decision version of the Linear Programming problem: given $A \in \mathbb{Q}^{m \times n}, \ b \in \mathbb{Q}^m, \ c \in \mathbb{Q}^n, \ \alpha \in \mathbb{Q}$, does there ...
reservoir's user avatar
2 votes
1 answer
241 views

Characterization of integral polyhedra

A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$. Equivalently, $P$ is integral if ...
Karagounis Z's user avatar
3 votes
0 answers
87 views

Using Baire Category to analyze the efficiency of the Simplex Method

I read from the wiki page of the Simplex Algorithm that we can "use Baire category theory from general topology, and to show that (topologically) "most" matrices can be solved by the ...
Ruiyuan Huang's user avatar
0 votes
0 answers
119 views

Prove that this linear relaxation has half-integral extreme points

Given a graph $G=(V,E)$, here is a Linear Relaxation of the edge cover polytope: (1) For each $v \in V, \sum_{e \in \delta(v)} x_e \geq 1.$ (2) For each $e \in E$, $0 \leq x_e \leq 1.$ Here $\delta(S)$...
Karagounis Z's user avatar
4 votes
0 answers
136 views

Complexity of real coefficients Linear Programs

I would like to know if there are known any polynomial time algorithms for deciding the feasibility of linear programs with real (not integers) coefficients. I know that for linear programs with ...
C Marius's user avatar
  • 141
3 votes
0 answers
203 views

(Integer) Linear Program formulation of planarity?

Q: Is there an efficient (I)LP formulation of planarity? More specifically, I am looking for a set of constraints that are satisfied by exactly all planar graphs on $n$ vertices, in order to optimize ...
GBathie's user avatar
  • 296
2 votes
1 answer
209 views

Is this homework problem on T-joins wrong? [closed]

In Question 9.3a, it states that if $T=V$, then the minimum cost perfect matching is the minimum cost T-join. Is this actually true? I think I have a counterexample which I have drawn below.
Karagounis Z's user avatar
4 votes
1 answer
346 views

Proof of $LP$ is in $coNP$ without showing it is in $P$?

Is there a proof that linear programming is in $coNP$ without showing it is in $P$? If so what is the strategy?
Turbo's user avatar
  • 12.9k
6 votes
1 answer
91 views

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

Let $G=(V,E)$ be graph. Recall that a cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in ...
dohmatob's user avatar
  • 291
5 votes
0 answers
98 views

reference request: greedy algorithm for fractional interval covering

Reference Request I've found a natural greedy algorithm for the problem below. My question is: what is already known about fast algorithms for this problem (faster than general linear programming, ...
Neal Young's user avatar
  • 10.6k
1 vote
1 answer
124 views

Ensuring integral maximizer from integral linear program

An integral linear program is one that has a maximizer that is integral. Sometimes it's possible to prove that a particular LP has this property, for example by proving that it's constraint matrix is ...
orlp's user avatar
  • 885
1 vote
0 answers
130 views

Is the edge cover polytope integral on graphs with self-loops?

It is well known that the edge cover polytope is integral on simple graphs. I am wondering whether this also holds for graphs with self-loops. Here is a Linear Relaxation of the edge cover polytope, ...
Karagounis Z's user avatar
1 vote
0 answers
165 views

Is the matching polytope integral?

In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf they prove the integrality of the matching polytope using the integrality of the perfect matching polytope. The ...
Karagounis Z's user avatar
1 vote
0 answers
195 views

Separation oracle for hitting all small cut on a graph?

We are given as input an undirected graph $G=(V,E)$, weights $w_e \ge 0$ for all $e\in E$ and an positive integer $k$. We aim to select a set of edges with the minimum weight, such that the cut set of ...
Mengfan Ma's user avatar
-2 votes
2 answers
656 views

Proof that optimal solutions of LP Relaxation of independent set are half-integral

I saw somewhere that optimal solutions of LP Relaxation of independent set are half-integral, by what I mean the possible values of a solution are ${ \{0,0.5,1 \} }$. I'm looking for proof of that. ...
Jakub Jabłoński's user avatar
1 vote
1 answer
309 views

Intuition behind the Charikar's LP formulation for densest subgraph problem

I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper. Just mentioning the LP for maximum density of a ...
am_rf24's user avatar
  • 23
1 vote
1 answer
223 views

Minimum non-zero variable in the optimal solution of linear programming

Suppose we have a linear programming about the vertex packing of a hypergraph G=(V,E), with size $n = \sum_{e \in E}|e|$. We introduce a variable $x_v$ for each vertex $v \in V$. $$\max \sum_{v} x_v ...
Xiao's user avatar
  • 49
0 votes
0 answers
157 views

linear programming with non-integer constraints

Suppose we have a linear progamming about vertex packing of a hypergraph (V,E), with size $n = \sum_{e \in E} |e|$. We introduce a variable $x_v$ for each vertex $v \in V$. The fractional version is ...
Xiao's user avatar
  • 49
-1 votes
1 answer
109 views

Is it possible to approximate the solution of NP-Hard problems in polynomial time using linear programming? [closed]

Suppose we have a NP-Hard problem such as the k-col, which is meant to determine if a graph may be colored using at most ...
G Oliveira's user avatar
3 votes
1 answer
241 views

Minimal number of hyperplanes needed to separate sets of points from one other set

Let $\mathbb{R}^d$ be our space. We have a single good set of points $g$, and a collection of bad sets of points $B$. We assume that for all $b \in B$ the convex hulls of $g$ and $b$ are disjoint. ...
orlp's user avatar
  • 885
1 vote
0 answers
77 views

Time complexity of alternation free quantified linear program with no free variables and only existential quantifications

We know $\exists x\in\mathbb R^n:Ax\leq b$ is standard linear program. I am mainly looking at following case of quantified linear program with no free variables with only existential quantifications ...
VS.'s user avatar
  • 539
1 vote
0 answers
74 views

Sherali-Adams lowerbound instance of Unique Games constructed via CLT

The question comes from the following paper I have been reading: [1] Integrality Gaps for Sherali–Adams Relaxations. SODA'09. Moses Charikar, Konstantin Makarychev, Yury Makarychev. Theorem 6.1 of [...
xyguo's user avatar
  • 191
2 votes
1 answer
174 views

Finding whether $n$ polytopes have nontrivial intersection from pairwise comparisons

I have a set of $n$ convex polytopes of the form $$\mathcal{L_i} = \{ \beta \mid C_i \beta \leq 0 \}$$ where $C$ is a matrix and $\beta$ is a vector. I know that for each pair of polytopes $$(\...
Magdalen Dobson's user avatar
0 votes
1 answer
269 views

finding maximum weight subgraph

My graph is as follows: I need to find a maximum weight subgraph. The problem is as follows: There are n Vectex clusters, and in every Vextex cluster, there are some vertexes. For two vertexes in ...
Refrain's user avatar
  • 67
5 votes
1 answer
185 views

Complexity of Finding Largest Set of Intersecting Convex Polytopes

I have a set of $n$ convex polytopes, and I wish to find the largest subset of those polytopes that shares at least one point in common. I think that this problem should be NP-hard, but I am ...
Magdalen Dobson's user avatar
1 vote
0 answers
348 views

Does simplex algorithm run in polynomial on Bipartite Perfect matching polytope?

It is well known that simplex algorithm runs in exponential time in worst case. However are there situations (necessary and sufficient conditions) where simplex algorithm runs in polynomial time? In ...
Turbo's user avatar
  • 12.9k

1
2 3 4 5