# 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
60 views

### Maximize the number of edges in subgraph

We are given a graph $G=(V,E)$ and we want an algorithm to find a set of vertices $U$ to maximize the following quantity : $\frac{|E(U)|}{|U|}$ where $E(U)$ denotes the number of edges in the subgraph ...
227 views

### LP formulation and integer solution existance

I’m trying to prove that the following problem has an integer optimal solution. This will hold if the corresponding linear program would have totally unimodular constraint matrix. We have $m$ pieces ...
40 views

### Why is the target function minimized at (0,0) if I can get to a negative number?

I just started learning LP and I saw this Q in my textbook: $$min : -x -y \\ S.T. : x + 2y \le 3, 2x +y \le 3, x \ge 0, y \ge 0$$ It is easy to see that the polygon created from these constraints ...
376 views

### Finding integrality gap for maximum weight independent set

One of the exercises I was given was to formulate Integer Linear Program (ILP) and relaxed version of it (LP) to solve the maximum weight independent set, and I need to find an integrality gap of my ...
61 views

### Objective function and constraint satisfaction over a set of multi-attributes elements

I'm looking for an approach to solve a problem consisting of maximizing an objective function over a set of discrete elements, while respecting a set of constraints. To illustrate my point, I'll try ...
47 views

### Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron?

The feasible region of a Linear Program (LP) is $\{x \in {\bf R}^n: Ax \le b, x\ge 0 \}$. This is an intersection of halfspaces, a polyhedron. If the LP is bounded and feasible, its optimal value will ...
2k views

### Expressing conditional in linear program [duplicate]

I have two variables $A$ and $B$, with $A$ being binary and $B$ is a real number where $B \ge 0$. My conditions are: if B > 0 A = 1 else A = 0 ...
47 views

### How to monitor and alter the value of decision variables using if then else

Assuming I have two 0-1 decision variables X[a,b] and Y[i,j,e,d] where : X[a,b] = 1 if a is in b 0 otherwise Y[i,j,e,d] = 1 if (i,j) is matched with (e,d) 0 otherwise. I need to ensure that if ...
461 views

### Max flow with priorities

I'm studying a simple max flow problem: Each type of object $a_1, a_2...$ can be stored in some of several stores $b_1,b_2...$. This is described by this graph: There are $|a_i|$ objects of the type ...
538 views

458 views

### When does strong duality fail in linear programming?

When does strong duality fail in linear programming? I have considered the case when both primal and dual solutions are infeasible, but then there are no optimal solutions at all.
134 views

### Expressing the condition as a set of linear constraints

Express the condition "$x = 0$ if and only if $y = 0$" as a set of linear constraints, where $x,y$ are integers such that $- 5 \le x \le 8$ and $0 \le y \le 1$
285 views

### Casting to boolean in integer linear programming

I have variables $x \in \{0,1,\dots,5\}$ and $y \in \{0,1\}$, where $$y = \begin{cases} 0 & \text{if } x = 5\\ 1 & \text{if } x \neq 5\end{cases}$$ My problem is to maximize $y$. How can I ...
186 views

### Set Cover and additional constraints

Consider the following bipartite graph: Each node in red color represents a warehouse $w = \{ 1,2,3\}$. For this example we have three warehouses located at different locations. Each warehouse has a ...
58 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 ...
47 views

### Computing line equations of two crossing tangents [duplicate]

Pictured is the problem in question. How do I compute the line equations for these two crossing tangents? These lines happen to be supporting two point sets for two convex hulls.
101 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 ...
79 views

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. ...
1k views

### Express a “complex” IF-Statement to Linear Programming

In our current project we need to model the following if-statement in linear programming: If T1 < b < T2 then z = s else z = 0 where T1 and T2 are two ...
736 views

### Linear programming formulation for the single-source shortest path problem

In this course lecture; section 5.1, single-source shortest path (SSSP) is formulated as the following linear program (LP): \begin{align} \max &\sum d_u \\ \text{subject to} & \\ d_v &\le ...
For my application problem, I am looking for an easy to implement or source code for approximation algorithm for maximum k-Set Packing problem. Given a universe $U$ and a family $\mathcal{S}$ of ...