All Questions
Tagged with linear-programming algorithm
195 questions
2
votes
1
answer
137
views
Bottleneck transportation problem in a grid with pairing of two adjacent cells
While working on a personal project I stumbled into a problem that can be formulated as follows:
You have a grid with N rows and M columns. The table contains some red and some green cells. The goal ...
0
votes
0
answers
68
views
Randomized Relaxation of Complex Linear Assignment Problem
I am currently working on creating an algorithm to solve a complex assignment problem. The problem is basically as follows: there are d "sessions" each with m "sections" each with ...
- 15
0
votes
3
answers
115
views
Solving for the closest point within designated area
Trying to wrap my head around a problem I am trying to solve. I can't imagine I'm the first one that has solved something like this. I'm fairly certain its a linear programming problem. I'm working in ...
- 29
0
votes
0
answers
53
views
How can i turn a set of points and a seperating line into a linear program solvable in python? (Marriage before conquest algorithm)
I'm currently working on a project where i'm implementing the marriage before conquest algorithm for finding the convex hull of a set of points.
One step involves separating my set of points by a line,...
- 21
2
votes
1
answer
3k
views
Faster alternatives to the Hungarian Algorithm?
I've successfully implemented Munkres' variation of the assignment algorithm in C#, the Hungarian Algorithm, as seen here https://users.cs.duke.edu/~brd/Teaching/Bio/asmb/current/Handouts/munkres.html
...
- 35
1
vote
0
answers
107
views
Algorithm to Solve Constrained Longest Path Problem
I am a matrix that represents the shortest path between any two nodes, which I compute from a weighted adjacency matrix using Floyd Warshall algorithm. Additionally, I have a constant maximum weight. ...
- 11
0
votes
1
answer
204
views
What's the optimal solution for 1D optimal transport
Assume I want to move n goods to n warehouses. I have a n x n cost matrix M, where Mij denotes the cost of transporting jth good to the warehouse. How do I find the transporting plan that minimizes ...
- 183
1
vote
3
answers
923
views
Find min max range of multiple variables the results in maximum PnL
Given a table of N columns, all columns except last are variables and the last column is PnL (Profit and Loss). Each variable value is a whole number (no fractions, decimals) greater than or equals 0 ...
- 31
3
votes
2
answers
290
views
An Algorithm for solving linear inequalities with two variables
I am trying to find an algorithm to determine existence of strictly positive integral solutions for a set of linear inequalities with two variables and the following form:
𝑎1𝑥 + 𝑏1𝑦 ≤ 𝑙1
𝑎2𝑥 + ...
3
votes
1
answer
102
views
Filling two fractional knapsacks using the same items
I have two knapsacks, let's call them knapsack A, and knapsack B, each knapsack has a max weight limit. We also have some item types that we can take with us. Each item type has a price, and two ...
- 33
0
votes
0
answers
31
views
MILP - How to set variable to be absolute value of other variable [duplicate]
In a Milp, given an integer variable x, I would like to define a variable y which will be the absolute value of x.
y = |x|
x is bounded between [M, -M].
Is it even possible?
Thank you!
- 93
0
votes
0
answers
31
views
MILP - Adding a constraint renders solution feasible?
I am using CBC solver in Pulp.
I have an MILP where I know a feasible solution exists.
Yet, I received a "Solution is not feasible" error.
I added a constraint "var_1 == var_2", ...
- 93
2
votes
1
answer
305
views
ILP - "Is variable equal to another variable"
In an ILP, given two variables x and y, is it possible to define a variable z where
z = (x==y)?
Meaning, if x equals y then z = 1.
Else, z = 0.
x and y are integer variables bounded between (1, M).
- 93
0
votes
1
answer
100
views
Ilp - count number of times variables received a value
In an ILP, is it possible to have a variable whose value will be the number of variables with value N?
N is a bounded integer, with lower bound 1.
Thank you
- 93
-1
votes
1
answer
110
views
ILP: Exclusive range for variable
In an ILP, How can I write a constraint "X is not in the interval [Y, Y+10]" ?
Is it even possible?
- 93