Questions tagged [linear-programming]

Optimization with a linear objective function, subject to linear equality and linear inequality constraints.

102 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
0answers
256 views

What's the complexity of solving a packing LP?

Linear Programming is in polynomial time weakly (when numbers are encoded in unary). AFAIK it remains open if it is possible to solve LP in polynomial time strongly (when numbers are encoded in ...
7
votes
0answers
169 views

Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function. The answer ...
7
votes
0answers
355 views

How are basic feasible solutions in linear programming related to vertices in its corresponding polytope?

In Section 2.3.3 "Polytopes and LP" of the book "Combinatorial Optimization: Algorithms and Complexity" by Christos H. Papadimitriou, Theorem 2.4 establishes the relation between bfs's (basic feasible ...
6
votes
0answers
108 views

Time complexity of linear programming with small number of variables

I have a linear program with $n$ variables, $m$ constraints and $O(nm)$ bit total length (the constraint matrix contains only zeros and ones). I am interested in finding a polynomial time algorithm ...
6
votes
1answer
544 views

Exponential example for simplex used in SMT solvers

The original simplex algorithm requires an exponential number of pivot operations in the worst case, e.g., if run on the Klee-Minty example [3,4]. What about the simplex algorithm used in SMT solvers ...
5
votes
0answers
43 views

Authors of Complementary Slackness

Who were the first researchers to prove the Complementary Slackness condition for linear programming? I believe that strong optimality was proved by Gale, Kuhn, and Tucker in 1951, but I couldn't ...
5
votes
0answers
40 views

Does it make sense to examine the dual of a feasbility problem?

Consider a standard feasibility problem. The goal is to examine the state of feasible solutions for $Ax=b$ to find an $x$ that satisfies some property. Does the dual of this problem tell us anything ...
4
votes
0answers
47 views

Repeated linear programming with similar (not identical) problems

I have multiple linear programming problems of the form: $$ Minimize\{c^{T}\cdot x\} s.t. Ax = b, x \ge 0 $$ Where $c$ and $A$ are fixed for all the problems. Is there any way to utilize that for a ...
4
votes
0answers
212 views

Intuitive self-contained proof of Farkas' Lemma

I've been studying the proof of Farkas' Lemma, and given my rather fuzzy memory of Linear Algebra, am having some trouble with it. One version of Farkas' lemma states: For any convex cone generated ...
4
votes
0answers
123 views

Showing a linear program is infeasible or finding a feasible solution

I'm aware that for any given maximize/minimize LP problem, if its dual is unbounded then the primary is infeasible and vice versa. But what if there is no maximize/minimize objective function? For ...
4
votes
0answers
251 views

Algorithm to optimize polling frequency between producer and consumer

I am trying to optimize what we call AJAX request polling frequency in the domain of web design. Here's a general version of the problem in simple lingo: Problem Statement: Suppose there are 3 ...
3
votes
0answers
43 views

Algorithm to cut a sphere in half with a plane and maximize the number of points on the sphere surface on one side of the plane

Consider a sphere with a coordinate system like the earth. There are $N$ points on its surface at random positions. For all the infinite planes that cuts the sphere exactly in half (i.e. the sphere's ...
3
votes
0answers
531 views

Minimum clique cover

How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time? Having an undirected graph, I am trying to partition all its ...
3
votes
0answers
165 views

2-approximation edge-cover algorithm using primal-dual method

The problem Given an undirected graph $G=\left(V, E\right)$ and positive edge weights $w_e$, design a 2-approximation algorithm based on the primal-dual principle. So far I managed to represent the ...
3
votes
0answers
68 views

Computing the line equations of two crossing tangents in a point set separated by a vertical line?

I have provided a picture as an example. We have two point sets, P and Q. P is to the left of this vertical line (named x = x0), and Q is to the right of it. The goal is to compute the line equations ...
3
votes
0answers
179 views

Why is my Forrest-Tomlin update worse than recomputing LU?

I wrote a simple C++ implementation of the revised simplex method that recomputes the LU decomposition of the basis from scratch on each iteration. I have to solve problems with many variables but few ...
3
votes
0answers
53 views

Heuristic for making set of indexes in an array/matrix with generating functions/patterns

I am trying to find a lead on how to solve or find a heuristic the following kind of problem: Given an array/matrix with entries of only 1s and 0s, using a set of looping functions/patterns of a ...
3
votes
0answers
30 views

What is the most efficient algorithm for finding the bounding inequalities of a cone given the extremal rays?

Say that I am given a cone, as specified by the extremal rays whose facets form its convex hull, what is the most efficient algorithm that finds the linear-rank inequalities whose intersection defines ...
3
votes
0answers
97 views

Start simplex method from feasible internal point

I have one algorithm that generates a feasible solution to a linear programming problem. However, it is very likely that this is not a corner point. This makes it not suitable for direct use as an ...
2
votes
0answers
183 views

Strong polynomial time algorithm for deciding LP feasibility

Let $$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
2
votes
0answers
42 views

Randomized Assignment Problem

Given $x_1,...,x_n,y_1,...,y_n\in \mathbb{R}^d$ find a permutation matrix $P\in\mathbb{S}_d$ that minimizes $\sum_{ij}P_{ij}|x_i-y_j|$. This is an assignment problem and can be solved in $O(n^3+n^2d)$ ...
2
votes
0answers
18 views

Integrality gap in Online Problems and adaptation to competitive ratio

As we all know, in offline problems it is common practice to calculate the integrality gap to get some bound on the approximation ratio of the integral solution. Now this gap ($IG:=\frac{OPT_{frac}}{...
2
votes
0answers
39 views

Half-integral linear programs

What are some of the known properties of half-integral linear programs? That is, linear programs for which the solution vector always takes its values in the set $\{0, \frac{1}{2}, 1\}^n$. I'm asking ...
2
votes
0answers
98 views

PTAS for Multiple Knapsack with Uniform Capacities, fixed number of Knapsacks

Consider the following problem: We are given a collection of $n$ items $I = \{1,...n\}$, each item has a size $0 < s_i \le 1 $ and a profit $ p_i > 0 $. There are $m$ (a fixed number) of unit-...
2
votes
0answers
32 views

LP - Dual variable is zero implies primal constraint unnecessary?

Say I have a primal program P with n variables and c constraints. Let's say that I have an optimal solution for the dual program D, in which the y1, the variable related to the first constraint in P, ...
2
votes
0answers
76 views

Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
2
votes
0answers
64 views

Relaxations for MILP with logical constraints

I have an LP with a (non-fixed) number of logical constraints in the form of $X_1 \rightarrow X_2$ (where $X_1$ and $X_2$ are linear functions inequalities of the $n$ input variables). To express ...
2
votes
0answers
78 views

Implementing a linear programming feasibility test in 3D

I have a little problem which requires determining if a system of linear inequalities in 3D is infeasible. The constraints (or oriented planes) are added one by one, so there is an opportunity to stop ...
2
votes
0answers
167 views

How to setup a model for a guillotine cutting stock problem?

Backgroud. I'm reading papers about cutting stock problem (CSP). Said Ben Messaoud, Chengbin Chu, Marie-Laure Espinouse (2008) Characterization and modelling of guillotine constraints. European ...
2
votes
0answers
59 views

Adding linear constraint to continuos LP to improve performance

Consider a standard LP minimization problem of the form $$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & A x = b\\ & x \geq 0\end{array}$$ Should I expect, on average,...
2
votes
0answers
118 views

Formalizing an intuitive linear programming proof

My professor has asked me to prove the following: Prove that we can use an algorithm for linear programming to solve linear inequality feasibility problems. The number of variables and ...
2
votes
0answers
47 views

Implications of the class of problems with parallel solutions being not P-complete for optimization of matrices

I am not a specialist on computational complexity theory. I do work on optimization and I am currently researching about the implications of the class of problems with parallel solutions (NC) being ...
2
votes
0answers
128 views

How to construct a network flow problem?

I have the optimization problem given below max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ s.t $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad 2)\quad x_{ij} \in {0,1}$ $\quad ...
2
votes
0answers
377 views

General Steiner Tree Variants

In the general Steiner tree problem (Steiner tree in graphs), we are given an edge-weighted graph G = (V, E, w) and a subset S ⊆ V of required vertices. A Steiner tree is a tree in G that spans all ...
2
votes
0answers
301 views

Assign $m$ tasks to $n$ workers, with $m \geq n$

There are $n$ students that share the same apartment. At each evening, one of them must prepare dinner for everyone. There are $m$ evenings to schedule, with $m \geq n$, and you have to assign any ...
2
votes
0answers
100 views

Facility location on a Sphere with great circle distance

I am looking for an algorithm to find the point that minimizes the sum of the great circle distances to a set of fixed points on a sphere. In more detail: Given $x_1,\ldots, x_k$ fixed points in the ...
2
votes
0answers
152 views

Practical implications of strongly polynomial time algorithm for linear programming

Why do people care about whether a strongly polynomial time algorithm for linear programming exists or not? Does this have any practical improvement?
2
votes
0answers
82 views

Issues with an optimization problem

I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$. I want to find the ...
2
votes
0answers
1k views

Job assignment problem

I want to solve job assignment problem using Hungarian algorithm of Kuhn and Munkres in case when matrix is not square. Namely we have more jobs than workers. In this case adding additional row is ...
2
votes
0answers
163 views

Maximum feasible subsystem problem (MaxFS) in 2 variables

Topic: The maximum feasible subsystem problem, which is generally NP-hard [1]. Question: Are there special algorithms in case of only 2 variables (2D linear constraints)? The problem seems to be a ...
1
vote
0answers
28 views

IP Programming - objective function ist not a function BUT a table

Here is a short description of my problem: Part of my objective function is not a regular function. Instead it's a table. You can see a short extract here: So if the height is smaller or equal to 300 ...
1
vote
0answers
27 views

Seeking guidance on what to read for Feasibility Binary IP with ''almost total unimodular'' (-1, 0, 1)-Coefficient Matrix and No Obj Function

I am working on an algorithm in graph theory which I wish to prove it's polynomiality/NP-hardness. I am investigating a binary variable (0, 1) integer program which has the coefficient matrix ...
1
vote
0answers
19 views

Why maximum-matching algorithm falls into the category of fill-reducing algorithms?

My understanding is that "maximum matching" (or "maximum transversal") are algorithms to pre-order matrix to increase the numerical stability. In Timothy Davis' book Direct Methods for Sparse Linear ...
1
vote
0answers
64 views

Can this graph-ordering problem be solved with LP?

I have a modelling problem that I am trying to solve with LP. (More specifically, in Python using PuLP or Pyomo). I am not terribly knowledgeable in this area and have been struggling to find the ...
1
vote
0answers
38 views

About Steiner tree problem in graphs

In the paper (p. 3) and the slides presents the formulation of the Steiner problem on graphs via so called Steiner cuts. But according to the definition, the number of Steiner cuts and so the ...
1
vote
0answers
20 views

Minimal subset of rows that generate smaller polyhedron

Given a matrix $[A|B]$ I want to find a minimal matrix $[A'|B'] \subseteq [A|B]$ (i.e. the rows in $[A'|B']$ are also in $[A|B]$) such that $A'x < B' \Rightarrow Ax < B$. Geometrically, I want ...
1
vote
0answers
43 views

Solving a linear program with simplex algorithm, matrix not full rank

I need to solve the following LP $$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & A x = b\end{array}$$ where $$A = \begin{bmatrix} 1 & 3 &1&0&0 \\ -2&...
1
vote
0answers
45 views

An LP with two covering constraints - how to round

I came across an LP with two covering problems, and I wonder how to find a good approximation. For the relevant part of the LP: We have a set $E$ , for each $e\in E$ we have a corresponding set $Y_{e}\...
1
vote
0answers
44 views

Time complexity: Using linear programming to solve a system of linear equations

As far as I know, most direct methods for solving linear systems of equations have time copmlexity $O(n^3)$ (where $n$ is the number of variables), with the few methods being faster having huge ...
1
vote
0answers
118 views

Confusion about the geometric interpretation of the simplex method for linear programming

In Section 7.6.2 of the textbook "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the authors provide a geometric interpretation of the two main tasks of each iteration of ...