Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
380
questions
0
votes
0
answers
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 ...
0
votes
0
answers
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 ...
0
votes
0
answers
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
1
vote
0
answers
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 ...
- 2,220
2
votes
1
answer
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 ...
- 21
1
vote
2
answers
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.
...
- 113
1
vote
1
answer
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 ...
- 13
2
votes
1
answer
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 ...
- 123
1
vote
0
answers
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 ...
- 369
1
vote
0
answers
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 ...
- 111
3
votes
0
answers
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 ...
- 131
0
votes
1
answer
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 ...
D.W.♦
- 141k
1
vote
1
answer
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 ...
- 141
0
votes
0
answers
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 ...
- 141
1
vote
1
answer
23
views
Linear encoding of a feed forward neural network
I was reading [1] 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,...
- 13
0
votes
1
answer
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 ...
- 13
1
vote
1
answer
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 ...
- 11
0
votes
0
answers
39
views
ILP - Maximize the number of pairs of variables with the same value
I have a 0-1 integer linear program for a set of $2n$ variables $S = \{x_1, ..., x_n, y_1, ..., y_n\}$. My objective is to maximize the number of pairs $(x_i, y_i)$ such that $x_i = y_i$, $i = 1, ..., ...
- 143
0
votes
0
answers
22
views
minimizing std. dev. in linear programming
I'm new to Linear Programming and trying to create an automated scheduling algorithm, and am having trouble defining the objective function and decision variables. Any help would be appreciated:
Let ...
- 11
1
vote
0
answers
81
views
Shortest path as a linear program
I just encountered this formulation of the shortest $s$-$t$ path problem as a linear program in a homework. I don't understand exactly the meaning of the variables and restrictions. Here, $G = (V, E)$ ...
- 81
1
vote
1
answer
25
views
Linear programming for prefix of graph
Question: Consider an arbitrary directed graph $G$ with weighted vertices, the weights can be positive, negative or $0$. The prefix of $G$ is a subset of vertices $P$ such that there's no edge $(u \...
- 361
0
votes
1
answer
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 ...
- 5
1
vote
0
answers
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 ...
- 11
10
votes
0
answers
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 ...
- 5,704
1
vote
0
answers
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, ...
- 81
1
vote
1
answer
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 ...
- 115
0
votes
1
answer
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 ...
- 109
0
votes
0
answers
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 ...
0
votes
1
answer
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 ...
- 1
0
votes
0
answers
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 ...
user144038
3
votes
1
answer
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 ...
- 129
1
vote
1
answer
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
1
vote
1
answer
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 ...
- 1
0
votes
0
answers
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
0
answers
169
views
Fixed Parameter Tractable for Special Vertex Cover using ILP
The problem I'm trying to solve reads as follows:
Given a graph $G=(V,E)$ ,a parameter $k$ and two values $U^\star, P^\star \in \mathbb N$, where every vertex $v\in V$ has a utility and a pollution $...
- 317
0
votes
0
answers
30
views
Maximizing an integer Linear problem
i am taking a basic Linear programming class this semester and we've recently started solving integer linear problems. I have a question regarding how to solve one of these exercises.
$$
z = max\: 5x_{...
- 1
0
votes
1
answer
20
views
Linear programing modeling
I am trying to prepare for my Linear programing exam and i stumbled upon an exercice that i can't wrap my head around. It goes like this.
Seven days before the final match a tennis player is trying to ...
- 3
1
vote
1
answer
44
views
Find optimal play by optimizing orders of each player alternatingly
A zero-sum game for two players allows a player to take no action during a turn. Can I reach optimal play (where both players always choose the best possible action in each turn) by the following ...
- 113
0
votes
1
answer
74
views
Non-convex linear program optimisation with infinite number of OR constraints
I am aware that when we have a linear problem subject to OR constraints, the LP would be a non-convex optimisation problem. For example,
${x = 0}$ OR ${1<=x<=2}$.
My question is in such a ...
- 135
0
votes
2
answers
106
views
Solving linear programming problem with mixed type of constraints
I have a query in solving the problem below:
An automobile company has two factories. One factory has 400 cars (of a certain model)
in stock and the other factory has 300 cars (of the model) in stock. ...
- 9
1
vote
1
answer
91
views
Linear programming infeasible problems
A part of ORCA local avoidance collision is calculating a linear program with an incremental approach - adding the constraints one by one. If the problem is determined to be infeasible, the ...
- 111
2
votes
1
answer
123
views
1/2 Approximation to MAX-DICUT by rounding a linear program
Consider a graph $G=(V, A, w)$, where each arc $(u,v)\in A$ has a non negative weight $w_{u,v} \in \mathbb{R}^+$, partition $V$ into $U$ and $W$, $W=V-U$ such that $\sum_{(i,j)\in A} w_{i,j}z_{i,j}$ ...
0
votes
1
answer
48
views
Finding lowest point in circles
Given n disks in the plane, i want to compute the lowest point in their intersection area, im looking for a simple randomized incremental algorithm.
There are some circles in the plane, these circles ...
- 358
1
vote
2
answers
119
views
Linear program for min-length pair of edge-disjoint paths problem
Consider a problem: we have an undirected graph $G = (V, E)$, function $l: E \to \mathbb{Z}_{+}$ where $l(e)$ is edge's length $e \in E$, and two vertices $s$ and $t$. And we want to find a pair $(A, ...
- 158
1
vote
1
answer
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 ...
- 11
2
votes
1
answer
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
...
- 587
1
vote
1
answer
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 ...
- 659
0
votes
0
answers
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 ...
- 11
5
votes
0
answers
67
views
2-Dimensional interval scheduling problem
I have a problem that is similar to the conventional interval scheduling algorithm but it is two dimensional, so I have another metric to take into account. My dataset format:
Cars with the start and ...
- 51
0
votes
1
answer
24
views
How/why is switch made from equation to inequality for certificate of optimality for dual problem in linear programming?
I am reading Chapter 7 Linear Programming in Algorithms by Dasgupta et al.
I don't get how they switch from an equation to an inequality specifically the part highlighted in red/pink regarding the ...
- 659