# Questions tagged [linear-programming]

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

380 questions
Filter by
Sorted by
Tagged with
9 views

### What does the complementary slackness theorem say intuitively/in layman's terms?

In layman's terms: weak duality theorem states that all feasible solutions to the primal LP is less than or equal to all feasible solutions to the dual LP. strong duality theorem states that the ...
27 views

### Identifying the parameters and finding an optimal solution to a problem

I work in the Computer Graphics field, and I have a problem where I need to find the optimal solution for, but I'm not sure how to best formulate the problem mathematically, how to define the ...
10 views

### Cutting stock problem upper bound with gilmore and gomory

I am trying to implement this article https://arxiv.org/pdf/1905.04897.pdf (the article is there only for information, no need to read it to answer my question) At some point they say when talking ...
1 vote
29 views

### Papadimitriou's pseudopolynomial algorithm for m x n integer program with fixed m

Consider the following proof from Papadimitriou's "On the Complexity of Integer Programming": Corollary 1. There is a pseudopolynomial algorithm for solving m x n integer programs, with ...
26 views

### Integer linear programming formulation of boolean selection

Given a boolean variable $x$ and nonnegative integer variable $s$, I want to select $y = \begin{cases} 0 & \text{if} \ x = 0 \\ s & \text{if} \ x = 1 \end{cases}$. Currently in the ...
1 vote
471 views

### Prove that a quadratically-constrained linear program (QCLP) is NP-Complete

Show that if we strengthen linear programming by also allowing constraints of the form $$\sum_{i,j = 1}^n a_{ij} x_i x_j = b,$$ for integers $b$ and $a_{ij}$, then the problem becomes NP-complete. ...
1 vote
18 views

### Why do we round from 1/2 when converting the LP to ILP for the weighted vertex cover problem?

I understand that to approximate a solution to the weighted vertex cover, we need to relax the integer linear program to a linear program which can be solved in polynomial time, but why do we round ...
26 views

### How can I best represent my 2D thrust problem as a linear programming problem?

While my question stems from game dev, the problem itself isn't as much about the game, but more about correctly representing my problem as a linear programming problem that I can solve with a linear ...
1 vote
25 views

### Dual Linear Program of the Densest-Subset Problem

In the densest-subset problem, given an undirected graph $G = (V, E)$, the goal is to maximise the “edge-density” ratio $|E(S)|/|S|$ over all non-empty sets $S ⊆ V$ , where $E(S)$ denotes the set of ...
1 vote
11 views

### What are the locally optimal points in an LP formulation of the max flow problem?

I'm taking a grad level algorithms course and we just ended the course talking about linear programming, and we had previously talked about the max flow/min cut problem. Our professor said that the ...
23 views

### Advantages of Integral over Non-integral Linear Program?

I have a linear program over real variables for which it can be shown that all the vertices of the polytope describing its feasible region are integral. Obviously I can just solve this using a ...
25 views

### MAX-LP: maximize number of linear inequalities satisfied

Consider the following variant of linear programming, where we want to maximize the number of linear inequalities that are satisfied: Input: linear inequalities $A_1x\le b_1$, ..., $A_nx \le b_n$; an ...
1 vote
27 views

### Proof that using residual network from Ford-Fulkerson will get you min-cut

So I'm following this article and they use the following algorithm to find the min-cut. Algorithm: Run Ford-Fulkerson algorithm and consider the final residual graph. Find the set of vertices that ...
16 views

### Convert Linear Program to Network Flow

Given the following network flow problem: $$max \sum_{p \in P}x_p$$ $$s.t. \sum_{x_p \in c_e} x_p \leq c_e, \forall e\in E$$ $$x_p \geq0$$ $P$: All paths from a start node $s$ to end node $t$ $E$: Set ...
1 vote
23 views

### Linear encoding of a feed forward neural network

I was reading  about reachability analysis of a feed forward neural network (FFNN). The paper encodes a FFNN as a linear programming problem. Suppose $x^{(i)}$ is the vector output of the ith layer,...
86 views

### If greater than or equal to zero then binary variable equals 1: integer linear program

I have a variable $d_{i} \in \mathbb{Z}$ with an upper and lower bound. I also have a binary variable $v_{i}$ which I want to $=1$ if $d_{i} \geq 0$; else $v_{i} = 0$. How do I enforce this as a ...
1 vote
20 views

### Can't figure out decision variable

