Questions tagged [linear-programming]

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

276 questions
Filter by
Sorted by
Tagged with
19 views

Knapsack Problem Via Column Generation

If I were to solve the linear relaxation of a knapsack problem via column generation how could I model the master problem and pricing subproblem? Given a set $N$ of items with value $v_{i}$ and weight ...
35 views

14 views

Given a primal LP p, and another LP d, how can i formally prove that d is the dual problem of p?

Given a primal LP p, and another LP d, how can i formally prove that d is the dual problem of p? Specifically, i'm talking about the shortest s-t path: where: And the dual LP:
7 views

How to input random values (constraints) of any variables in case of formulating Linear Programming Problem?

Suppose, Min 2x+3y Subject to, x=2,x=5,x=7 y=5, y=9 is a linear program. Where x holds the values 2 or 5 or 7 and y holds the values 5 or 9. Then what should the correct ...
19 views

How is ellipsoid method a polynomial-time algorithm for LP?

I have always thought that the ellipsoid algorithm is an algorithm which can be used to solve LP in polynomial-time. However, what confuses me is the dependence on the ratio of volumes of the balls (...
19 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 ...
28 views

121 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 ...
27 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 ...
118 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 ...
30 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 ...
36 views

54 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: ...
48 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 ...
42 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 ...
22 views

Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?

Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem? I saw this Gurobi post that uses Integer Linear Programming to solve the traveling ...
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 ...
46 views

Logic of multiple variables in ILP

Is there a better way to represent an AND of $n$ variables together other than creating $O(n)$ new variables and constraints?
38 views

Traveling Salesman Problem with profit and time limit as ILP formulation

How to formulate the following problem? The salesman gains a profit $p_{i}$ when visiting a city i, trip between city i and city j costs $c_{ij}$ and takes $t_{ij}$ time. The trip must not exceed a ...
53 views

ILP representation of the number of maximal 1 sequences in a row

I am currently using an ILP to model events which occur on some input sequence from $1...n$. These events modify the input sequence in order to obtain a desired sequence. Each event can happen on some ...
19 views

28 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 ...
47 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 ...
80 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 ...
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)...
51 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 ...
27 views

71 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 ...
59 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 ...
473 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 ...
45 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 ...
19 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 ...
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 ...