Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

0
votes
0answers
41 views

All or nothing Integer Multi Commodity Flow

I couldn't find any approximation algorithms for all or nothing integer multi commodity flow. By all or nothing, I mean I wish to maximize the number of commodities fully transferred from their source ...
0
votes
0answers
65 views

finding an integral solution to a LP which does not violate constraints by much

Consider the following LP: Maximize $\sum_{i=1}^{N} p_i x_i$ subject to $0 \leq x_i \leq 1, Ax \leq b$ where $A$ is a $M \times N$ matrix with nonnegative entries. Let $T$ be the maximum column sum ...
6
votes
1answer
134 views

How “hard” is it to maximize a polynomial function subject to linear constraints?

General Problem Suppose we have a multivariate polynomial function $f(\mathbf{x})$, and several linear functions $\ell_i(\mathbf{x})$. What is known about the complexity of solving the following ...
1
vote
0answers
36 views

Monotone complexity of PLP

Blum and Nisan show Positive Linear Programming could be done in $NC$ if we only ask for approximate solutions. This paper https://pdfs.semanticscholar.org/8dc7/5aa9d72864022d848c3e599c5f24d9d527e7....
3
votes
1answer
119 views

On complexity of linear programming with quadratic equality/inequality constraints?

Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ ...
5
votes
2answers
305 views

Complexity of finding a consistent hyperplane

Given $m$ binary labeled points in $\mathbb{R}^d$, it is well-known that in general it's NP-hard to find a hyperplane that minimizes sample error. A brute-force search considers all $O(m^d)$ sample ...
2
votes
0answers
56 views

Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$

The problem of giving an explicit formula for $A_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A_q(n,d)$ is given by the maximum number of codewords in a q-ary ...
0
votes
0answers
43 views

Problem: Scheduling diverse teams while minimizing frequency

I have the following problem which I have been asked to solve. I like to think that a few years ago, I'd be able to do it myself, but these days I must admit that help is good :) Given $n$ employees $...
3
votes
0answers
123 views

Max and Min Equations with Linear Programing

