The 2024 Developer Survey results are live! See the results

# 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.

213 questions
Filter by
Sorted by
Tagged with
16 views

### What is a tight set for a face $F$ of the perfect matching polytope

I was reading the paper The Matching Problem in General Graphs is in Quasi-NC - Ola Svensson, Jakub Tarnawski. There the word mentioned in many places for example Definition 4.1 `$S$ is tight set for ...
1 vote
93 views

### Non-convex optimization with correlated minima

I am thinking of non-convex optimization problems where the minima are somehow correlated. Maybe there are symmetry relationships among minima or maybe there is regularity in spacing among minima in ...
• 651
117 views

### Can you find a counterexample / disprove my P=NP solution?

I've posted the full article here. The source code is available here. Basically, in the Linear Programming (LP) task, we solve a system of inequalities: one inequality per BSAT clause. In each ...
45 views

### Can you fix integral LP variables for a non-integral polytope without affecting the existence of integral optima?

Suppose I have a linear program $LP1=\{\mbox{Maximize }c^\top x \mid x\in \mathcal{P}\}$ for some polytope $\mathcal{P}\subseteq [0,1]^n$, which is known to have fractional extreme points. Suppose ...
• 341
65 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?
164 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 ...
• 646
162 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
72 views

• 73
1 vote
99 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 ...
• 1,153
80 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....
• 13.1k
46 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 ...
• 412
116 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$ ...
167 views

• 49
160 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 ...
• 49
116 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 ...
• 103
254 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. ...
• 885
1 vote
78 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 ...
• 539
1 vote