search

takemaru / graphillion

Fast, lightweight graphset operation library
Other
466 stars 40 forks source link

Creating a Graphset Using a Toy Example #63

Open seanlaw opened 2 years ago

seanlaw commented 2 years ago

Hi @takemaru! I hope you are well. Can you please help me understand if Graphillion could be used to represent and solve the following toy problem?

Let's say that I have a discrete function that can be described as $2x{0}+3x{1}+5x{2}+5x{3} \ge 7$, where $x{i} \in \set{0,1}$. Once I find all of the combinations of $(x{0}, x{1}, x{2}, x{3})$ that satisfy this constraint, I would like to find the shortest path that minimizes the objective function $2x{0}-3x{1}+4x{2}+6x_{3}$.

For example, $(x{0}, x{1}, x{2}, x{3}) = (0, 1, 1, 0)$ would satisfy the function since $2\cdot0+3\cdot0+5\cdot1+5\cdot1 = 10$, which is greater than or equal to $7$. Next, substituting $(x{0}, x{1}, x{2}, x{3}) = (0, 1, 1, 0)$ into the objective function would result in a path length of $2\cdot0-3\cdot0+4\cdot1+6\cdot1=10$. However, this is only one solution and it is also not the shortest path!

Can you please tell me the best way to:

  1. Construct the graphset for this problem using Graphillion
    • I believe that this step may be referred to as "enumeration" in the literature. If I understand correctly, this can be done naively by iterating through $2^{n}$ combinations (e.g., for $(x{0}, x{1}, x{2}, x{3}),$ there would be $2^{4} = 16$ combinations) but this is very inefficient for large $n$. Perhaps, this is where the "frontier-based search" comes in but I don't understand what inputs I need to provide to Graphillion to do this automatically
  2. Find all values of $(x{0}, x{1}, x{2}, x{3})$ that satisfy $2x{0}+3x{1}+5x{2}+5x{3} \ge 7$
  3. Find the 3 shortest paths (computed from $2x{0}-3x{1}+4x{2}+6x{3}$) using the solutions identified in step 2

I'm having some conceptual trouble setting this up using the Graphillion framework. I understand that I could try to enumerate all of combinations of $(x{0}, x{1}, x{2}, x{3})$ but, in my real use case, I may have as many as $(x{0}, x{1}, ..., x{1000})$. Also, $x{i} \in \set{0, ..., 25}$ and so I was hoping that Graphillion may be a good use case.

Any help, suggestions, or code examples using Graphillion would be greatly appreciated!

takemaru commented 2 years ago

Sorry for the late response. Although I can't understand the relationship between the objective and paths on a graph in your problem, I recommend to use an ILP solver like Gurobi for problems constrained by inequalities.