I am given constants $c_{i,j}$ as inputs. I want to find values for the variables $x_i$ that satisfy a system of equations, where each equation either takes the form $$x_i = \max\{x_j + c_{i,j} : j \...
1
vote
1answer
104 views

Solving linear program with 1 quadratic constraint complexity

Consider the following linear program, $$\min y \\ xc_1 \leq c_2 + yz,\\ x = x_1 + \dots + x_n,\\ z \leq x_1 + x_2, \\ z \leq x_2 + x_3, \\ \vdots\\ z \leq x_{n-1} + x_n, \\ x,x_1, \dots, x_n,y,z \...
-3
votes
1answer
108 views

What is wrong with this procedure to convert quadratic programming to convex quadratic programming?

Consider the feasibility quadratic program with constraint $$\sum_{i=1}^nc_{i1}x_{i}\leq \ell_1$$ $$\vdots$$ $$\sum_{i=1}^nc_{it}x_{i}\leq \ell_t$$ $$\sum_{i,j=1}^na_{ij}x_{i}x_{j}+\sum_{i=1}^nb_{i}x_{...
4
votes
0answers
153 views

What exactly did Lenstra prove on mixed integer linear program?

I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
6
votes
1answer
177 views

Cases of Linear programming known to be in $NC$?

Linear programming is $P$-complete. However are there special situations where we know an $NC$ algorithm?
3
votes
1answer
82 views

About the sign-rank of the Minsky-Pappert function

Apologies this might be a very trivial thing I am getting confused by! Firstly in corollary 1.1 (page 3) in this paper, https://eccc.weizmann.ac.il/report/2016/075/ the authors claim that they have ...
1
vote
1answer
170 views

Max weight travel on a graph with deadline

Given a deadline $D>0$ and a complete graph $K_n$ (with loops) in which each edge $e_{ij}$ has a weight $w(e_{ij}) \ge 0$ and a travel time $l(e_{ij}) > 0$. Starting from one of the nodes, we ...
18
votes
1answer
409 views

How not to compute the smallest circle enclosing a finite set of circles

Suppose we have a finite set $L$ of disks in $\mathbb{R}^2$, and we wish to compute the smallest disk $D$ for which $\bigcup L\subseteq D$. A standard way to do this is to use the algorithm of ...
0
votes
1answer
52 views

How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming? [closed]

Edges are given in form of $X_{ij}$, which denotes whether there is edge in between $i^{th}$ and $j^{th}$ vertex. I am solving integer optimization problem and want to add this constraint to it.
2
votes
1answer
180 views

Are there specific examples of integral polyhedra that are neither Totally Unimodular nor Total Dual Integral?

It is well known that if a constraint matrix $A$ is total dual integral or totally unimodular, then this is a sufficient condition of integrality of the polyhedron defined by the system $Ax \leq \beta$...
5
votes
1answer
219 views

Solving linear equations involving min

Solve for $\alpha$ if solution exists: $\min(r_1, s_1 \alpha_1) + \min(r_2, s_2\alpha_1) = d_1$, where $r_1,r_2,s_1,s_2,d_1$ are integer constants. One way seems to be enumerate all possible outcomes,...
4
votes
1answer
122 views

Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K

I find myself with another graph problem that I can't find the name of. I was wondering if anyone was able to identify if this problem and any efficient algorithms to solve it are known. The ...
6
votes
1answer
138 views

Brute force search algorithm for semidefinite programming (representation of spectrahedron)

I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for ...
3
votes
1answer
180 views

List of Pivot rules for simplex methods

Any implementation of the simplex method depends on the choice of pivot rule, which determines how the corners of the search space polyhedron are traversed. Many different have been proposed ...
4
votes
0answers
170 views

Are there integer programs with small coefficients that only have large solutions?

It is well-known that if an integer linear program has a feasible solution, then it has a feasible solution whose bit size is polynomially bounded. For example, here is Theorem 13.4 from Papadimitriou ...
1
vote
1answer
260 views

Is finding an optimal solution to this Knapsack-like problem NP-hard?

Suppose our inputs are a set of objects with weights $w_1,...,w_n$. We have two separate sets of profits: $p_1,...,p_n$ and $v_1,...,v_n$. We wish to maximize $ \sum_{i=1}^{n} p_i(1-x_i)+\alpha_i ...
6
votes
1answer
444 views

The Average-case Complexity of Simplex Algorithm

I was wondering if there are any results on the average case complexity of the simplex algorithm. Let $A \in \mathbb{R}^{m \times n}$ be the matrix in the linear constraint. I know that Smale did ...
1
vote
0answers
58 views

Convex hull of codebook (LP-decoding)

So the well-cited article by Feldman et al from 2005 has a method of constructing the convex hull of the feasible set for ML-decoding. Basically, he considers the parity check matrix $H$ as a Tanner ...
13
votes
4answers
731 views

Finding the sparsest solution to a system of linear equations

How hard is it to find the sparsest solution to a system of linear equations? More formally, consider the following decision problem: Instance: A system of linear equations with integer coefficients ...
2
votes
0answers
294 views

How to prove integrality of LP with not totally unimodular matrix

I have a linear program (LP) for which the constraint matrix is NOT totally unimodular (TU). However, even though constraint matrix is small (14x20), extensive generation of random coefficients for ...
0
votes
2answers
386 views

NP completeness of linear $0-1$ assignment problem

Supposing we have a linear equation in $n^2$ variables with integer (negatives allowed) coefficients of at most $m$ bits each. Partition $\Pi_1$ the variables into $n$ disjoint sets of $n$ variables ...
1
vote
1answer
159 views

On a Linearization of the Quadratic Assignment Problem

The Quadratic Assignment Problem formulated as an integer program: \begin{align} \mbox{minimize}\quad & \sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n ...
1
vote
0answers
177 views

Linear Programing with Rounding for the Fire Station Problem

Consider the following fire station problem: The input is a positive integer k and a complete undirected graph $G = (V,E)$ with distances on the edges. The distances form a metric: $d(v, v) = 0$, $d(...
12
votes
0answers
182 views

Linear programming with superpolynomially many constraints?

(The specific problem I have is stated as precisely as I could in the very last paragraph which starts with a boldface "Question:", up until then the question provides context for it.) Say we have an ...
2
votes
0answers
150 views

Inclusion of polytopes

Consider the following two system of linear (in)eqaulities: $S = Ax \leq b;\; Cx = e$ $T = Dx \leq d;\; Gx = g$ How can I check if $S\cap \neg T=\emptyset$ where $\neg T$ is the complement of the ...
3
votes
0answers
90 views

Equivalence of weighted Minkowski sums

Given $n$ polytopes $P_1, \cdots, P_n$, each $P_i$ is given as the V-representation, i.e., a set of $m$ points as its set of vertices. Furthermore, consider a variant of the Minkowski sum (somehow ...
6
votes
1answer
233 views

Decide whether a point is a vertex of a polytope?

Inspired by the question, I would like to ask the following question: Input: A polytope specified by $\Theta=\{\vec{x}\mid A\vec{x}\leq b\}$, and its affine projection $f(\Theta)= \{(\vec{c}_1\cdot \...
2
votes
0answers
66 views

Check whether a point is a vertex of Minkowski sum of polytopes

Given $n$ polytopes $$\begin{align*} P_1&=\{(f^1_1(\vec{x}_1), \cdots, f^1_m(\vec{x}_1))\mid A_1\vec{x}_1\leq b_1\}\\ P_2&=\{(f^2_1(\vec{x}_2), \cdots, f^2_m(\vec{x}_2))\mid A_2\vec{x}_2\leq ...
2
votes
0answers
51 views

How to compute the basis

Given $n$ sets of linear constraints $\Theta_1, \cdots, \Theta_n$ which are over $\vec{x}_1, \cdots, \vec{x}_n$ respectively where $\vec{x}_i$ and $\vec{x}_j$ are pairwise disjoint, and $W= \begin{...
14
votes
2answers
917 views

Checking equivalence of two polytopes

Consider a vector of variables $\vec{x}$, and a set of linear constraints specified by $A\vec{x}\leq b$. Furthermore, consider two polytopes $$\begin{align*} P_1&=\{(f_1(\vec{x}), \cdots, f_m(\...
5
votes
0answers
89 views

LPs with “sparse solutions”

Consider a graph optimization on a graph with n vertices and m edges that can be written as an LP (like say bipartite matching). By the duality with vertex cover, we know that there's a sparse dual ...
1
vote
0answers
109 views

Runtime of Gomory's Cutting Plane Algorithm

I read in several sources that the use of Gomory's cuts exclusively in Integer Programming was shown to be inefficient in practice when Gomory had created them. But later down the line they were shown ...
4
votes
1answer
112 views

Polytopes convex hull

Assume $P_1$, $P_2$ and $Q$ are axis-parallel polytopes in $\mathbb{R}^d$. Is it true to say that checking $CH(P_1\cup P_2)\neq Q$ is NP-hard? There is a similar result for the general polytopes but I ...
7
votes
0answers
141 views

SVM - running time for detecting if data is linearly separable?

If my understanding is correct, one way to check if a set of $m$ data points is linearly separable is to use support vector machines to find a maximum margin hyperlane for separating the data; the ...
2
votes
1answer
157 views

H-representation of convex hull

Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows: $P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ ...
7
votes
2answers
252 views

What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?

What are some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems, especially any linear programs which had helped in getting good ...
1
vote
0answers
80 views

Minimum cost flow with Demand and Edge Capacity scaling

Consider a the splittable minimum cost flow problem on network $G(V,E,W,C)$ and a set of commodities $(s_i,t_i)$ with demand $d_i$ for $i=1,2,\dots,k$. Here, $w_e$ and $c_e$ is the weight of edge $e$ ...
-1
votes
1answer
265 views

Vertices of a polytope

Consider the polytope $P=\{(x_1,x_2,...,x_n)\in \mathbb{R}^n| \sum_{i=1}^n x_i=1; 0\leq a_i\leq x_i\leq b_i, i=1,...,n\}$ where $a_i$ and $b_i$ are constant lower and upper bounds for $x_i$. Is it ...
7
votes
1answer
277 views

Embedding a graph in the euclidean space

Given a graph $G=(V,E)$, find a mapping $f\colon V \rightarrow \mathbb R^d$ such that for every edge $(u,v) \in E$ we have that $||f(u)-f(v)|| \leq r$; and for every $(u,v) \not \in E$, we have the ...
5
votes
1answer
139 views

Is computing the dual optimum of a degenerate LP equivalent in complexity to solving LP?

Given a primal LP and an optimum solution thereof, it is well-known that complementary slackness conditions [1] can be used in non-degenerate cases to produce a dual optimum solution. For instance, ...
3
votes
0answers
128 views

Exactly solvable but non-trivial integrality gap

Are there interesting polynomial time solvable problems that we know of for which the natural convex relaxation has a non-trivial integrality gap? Note: Maximum matching doesn't qualify because I ...
-1
votes
1answer
225 views

convertion into integer linear program for Ising spin state problem [closed]

I am trying to model the Ising spin state problem into Integer linear program and find the optimal ground state using lp_solve. (This is just a miniature version of Ising state problem) $$ maximise: \...