# Questions tagged [linear-programming]

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

267 questions
Filter by
Sorted by
Tagged with
3k views

### Short and slick proof of the strong duality theorem for linear programming

Consider the linear programs \begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array} \begin{array}{|ccc|} \hline Dual: & \...
18 views

### Why doesn't my code fill in the augmented matrix properly? [on hold]

I'm trying to input data from a training file. It is skipping the first row entirely. ...
40 views

### What is the most efficient way to test whether a set $X \subset \{0, 1\}^n$ and its complement $\{0, 1\}^n \setminus X$ are linearly separable?

I am interested in algorithms that have optimal running time, and ideally which are also very easy to implement. If you can also give some tips on how to implement the algorithm(s) you mention in the ...
16 views

### Creating a waste-optimizing algortihm for cutting a 1d block

I have a one-dimensional block of material. I run an analysis that divides the material into usable and unusable regions. In a manufacturing process, said material is cut and the unusable regions ...
26 views

114 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 ...
24 views

### Linear programing, objective function. variable depending on the sign of another variable

I have the variable Si. How to express a variable Di in LP that satisfies: Di=100*Si if Si>=0 ...
44 views

### If-Then with disjunctions (OR) in Integer Linear Programming (ILP)

I have the following constraints I'm trying to model in Linear Integer Programming. I will try out diverse solvers for this later, but first I need to model the problem. Given the integer variables: ...
74 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 ...
23 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 ...
31 views

### How to model equality in Integer Linear Programming

How to implement v=(a==b) using Linear Programming? $$v= \begin{cases} True, a=b\\ False, a≠b\\ \end{cases}$$ Until now I tried the big M-Method. To show a≤b: $$a-b+Mv≤M$$ $$-a+b-Mv≤-1$$ To show ...
701 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 ...
33 views

47 views

### Partitioning a boolean circuit for automatic parallelization

tl;dr: I have a problem where I have a Boolean circuit and need to implement it with very specific single-thread primitives, such that SIMD computation is significantly cheaper after a threshold. I'm ...
21 views

26 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 ...
192 views

### A simple way to find the feasible region of a system with simple constraints

I'm coding something... weird, and I'm running into some constraint satisfaction and graph theory problems, which are fields I'm not too experienced in. Here's the problem: I start out with this ...
82 views

### Conditional milp formulation

I have two binaries, $\alpha_{ts,it}$ and $\alpha_{ts,gshp} \in \{0,1\}$, and two reals $T_{it}$ and $T_{ts}$ which have upper and lower bounds. How can I model $\alpha_{ts,it}=1$ if the following ...
61 views

### Approximation algorithm for weighted set cover, using multiplicative weights

It is known that the problem of fractional set cover can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows ...
50 views

### Minimal paths as solution of a linear program of a special network flow

Let $G= (V,E)$ be a given directed weighted graph, and $s,t$ two specified nodes, so that there is no negative cycle reachable from $s$, and $t$ is reachable from $s$. We're looking for the shortest ...
43 views

### Where's the flaw in my algorithm? (Linear program to solve NP-hard problem)

The problem (copy-pasted from this question on cs.stackexchange): Given a connected, directed graph $G=(V,E)$, vertices $s,t \in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices ...
27 views

### Sanity check about a linear programming problem

given the linear program: minimize $x+y$ subject to, $ax+by \leq 1$ $x,y \geq 0$ I need to find real numbers $a,b \in \mathbb{R}$ such that the program (a) is infeasible, (b) is unbounded, and (c)...
27 views

59 views

### Boolean variable that captures whether an inequality holds

I have an integer linear program with variables $x_1,\dots,x_n$. I have an inequality $a_1 x_1 + \dots + a_n x_n \ge b$ that I care about; it may or may or not hold. I want to introduce a boolean ...
30 views

### Check a variable within a range with a binary variable [closed]

I have a value, a, it can be any value from 0 to 1. In an integer linear program, how can I formulate a constraint that uses a binary variable, y, to determine whether a is within a range of 0 and 1 ...
50 views

### What is the intuition behind the way of reading off a dual optimal solution from simplex primal tabular in CLRS?

Section 29.4 "Duality" of CLRS (3rd Edition) describes the way of reading off an optimal dual solution from the last slack form of the primal as follows: Suppose that the last slack form of the ...
56 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 ...
34 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 ...
277 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 ...
43 views

### How to efficiently specify a MILP constraint with nested AND and ORs

Let's say I want to set x1=1 if (x2=1 AND x3=1 AND x4=1) or (x5=1 and x6=1) or (x7=1) else x1=0 All of the xs are binary ...
18 views

### When does total unimodularity implies integrality of solutions?

In Gartner & Matousek's book on linear programming, they prove the following lemma (Lemma 8.2.4, page 145): Let us consider a linear program with $n$ nonnegative variables and $m$ inequalities ...
101 views

### Using LP to prove the max matching - min cover theorem

Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following ...
3k views

### Partition of a set of integer into 3 subsets of approximately equal sum

I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes: "A hard working mom bought several fruits with different nutritional values for ...
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$)...
Suppose we have an oracle that solves problems of the form \begin{align*} \text{maximize} ~~ & c^T x \\ \text{subject to} ~~ & A x = b, x\geq 0 \end{align*} when $c\geq 0$ (all coefficients ...