Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
334
questions
2
votes
1answer
93 views
Efficient algorithm to compute the diameter of a convex set?
Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set?
It is possible to do it efficiently for a set of points, but imagine that the ...
2
votes
1answer
31 views
When LP solution is ILP solution?
For many discrete problems, it's natural to consider their continuous relaxations. A common case is when instead of $x_i \in \{0, 1\}$ we allow $x_i \in [0, 1]$. In certain cases, the original problem ...
2
votes
1answer
32 views
Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program
I am trying to solve an LP in which one of the constraints is mentioned below,
$$\max(x_1,x_2) \ge q,$$
where $x_1 \ge 0$ and $x_2 \ge 0$.
Is it possible to do in linear programming?
1
vote
0answers
46 views
Best algorithm/model to establish relevance between events utilizing mixed data type (Tags, Time, x_coordinate, y_coordinate)? [closed]
I'm building a relevance ranking system for incidents occurrence and prevention. My goal is to use four attributes to establish relevance: tag (About 500 tags), x_coordinate, y_coordinate and time. ...
1
vote
1answer
24 views
Finding optimal separating value
Problem description
We are given two sorted arrays of even numbers: A and B.
Values of A are generally supposed to be smaller than values of B. So we are asked to find a value X where X is an odd ...
0
votes
0answers
16 views
estimating optimal solution for LP with strict inequalities
I have an LP problem with strict inequalities that cannot be relaxed. I understand that most LP solvers require the problem to not have any strict inequalities as it is impossible to find an optimum ...
0
votes
1answer
31 views
Combinatorial optimization algorithm with constraints and objective function
I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function.
.e.g
Say each ...
0
votes
0answers
19 views
What is the significance of Bellman-Ford and linear programming for scheduling and makespans?
CLRS exercise 24.4-9 says the following:
Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \leq b$ of difference constraints, minimizes the quantity $\max_i\{x_i\...
2
votes
1answer
20 views
Linear separability
I have an assignment in linear programming and this question was asked:
given an input of two data sets $P_1,P_2$ containing points $(x,y)$, create a linear program that finds an equation of a line ...
0
votes
0answers
28 views
How to find the optimal assignment using the Kuhn-Munkres algorithm?
I managed to get through the Wikipedia article until the last step and I have implemented an algorithm that can reach the optimum.
Unfortunately the article does not say anything about how can I make ...
0
votes
2answers
52 views
Infeasible linear programming reduce errors to find solution
Most normal linear programming problems look like this:
We choose some point in the double shaded area that solves our optimizer and we're good to go.
However, I've come across a problem where it's ...
1
vote
1answer
18 views
Approximate LP for vertex cover problem
I am studying the topic of vertex cover on coursera and how it can be solved approximately by linear programming. Suppose the optimal solution for the vertex cover problem is $OPT$. I do not ...
0
votes
0answers
26 views
IF THEN condition in Linear Program
I have the following condition in an LP problem. I have a variable $x_i \in i = 1,2,..7$ and I need to constrain the problem via:
if $x_1$ >5 then $x_2 \leq 30$
I'm stumped on how to formulate that ...
2
votes
1answer
28 views
What is the best algorithm to find the optimal path in reducing company's real-estate footprint?
I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it.
Here is the problem: A company is in ...
1
vote
0answers
28 views
IP Programming - objective function ist not a function BUT a table
Here is a short description of my problem:
Part of my objective function is not a regular function. Instead it's a table.
You can see a short extract here:
So if the height is smaller or equal to 300 ...
0
votes
1answer
41 views
Integer programming with indicators
I have the following question, and I need to write it as an integer programming problem:
A manager of a company wants to by presents to his 100 employers. He can buy the presents from two different ...
1
vote
1answer
21 views
linear time nash equilibirum aproximations for two player zero sum games
I'm working on an AI for a game where I'd like the game where each player has hundreds of moves to select from and so the game matrix has 10s of thousands of entries. The game is however zero sum. ...
0
votes
0answers
27 views
Formulating if-then constraints in linear binary programming
From a stock of various computer accessories of different brands, the optimization problem requires deciding to keep or discard products. The decision should be made maintaining the following if-then ...
-1
votes
3answers
44 views
Which topics of mathematics should I need to learn to be a good app developer?
I'm 29 years old. I couldn't continue my studies after grade 10 due to some financial issues and I didn't have time to practice mathematics. It's been more than 11 years since I left studies. Now I ...
2
votes
0answers
194 views
Strong polynomial time algorithm for deciding LP feasibility
Let
$$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
1
vote
2answers
31 views
Linear programming vs integer linear programming
Given $A,b$, let $Ax \le b$ be an instance of linear programming on the variables $x=(x_1,\dots,x_n)$. Assume that the constraints $0 \le x_i$ and $x_i \le 1$ are included in $A,b$.
Suppose that ...
0
votes
0answers
12 views
Integer Linear (ILP / MILP) Formulation for Collision Avoidance of Convex Polytopes / Polyhedra
I am looking for a possibility to avoid the collision of two convex polytopes using (mixed integer) linear programming. I know how I can detect a collision (Akgunduz, A., Banerjee, P., and Mehrotra, S....
2
votes
0answers
42 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
49 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
33 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
60 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
47 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
93 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
66 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
56 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
116 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
203 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$ ...
4
votes
1answer
276 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
27 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
31 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
50 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
55 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
45 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
34 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
18 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}}{...
2
votes
1answer
37 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
84 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
50 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
43 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
168 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
45 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
50 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
41 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 ...
