All Questions
11 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
254
views
Detect Disconnected Subtours in Graph
I have used an Integer Linear Program (ILP) to generate a path from source to sink in a graph. Each variable Pij in the solution represents a transition from node i to j in the path. Unfortunately, ...
- 143
4
votes
1
answer
482
views
How to maximize distance between nodes on a graph?
I have an undirected graph such as the one shown below. I can make up to 3 choices about the color of each node. The edge weights are equal to the difference between the nodes, given by the "...
- 176
0
votes
1
answer
212
views
How to minimize a linear function to the constraints, my confusion arises from the notation?
So essentially I understand how to minimize/maximize a linear function when I am given it in the form such as y = mx + b.
But the problem involves a flow network and linear programming, and this is ...
- 31
5
votes
4
answers
1k
views
How would I efficiently find the min and max values of the variables in this constraint system?
I have a system where I need to calculate the possible range of values for each variable (I don't need to find a solution to the system). Here is an illustration of an example system:
Each blue line ...
- 525
0
votes
0
answers
62
views
How to greedily add as many equality constraints as possible to a set of inequality constraints?
I have a set of inequality constraints of the following form:
x >= y + 3
y >= z + 4
z >= w + 1
z >= y - 8
w >= x + 0
And I guarantee that these constraints have a solution. I also have ...
- 672
0
votes
1
answer
481
views
Flaw in linear programming solution for multi-commodity flow?
The multi-commodity flow problem problem statement - wiki
According to constraints of multi-commodity flow problem a given material must start at source s with demand d and end up at its target t. ...
- 717
3
votes
3
answers
3k
views
Heuristic to find the maximum weight independent set in an arbritary graph
The MWIS (Maximum weight independent set) is a NP-complete problem, so if P!=NP we cannot find a solution in a good enough time complexity.
I am looking for an algorithm that can find an ...
- 33
2
votes
1
answer
161
views
Bipartite matching with a twist
I'm working on a scheduling problem assigning speakers to slots, with speakers having varying availability. A maximum matching unweighed bipartite graph works for a simple solution where each speaker ...
- 9,529
7
votes
2
answers
1k
views
Vertex-Coloring/Assignment to minimize the number of "color crossings"
I am not sure if this is really a "coloring" problem as much as it is an assignment/linear-programming problem. I have zero expertise in either, so pardon any noob-ness that might follow. But I get ...
- 71
27
votes
5
answers
21k
views
How to choose an integer linear programming solver?
I am newbie for integer linear programming.
I plan to use a integer linear programming solver to solve my combinatorial optimization problem.
I am more familiar with C++/object oriented programming on ...
- 271