Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
318
questions
1
vote
0answers
13 views
Randomized Assignment Problem
Given $x_1,...,x_n,y_1,...,y_n\in \mathbb{R}^d$ find a permutation matrix $P\in\mathbb{S}_d$ that minimizes $\sum_{ij}P_{ij}|x_i-y_j|$.
This is an assignment problem and can be solved in $O(n^3+n^2d)$ ...
3
votes
0answers
33 views
Algorithm to cut a sphere in half with a plane and maximize the number of points on the sphere surface on one side of the plane
Consider a sphere with a coordinate system like the earth. There are $N$ points on its surface at random positions. For all the infinite planes that cuts the sphere exactly in half (i.e. the sphere's ...
2
votes
1answer
31 views
In what cases is solving Binary Linear Program easy (i.e. **P** complexity)? I'm looking at scheduling problems in particular
In what cases is solving Binary Linear Program easy (i.e. P complexity)?
The reason I'm asking is to understand if I can reformulate a scheduling problem I'm currently working on in such a way to ...
0
votes
0answers
58 views
Is it possible to form this as a linear program?
My problem is as follows: I have some number $n\in \mathbb{N}$ of items all of size $s\in \mathbb{N}$ that need to be fit into a distributed storage of sizes $[b_1, b_2, ..., b_m], \forall i, b_i \in \...
4
votes
0answers
44 views
Repeated linear programming with similar (not identical) problems
I have multiple linear programming problems of the form:
$$
Minimize\{c^{T}\cdot x\} s.t. Ax = b, x \ge 0
$$
Where $c$ and $A$ are fixed for all the problems. Is there any way to utilize that for a ...
1
vote
0answers
68 views
Minimum vertex cover and odd cycles [closed]
Suppose we have a graph $G$. Consider the minimum vertex cover problem of $G$ formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $...
1
vote
1answer
38 views
How to prove that the dual linear program of the max-flow linear program indeed is a min-cut linear program?
So the wikipedia page gives the following linear programs for max-flow, and the dual program :
While it is quite straight forward to see that the max-flow linear program indeed computes a maximum ...
0
votes
1answer
54 views
Question about the CLRS Linear Programming chapter
I'm currently reading the CLRS Linear Programming chapter and there is something i don't understand.
The goal is to prove that given a basic set of variables, the associated slack form is unique
They ...
2
votes
1answer
100 views
Minimum vertex cover algorithm with linear programming
Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem LP where there is a variable $x_i$ for each vertex $v_i$ of $G$, each variable can take value ...
6
votes
2answers
183 views
Odd cycle transversal and linear programming
Suppose we have a graph $G$ with $n$ vertices. Suppose LP is a linear programming problem where there is a variable for each vertex of $G$, each variable can take value $ā„0$, for each odd cycle of $G$ ...
5
votes
1answer
111 views
How to calculate the dimension of a convex polyhedron?
A convex polyhedron can be represented by a set of linear inequalities. If the inequalities involve $n$ variables, then the polyhedron can be $n$-dimensional, but it can also be of a smaller dimension ...
1
vote
0answers
26 views
Seeking guidance on what to read for Feasibility Binary IP with ''almost total unimodular'' (-1, 0, 1)-Coefficient Matrix and No Obj Function
I am working on an algorithm in graph theory which I wish to prove it's polynomiality/NP-hardness. I am investigating a binary variable (0, 1) integer program which has the coefficient matrix ...
2
votes
0answers
30 views
Ensuring integral result from integral linear program [closed]
An integral linear program is one that has a maximizer that is integral. Sometimes it's possible to prove that a particular LP has this property, for example by proving that it's constraint matrix is ...
0
votes
1answer
44 views
In a LP problem Ax = b, how to solve for A instead of x?
I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A.
Constraints ...
1
vote
1answer
45 views
Converting If-else integer equation to Linear Programming
I have an if-then-else condition with three binary variables A, B and C:
if A + B = 1 then C = 0
How do I express this as an integer linear program with equality ...
0
votes
0answers
30 views
more than one min cut in a net flow
I know the answer to the question, but I still can't understand.
I have the max flow and I need to determine whether there is more than one min-cut.
I know that I need to run BFS from s in the ...
0
votes
0answers
31 views
Looking for fast LP solver algorithm for my Special case
I am interested to know what is the fastest algorithm (complexity wise) known to us to solve the following linear program. Due to its simplicity, I hope for a very fast algorithm. Your help is greatly ...
2
votes
0answers
17 views
Integrality gap in Online Problems and adaptation to competitive ratio
As we all know, in offline problems it is common practice to calculate the integrality gap to get some bound on the approximation ratio of the integral solution.
Now this gap ($IG:=\frac{OPT_{frac}}{...
1
vote
0answers
29 views
Gaussian Elimination, find all rows equal to zero
I have a system of integer linear equalities modulo P a large prime.
Using GE, I place the matrix in row echelon form to check if there are solutions.
After that, I want to check if there is any ...
2
votes
1answer
36 views
Constrain traveling salesman: visit a given city within a given distance from start
I would like to add an additional constraint to the traveling salesman problem: that a given city is visited within a given distance (say 100) from start. Is there ...
2
votes
2answers
56 views
Is there a dynamic programming solution to the student allocation problem?
The student project allocation problem I am trying to solve goes as follows.
There is a set $S$ of students and $P$ of projects such that $|S| \leq |P|$.
Each student makes a top $3$ of their ...
1
vote
3answers
48 views
Linear Programming Problem - what is feasible size for solution on a PC
I need to get feeling for the feasible size of a LPP, that can be solved on a PC.
Say, its a good one (8 cores @ 3+GHz, 64GB RAM).
We also assume that number of variables is close to the number of ...
1
vote
1answer
35 views
Gaussian Elimination: Check an assignment
This question is similar to Check if a row is in the span of a matrix
Suppose I have a matrix $M$ over $GF(2)$ with rows that represent a system of linear equations:
A xor B xor C = 1
A xor B xor ...
1
vote
1answer
40 views
Check if a row is in the span of a matrix
Suppose I have a matrix $M$ over $GF(2)$ with rows that represent a system of linear equations:
A xor B xor C = 1
A xor B xor D = 1
X xor A xor Z = 0
etc...
For a new external row, I want the ...
1
vote
1answer
33 views
Finding all rows of 2 variables using Gaussian Elimination
Suppose I have a system of linear equations. Using Gaussian elimination, I can determine whether a solution exists, and even find a valid solution.
During the elimination, I can combine rows together,...
3
votes
2answers
120 views
Complexity of linear programming
I have a basic question, if I can model a problem $(P)$ by a linear program, can we say that $(P)$ is polynomial?
Linear programs can be solved using simplex, and it was proved that simplex run in ...
0
votes
1answer
41 views
How to write an OR constraint in MILP?
I want to write a constraint with ORs in a MILP. In particular, the following:
$$x \ge c \lor x \le -c \lor x=0,$$
where $c$ is just a real number.
Can anyone give me some hints?
2
votes
1answer
46 views
Labeled points in $\{0,1\}^n$ such that every linear separator requires exponential weights
I want to find labeled samples in $\{0,1\}^n$ such that the Perceptron algorithm takes $2^{\Omega(n)}$ steps to converge. One way to do this would be to find a sequence of labeled examples that are ...
0
votes
0answers
23 views
Stable matching with dynamic preference lists
I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same ...
0
votes
1answer
33 views
Why is a Knapsack problem not an LP problem?
We know that LP can solve optimization problems that have linear constraints and linear objective functions.
A knapsack problem can be formulated into a linear objective function (because it is just ...
0
votes
0answers
46 views
Special case of stable marriage
I have an instance of the stable marriage problem in which the first side $S_1$ has $n_1$ agents and the second side $S_2$ has $n_2$ agents with $n_2$ is very big in comparison to $n_1$. In addition, ...
2
votes
0answers
37 views
Half-integral linear programs
What are some of the known properties of half-integral linear programs?
That is, linear programs for which the solution vector always takes its values in the set $\{0, \frac{1}{2}, 1\}^n$.
I'm asking ...
0
votes
0answers
16 views
Why are basic feasible solutions the same as vertices geometrically?
The first line on the Wikipedia page for basic feasible solutions reads, ...
2
votes
1answer
398 views
Some Questions related to Linear programming
I have some question related to the Linear Programming problem:
If we have an objective function that needs to be maximized and let the feasible region be unbounded such that there is no finite ...
2
votes
1answer
55 views
Linear programming over a finite field
I have a system of equations $Ax = b$ over some finite field $\mathbb{Z}_p$ and want to find a feasible solution. I'm sure this problem is NP-hard, but I'm struggling to find any literature on the ...
1
vote
1answer
69 views
Can the KenKen puzzle be solved using the same ideas as for Sudoku?
There are many ways of solving Sudoku puzzles, however two good approaches are the Algorithm X and solving using Linear programming. Is it possible to solve the KenKen puzzle using Algorithm X (...
0
votes
1answer
31 views
Standard ILP Formulation of Travelling salesman problem: Purpose of subtour elimination constraints?
Consider the Traveling Salesman Problem:
Input: $n$ cities, distances $c_{ij}$ for each ordered pair $(i,j)$ of them.
Output: Find a shortest round tour visiting every city exactly once.
I came ...
2
votes
0answers
95 views
PTAS for Multiple Knapsack with Uniform Capacities, fixed number of Knapsacks
Consider the following problem:
We are given a collection of $n$ items $I = \{1,...n\}$, each item has a size $0 < s_i \le 1 $ and a profit $ p_i > 0 $. There are $m$ (a fixed number) of unit-...
0
votes
0answers
33 views
Scheduling jobs on a single machine - minimising the weighted sum of completion times
Consider the following problem:
there are $n$ jobs $\{1,...,n\}$, each has a processing time, $p_i$, a weight $w_i$, and an arriving time $r_i$. The goal is to minimise the weighted sum of completion ...
0
votes
1answer
67 views
Integer Linear programming formulation if then condition
I want to create constraints such that I can implement the following condition:
Let A be an integer variable >= 0 with an upper bound of 12
I want to introduce the following variable B also an ...
6
votes
0answers
104 views
Time complexity of linear programming with small number of variables
I have a linear program with $n$ variables, $m$ constraints and $O(nm)$ bit total length (the constraint matrix contains only zeros and ones). I am interested in finding a polynomial time algorithm ...
0
votes
1answer
21 views
Bin Packing variant
I am currently struggling with a bin packing variant, where we have fuel and compartments of a tank truck. Some industry constraints apply, but the whole picture is that you must fit the total volume ...
2
votes
0answers
29 views
LP - Dual variable is zero implies primal constraint unnecessary?
Say I have a primal program P with n variables and c constraints.
Let's say that I have an optimal solution for the dual program D, in which the y1, the variable related to the first constraint in P, ...
0
votes
2answers
43 views
LP - given m constraints for 2 variables find maximal radius of circle
Given $m$ constraints for 2 variables $x_1,x_2$ :
$d_ix_1 + e_ix_2 \leq b_i$ for $i = 1,...m$
need to create a linear program that finds the maximal radius of a circle such that all the points ...
3
votes
2answers
175 views
Examples of Analysis of Branch and Bound Method
I am solving a graph problem, which can be formulated as an integer programme. Based on computer experiments, it seems that the branch and bound method works well. I would like to analyse the running ...
0
votes
1answer
30 views
Writing a linear program to model balanced bin packing
Say we want to write a (MI)LP to model the following problem:
Find a parking plan for a set of cars $K=\{1, ..., k\}$ with lengths
$\lambda_i$. Parking is organised in lanes $P=\{1, ..., p\}$. ...
3
votes
1answer
83 views
Integrality gap and LP-rounding
I have a doubt about integrality gap.
If I know that there is no integrality gap for a given problem, i.e.:
$$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$
...
3
votes
2answers
56 views
Linear programming: reduce a contstraint that includes minimun
I have an almost linear programme. However one of the constraints has a form $z = min(x,y)$ (all the other things are linear in the model). Is there a way to substitute this with something (or ...
0
votes
0answers
75 views
Computing an optimal integer assignment given an optimal LP-solution
I modeled an ILP where I have a set of outfits and a set of friends with , all these friends should take one outfit with the lowest effort , considering the fact that these outfits differ in size, ...
1
vote
0answers
18 views
Why maximum-matching algorithm falls into the category of fill-reducing algorithms?
My understanding is that "maximum matching" (or "maximum transversal") are algorithms to pre-order matrix to increase the numerical stability. In Timothy Davis' book Direct Methods for Sparse Linear ...