Good Evening, I am trying to solve an exercise related to my algorithm designing course. I have understood the question and what it asks. I am required to formulate an ILP and then relax it to ...
39 views

235 views

### How are vertex capacities defined in a flow network?

I'm new to network flows and I'm reading this topic from Cormen's Algorithms book (3rd edition) from 26 chapter. I came across this problem from the 26.1 section Suppose that, in addition to edge ...
1 vote
51 views

### Linear Program, minimize maximum distance

Given: Set $N = \{0, \ldots, n-1\}, k \in \mathbb{N}, d_{ij} \geq 0$ with $d_{ii} = 0$. Task: Find subset $C \subseteq N, |C| \leq k$ that minimizes $\max_{i \in N} \min_{j \in C} d_{ij}$. Idea: I ...
67 views

### Maximum matching with social distancing

Let $G = (X\cup Y, E)$ be a bipartite graph. Suppose $X$ contains people, $Y$ contains seats in a theatre, and each edge $(x,y)$ has a weight representing how much person $x$ is willing to pay for ...
1 vote
32 views

### Linear programming and network flow

I would like some hint in this homework question. I have to write the max-flow problem (with souce $s$ and sink $t$) as a linear program. I have to do this by defining variables on each $s - t$ path, ...
1 vote
112 views

### How to get the highest score in this game?

I would like some advice in this homework question. There is a three players game, in which each player ($A, B$, and $C$) is given a $n$-length array of integer values. There are $n$ rounds in this ...
253 views

### LP formulation for minimum edge covering

Given a simple graph $G(V,E)$, what is the LP formulation for the minimum edge covering? Minimum weight edge covering would also work here. If there are none, then that is an answer too. I took a ...
33 views

### how do i formulate this assignment optimisation problem?

Individual i, associated with organization k, are to be deployed at facility j. Each individual has a cost cij of being deployed at j, and each facility has a minimum number of men required bj. In ...
28 views

### Encoding a binary sequence with shift in MILP

I would like to know if it's actually possible to encode a (binary) sequence with rotations in MILP/MIP. Given a binary sequence $(0,1,1,0,0,0,0,1)$ and variables $x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7$ I ...
25 views

### Finding all k-partitions with additional constraints

The partition problem is a very well known one. To partition an integer array into k equal sum partitions. My problem is I want to partition them in such a way that the sum of their partitions equals ... 121 views

### Learn a system of linear inequalities given solutions

Instead of finding a solution to a system of linear inequalities (Ax + b >= 0), I want to find any system of linear inequalities that satisfy a set of feasible ...
1 vote
130 views

### Is there an algorithm to solve the following point clustering problem?

According to this post Given $n$ points $P=\{p_1,p_2,\dots,p_n\}$ in 2D space, and a matrix $D^{n\times n}$ with the distances between each pair of points, we want to partition the points into two ...
1 vote
84 views

### Formulate a 2-clustering problem in LP

The problem: Suppose there are $n$ points in plane, and we want to partition points into two clusters such that sum of diameter of clusters is minimized. The diameter of cluster is maximum distance ...
43 views

### Recommendations on where to learn and practice linear programming?

[CLOSED] Thanks! I am studying Linear Programming in college but I am facing some difficulties to assimilate some concepts. So do you have any recommendations of materials to learn or practice Linear ...
1 vote
169 views

1 vote
61 views

### k-polynomial time approximation algorithm for set cover (k = max size of subsets)

Problem Definition: Given a universe set $U = \{1, 2, \dots, n\}$ and a collection of $m$ subsets $S_1, S_2, \dots S_m \subseteq U$, find the minimum collection of subsets that cover $U$. I am ...
48 views

### Lower bound on positive coefficients of the optimum of 0,1-linear programming problem

I have an instance linear programming such that the coefficients and the constant terms are 0 or 1. Formally, the set of variables is denoted as $V$ and $|V| = n$. There are $m$ constraints, formed as ...
1 vote
688 views

### What happens when we increase or decrease capacities in the minimum flow?

I am confused from these 2 true-false questions on the max flow and am seeking clarity on the basics. If in a network we increase the capacity of an edge in the minimum cut, the maximum flow gets ...
81 views

### How to determine the number of active linearly independent constraints in a basic feasible solution for linear programming?

I am trying to determine if a given solution is a basic feasible solution. I am working with an $n-$dimension polyhedron $P$ defined by a set of $M$ inequalities $Ax \leq B$. I am running into an ...