# Questions tagged [linear-programming]

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

282 questions
Filter by
Sorted by
Tagged with
37k views

### Express boolean logic operations in zero-one integer linear programming (ILP)

I have an integer linear program (ILP) with some variables $x_i$ that are intended to represent boolean values. The $x_i$'s are constrained to be integers and to hold either 0 or 1 ($0 \le x_i \le 1$)...
3k views

### Sorting as a linear program

A surprising number of problems have fairly natural reductions to linear programming (LP). See Chapter 7 of  for examples such as network flows, bipartite matching, zero-sum games, shortest paths, ...
468 views

### Does every NP problem have a poly-sized ILP formulation?

Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem ...
1k views

### Minimize the maximum component of a sum of vectors

I'd like to learn something about this optimization problem: For given non-negative whole numbers $a_{i,j,k}$, find a function $f$ minimizing the expression $$\max_k \sum_i a_{i,f(i),k}$$ An example ...
1k views

### Finding exact corner solutions to linear programming using interior point methods

The simplex algorithm walks greedily on the corners of a polytope to find the optimal solution to the linear programming problem. As a result, the answer is always a corner of the polytope. Interior ...
1k views

### Does linear programming admit a strongly polynomial-time algorithm?

The linear programming problem: find a strongly-polynomial time algorithm which for given matrix A ∈ Rm×n and b ∈ Rm decides whether there exists x ∈ Rn with Ax ≥ b. I know that Steve Smale's lists ...
14k views

### Are all Integer Linear Programming problems NP-Hard?

As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming ...
2k views

I'm trying to understand a formalization of the shortest path algorithm to a linear programming problem: For a graph $G=(E,V)$, we defined $F(v)=\{e \in E \mid t(e)=v \}$ and $B(v)=\{ e \in E \mid h(... 1answer 445 views ### How to find the supremum over all the “good” (interior) polytopes for a given set of 3D points? Let$S \subset \mathbf{R}^3$be a set of points in 3D and let$O=(x_0,y_0,z_0)$be the origin/point of reference. We consider a convex polytope$P$good / interior if:$P$is wholly contained ... 0answers 234 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 ... 0answers 276 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 ... 2answers 369 views ### Why does this not prove$P\neq NP$? Fiorini, Massar, Pokutta, Tiwary and De Wolf (Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Journal of the ACM 62(2):article 17, 2015; PDF, ArXiv) show any linear program that ... 2answers 564 views ### Randomized Rounding of Solutions to Linear Programs Integer linear programming (ILP) is an incredibly powerful tool in combinatorial optimization. If we can formulate some problem as an instance of an ILP then solvers are guaranteed to find the global ... 2answers 282 views ### Find a binary matrix so that no vector from {-1,0,1}^n is in its kernel Given integers$n,m$, I want to find a$m \times n$binary matrix$X$such that there does not exist any non-zero vector$y \in \{-1,0,1\}^n$with$Xy=0$(all operations performed over$\mathbb{Z}$). ... 1answer 210 views ### Use complementary slackness to prove the LP formulation of max-flow only need polynomial number of path constraints This is a homework problem for a class that ended 2 years ago, I'm learning it by myself. Consider a directed graph$D=(V,A)$,$s,t\in V$.$A=\{a_1,\ldots,a_n\}$. Let$P=\{p_1,\ldots,p_m\}$be the ... 3answers 796 views ### Maximum set packing and minimum set cover duality I read that the maximum set packing and the minimum set cover problems are dual of each other when formulated as linear programming problems. By the strong duality theorem, the optimal solution to the ... 0answers 68 views ### Uniform Sampling on Intersection of Faces of Simplices [closed] I'm trying to sample uniformly on the intersections of faces of several simplicies, with all coordinates being non-negative. That is, given constraints $$A\vec{w}=\vec{b} \ \ and \ \ \vec{w} \geq \vec{... 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 ... 2answers 1k views ### Proof of Strong Duality Via Farkas Lemma I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the ... 0answers 39 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 ... 1answer 463 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 ... 1answer 1k views ### Find maximum distance between elements given constraints on some I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements: The element 1 is in position 1, and element N must be ... 1answer 78 views ### Unfeasible linear program becomes feasible if a variable is removed Apologies, not a computer scientist by trade but I'm playing with linear programming these days. Let \{x_i\} be N optimization variables with bounds$$l_i \leq x_i \leq u_i$$I'm interested in ... 1answer 88 views ### Finding a minimal width strip which encloses a set of points in the plane Problem: Consider a set of n points in the plane, how could we find a strip of minimal vertical distance that contains all points? Definitions: A strip is defined by two parallel lines and the ... 2answers 90 views ### Does real linear programming produce bipartite perfect matching using maxflow reduction? Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram: We can formulate max flow as an linear programming problem with integer variables in ... 1answer 124 views ### Mistake in a proof of termination phase of Simplex algorithm in CLRS? There is a pseudo-code for Simplex algorithm in CLRS: The proof consists from three-part loop invariant: Proof We use the following three-part loop invariant: At the start of each iteration ... 1answer 55 views ### Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations? My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a ... 1answer 435 views ### Linear programming restricted to rational coefficients I'm reading the appendix A of Williamson's "the design of approximation algorithms" about linear programming. In the definition of a linear programming it restricted the coefficients of cost function ... 3answers 200 views ### Help wrapping my head around a combinatorial optimization problem Here's the problem I'm trying to solve: I have a bunch of widgets, whose weights vary over a small range. I would like to find the optimal grouping of them such that each group meets a minimum weight ... 1answer 184 views ### Formulating a linear program s.t. only extreme point solutions are found If there are many solutions to a linear program s.t. the objective function is minimized/maximized (= optimal solutions are on an edge of the polytope), how can I force an LP solver to find only an ... 1answer 737 views ### Maximum matching using linear programming In a bipartite graph G = (V,E), there is a neat algorithm for finding a maximum matching (or even a maximum-weight matching) using linear programming. It is explained here. The first step is to ... 3answers 79 views ### Need help optimizing the loading of passengers on small airplanes I work for a small non-profit that provides transportation for people who need medical treatment. We connect volunteer private pilots who fly people in their own (small) aircraft, typically 3-5 seats. ... 3answers 5k views ### “Greater than” condition in integer linear program with a binary variable How can one model the following condition in an integer linear program?$$A = \begin{cases} 1 & \text{if } B > C\\ 0 & \text{otherwise}\end{cases}$$where$A \in \{0,1\}$and$B, C \in \...
Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps. There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ is ...