Dancing Links internal pyx code¶
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: x = dlx_solver(rows)
sage: x
Dancing links solver for 6 columns and 6 rows
The number of solutions:
sage: x.number_of_solutions()
3
Iterate over the solutions:
sage: sorted(map(sorted, x.solutions_iterator()))
[[0, 1], [2, 3], [4, 5]]
All solutions (computed in parallel):
sage: sorted(map(sorted, x.all_solutions()))
[[0, 1], [2, 3], [4, 5]]
Return the first solution found when the computation is done in parallel:
sage: sorted(x.one_solution(ncpus=2)) # random
[0, 1]
Find all solutions using some specific rows:
sage: x_using_row_2 = x.restrict([2])
sage: x_using_row_2
Dancing links solver for 7 columns and 6 rows
sage: sorted(map(sorted, x_using_row_2.solutions_iterator()))
[[2, 3]]
The two basic methods that are wrapped in this class are search
which
returns 1
if a solution is found or 0
otherwise and get_solution
which return the current solution:
sage: x = dlx_solver(rows)
sage: x.search()
1
sage: x.get_solution()
[0, 1]
sage: x.search()
1
sage: x.get_solution()
[2, 3]
sage: x.search()
1
sage: x.get_solution()
[4, 5]
sage: x.search()
0
There is also a method reinitialize
to reinitialize the algorithm:
sage: x.reinitialize()
sage: x.search()
1
sage: x.get_solution()
[0, 1]
- class sage.combinat.matrices.dancing_links.dancing_linksWrapper¶
Bases:
object
A simple class that implements dancing links.
The main methods to list the solutions are
search()
andget_solution()
. You can also usenumber_of_solutions()
to count them.This class simply wraps a C++ implementation of Carlo Hamalainen.
- all_solutions(ncpus=None, column=None)¶
Return all solutions found after splitting the problem to allow parallel computation.
INPUT:
ncpus
– integer (default:None
), maximal number of subprocesses to use at the same time. IfNone
, it detects the number of effective CPUs in the system usingsage.parallel.ncpus.ncpus()
.column
– integer (default:None
), the column used to split the problem, ifNone
a random column is chosen
OUTPUT:
list of solutions
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]] sage: d = dlx_solver(rows) sage: S = d.all_solutions() sage: sorted(sorted(s) for s in S) [[0, 1], [2, 3], [4, 5]]
The number of CPUs can be specified as input:
sage: S = Subsets(range(4)) sage: rows = map(list, S) sage: dlx = dlx_solver(rows) sage: dlx Dancing links solver for 4 columns and 16 rows sage: dlx.number_of_solutions() 15 sage: sorted(sorted(s) for s in dlx.all_solutions(ncpus=2)) [[1, 2, 3, 4], [1, 2, 10], [1, 3, 9], [1, 4, 8], [1, 14], [2, 3, 7], [2, 4, 6], [2, 13], [3, 4, 5], [3, 12], [4, 11], [5, 10], [6, 9], [7, 8], [15]]
If
ncpus=1
, the computation is not done in parallel:sage: sorted(sorted(s) for s in dlx.all_solutions(ncpus=1)) [[1, 2, 3, 4], [1, 2, 10], [1, 3, 9], [1, 4, 8], [1, 14], [2, 3, 7], [2, 4, 6], [2, 13], [3, 4, 5], [3, 12], [4, 11], [5, 10], [6, 9], [7, 8], [15]]
- get_solution()¶
Return the current solution.
After a new solution is found using the method
search()
this method return the rows that make up the current solution.
- ncols()¶
Return the number of columns.
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [1,2], [0], [3,4,5]] sage: dlx = dlx_solver(rows) sage: dlx.ncols() 6
- nrows()¶
Return the number of rows.
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [1,2], [0], [3,4,5]] sage: dlx = dlx_solver(rows) sage: dlx.nrows() 4
- number_of_solutions(ncpus=None, column=None)¶
Return the number of distinct solutions.
INPUT:
ncpus
– integer (default:None
), maximal number of subprocesses to use at the same time. If \(ncpus>1\) the dancing links problem is split into independent subproblems to allow parallel computation. IfNone
, it detects the number of effective CPUs in the system usingsage.parallel.ncpus.ncpus()
.column
– integer (default:None
), the column used to split the problem, ifNone
a random column is chosen (this argument is ignored ifncpus
is1
)
OUTPUT:
integer
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2]] sage: rows += [[0,2]] sage: rows += [[1]] sage: rows += [[3]] sage: x = dlx_solver(rows) sage: x.number_of_solutions() 2
The number of CPUs can be specified as input:
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]] sage: x = dlx_solver(rows) sage: x.number_of_solutions(ncpus=2, column=3) 3
sage: S = Subsets(range(5)) sage: rows = map(list, S) sage: d = dlx_solver(rows) sage: d.number_of_solutions() 52
- one_solution(ncpus=None, column=None)¶
Return the first solution found.
This method allows parallel computations which might be useful for some kind of problems when it is very hard just to find one solution.
INPUT:
ncpus
– integer (default:None
), maximal number of subprocesses to use at the same time. IfNone
, it detects the number of effective CPUs in the system usingsage.parallel.ncpus.ncpus()
. Ifncpus=1
, the first solution is searched serially.column
– integer (default:None
), the column used to split the problem (seerestrict()
). IfNone
, a random column is chosen. This argument is ignored ifncpus=1
.
OUTPUT:
list of rows or
None
if no solution is foundNote
For some case, increasing the number of cpus makes it faster. For other instances,
ncpus=1
is faster. It all depends on problem which is considered.EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]] sage: d = dlx_solver(rows) sage: solutions = [[0,1], [2,3], [4,5]] sage: sorted(d.one_solution()) in solutions True
The number of CPUs can be specified as input:
sage: sorted(d.one_solution(ncpus=2)) in solutions True
The column used to split the problem for parallel computations can be given:
sage: sorted(d.one_solution(ncpus=2, column=4)) in solutions True
When no solution is found:
sage: rows = [[0,1,2], [2,3,4,5], [0,1,2,3]] sage: d = dlx_solver(rows) sage: d.one_solution() is None True
- one_solution_using_milp_solver(solver=None, integrality_tolerance=0.001)¶
Return a solution found using a MILP solver.
INPUT:
solver
– string orNone
(default:None
), possible values include'GLPK'
,'GLPK/exact'
,'Coin'
,'CPLEX'
,'Gurobi'
,'CVXOPT'
,'PPL'
,'InteractiveLP'
.
OUTPUT:
list of rows or
None
if no solution is foundNote
When comparing the time taken by method \(one_solution\), have in mind that \(one_solution_using_milp_solver\) first creates (and caches) the MILP solver instance from the dancing links solver. This copy of data may take many seconds depending on the size of the problem.
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]] sage: d = dlx_solver(rows) sage: solutions = [[0,1], [2,3], [4,5]] sage: d.one_solution_using_milp_solver() in solutions True
Using optional solvers:
sage: s = d.one_solution_using_milp_solver('gurobi') # optional - gurobi sage_numerical_backends_gurobi sage: s in solutions # optional - gurobi sage_numerical_backends_gurobi True
When no solution is found:
sage: rows = [[0,1,2], [2,3,4,5], [0,1,2,3]] sage: d = dlx_solver(rows) sage: d.one_solution_using_milp_solver() is None True
- one_solution_using_sat_solver(solver=None)¶
Return a solution found using a SAT solver.
INPUT:
solver
– string orNone
(default:None
), possible values include'picosat'
,'cryptominisat'
,'LP'
,'glucose'
,'glucose-syrup'
.
OUTPUT:
list of rows or
None
if no solution is foundNote
When comparing the time taken by method \(one_solution\), have in mind that \(one_solution_using_sat_solver\) first creates the SAT solver instance from the dancing links solver. This copy of data may take many seconds depending on the size of the problem.
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]] sage: d = dlx_solver(rows) sage: solutions = [[0,1], [2,3], [4,5]] sage: d.one_solution_using_sat_solver() in solutions True
Using optional solvers:
sage: s = d.one_solution_using_sat_solver('glucose') # optional - glucose sage: s in solutions # optional - glucose True
When no solution is found:
sage: rows = [[0,1,2], [2,3,4,5], [0,1,2,3]] sage: d = dlx_solver(rows) sage: d.one_solution_using_sat_solver() is None True
- reinitialize()¶
Reinitialization of the search algorithm
This recreates an empty \(dancing_links\) object and adds the rows to the instance of dancing_links.
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]] sage: x = dlx_solver(rows) sage: x.get_solution() if x.search() else None [0, 1] sage: x.get_solution() if x.search() else None [2, 3]
Reinitialization of the algorithm:
sage: x.reinitialize() sage: x.get_solution() if x.search() else None [0, 1] sage: x.get_solution() if x.search() else None [2, 3] sage: x.get_solution() if x.search() else None [4, 5] sage: x.get_solution() if x.search() else None
Reinitialization works after solutions are exhausted:
sage: x.reinitialize() sage: x.get_solution() if x.search() else None [0, 1] sage: x.get_solution() if x.search() else None [2, 3] sage: x.get_solution() if x.search() else None [4, 5] sage: x.get_solution() if x.search() else None
- restrict(indices)¶
Return a dancing links solver solving the subcase which uses some given rows.
For every row that is wanted in the solution, we add a new column to the row to make sure it is in the solution.
INPUT:
indices
– list, row indices to be found in the solution
OUTPUT:
dancing links solver
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]] sage: d = dlx_solver(rows) sage: d Dancing links solver for 6 columns and 6 rows sage: sorted(map(sorted, d.solutions_iterator())) [[0, 1], [2, 3], [4, 5]]
To impose that the 0th row is part of the solution, the rows of the new problem are:
sage: d_using_0 = d.restrict([0]) sage: d_using_0 Dancing links solver for 7 columns and 6 rows sage: d_using_0.rows() [[0, 1, 2, 6], [3, 4, 5], [0, 1], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]]
After restriction the subproblem has one more columns and the same number of rows as the original one:
sage: d.restrict([1]).rows() [[0, 1, 2], [3, 4, 5, 6], [0, 1], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]] sage: d.restrict([2]).rows() [[0, 1, 2], [3, 4, 5], [0, 1, 6], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]]
This method allows to find solutions where the 0th row is part of a solution:
sage: sorted(map(sorted, d.restrict([0]).solutions_iterator())) [[0, 1]]
Some other examples:
sage: sorted(map(sorted, d.restrict([1]).solutions_iterator())) [[0, 1]] sage: sorted(map(sorted, d.restrict([2]).solutions_iterator())) [[2, 3]] sage: sorted(map(sorted, d.restrict([3]).solutions_iterator())) [[2, 3]]
Here there are no solution using both 0th and 3rd row:
sage: list(d.restrict([0,3]).solutions_iterator()) []
- rows()¶
Return the list of rows.
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [1,2], [0]] sage: x = dlx_solver(rows) sage: x.rows() [[0, 1, 2], [1, 2], [0]]
- search()¶
Search for a new solution.
Return
1
if a new solution is found and0
otherwise. To recover the solution, use the methodget_solution()
.EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2]] sage: rows+= [[0,2]] sage: rows+= [[1]] sage: rows+= [[3]] sage: x = dlx_solver(rows) sage: print(x.search()) 1 sage: print(x.get_solution()) [3, 0]
- solutions_iterator()¶
Return an iterator of the solutions.
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]] sage: d = dlx_solver(rows) sage: sorted(map(sorted, d.solutions_iterator())) [[0, 1], [2, 3], [4, 5]]
- split(column)¶
Return a dict of independent solvers.
For each
i
-th row containing a1
in thecolumn
, the dict associates the solver giving all solution using thei
-th row.This is used for parallel computations.
INPUT:
column
– integer, the column used to split the problem into independent subproblems
OUTPUT:
dict where keys are row numbers and values are dlx solvers
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]] sage: d = dlx_solver(rows) sage: d Dancing links solver for 6 columns and 6 rows sage: sorted(map(sorted, d.solutions_iterator())) [[0, 1], [2, 3], [4, 5]]
After the split each subproblem has one more column and the same number of rows as the original problem:
sage: D = d.split(0) sage: D {0: Dancing links solver for 7 columns and 6 rows, 2: Dancing links solver for 7 columns and 6 rows, 4: Dancing links solver for 7 columns and 6 rows}
The (disjoint) union of the solutions of the subproblems is equal to the set of solutions shown above:
sage: for x in D.values(): sorted(map(sorted, x.solutions_iterator())) [[0, 1]] [[2, 3]] [[4, 5]]
- to_milp(solver=None)¶
Return the mixed integer linear program (MILP) representing an equivalent problem.
See also
sage.numerical.mip.MixedIntegerLinearProgram
.INPUT:
solver
– string orNone
(default:None
), possible values include'GLPK'
,'GLPK/exact'
,'Coin'
,'CPLEX'
,'Gurobi'
,'CVXOPT'
,'PPL'
,'InteractiveLP'
.
OUTPUT:
MixedIntegerLinearProgram instance
MIPVariable with binary components
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [0,2], [1], [3]] sage: d = dlx_solver(rows) sage: p,x = d.to_milp() sage: p Boolean Program (no objective, 4 variables, 4 constraints) sage: x MIPVariable with 4 binary components
In the reduction, the boolean variable x_i is True if and only if the i-th row is in the solution:
sage: p.show() Maximization: Constraints: one 1 in 0-th column: 1.0 <= x_0 + x_1 <= 1.0 one 1 in 1-th column: 1.0 <= x_0 + x_2 <= 1.0 one 1 in 2-th column: 1.0 <= x_0 + x_1 <= 1.0 one 1 in 3-th column: 1.0 <= x_3 <= 1.0 Variables: x_0 is a boolean variable (min=0.0, max=1.0) x_1 is a boolean variable (min=0.0, max=1.0) x_2 is a boolean variable (min=0.0, max=1.0) x_3 is a boolean variable (min=0.0, max=1.0)
Using some optional MILP solvers:
sage: d.to_milp('gurobi') # optional - gurobi sage_numerical_backends_gurobi (Boolean Program (no objective, 4 variables, 4 constraints), MIPVariable with 4 binary components)
- to_sat_solver(solver=None)¶
Return the SAT solver solving an equivalent problem.
Note that row index \(i\) in the dancing links solver corresponds to the boolean variable index \(ì+1\) for the SAT solver to avoid the variable index \(0\).
See also
sage.sat.solvers.satsolver
.INPUT:
solver
– string orNone
(default:None
), possible values include'picosat'
,'cryptominisat'
,'LP'
,'glucose'
,'glucose-syrup'
.
OUTPUT:
SAT solver instance
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [0,2], [1], [3]] sage: x = dlx_solver(rows) sage: s = x.to_sat_solver()
Using some optional SAT solvers:
sage: x.to_sat_solver('cryptominisat') # optional - cryptominisat CryptoMiniSat solver: 4 variables, 7 clauses.
- sage.combinat.matrices.dancing_links.dlx_solver(rows)¶
Internal-use wrapper for the dancing links C++ code.
EXAMPLES:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2]] sage: rows+= [[0,2]] sage: rows+= [[1]] sage: rows+= [[3]] sage: x = dlx_solver(rows) sage: print(x.search()) 1 sage: print(x.get_solution()) [3, 0] sage: print(x.search()) 1 sage: print(x.get_solution()) [3, 1, 2] sage: print(x.search()) 0
- sage.combinat.matrices.dancing_links.make_dlxwrapper(s)¶
Create a dlx wrapper from a Python string s.
This was historically used in unpickling and is kept for backwards compatibility. We expect s to be
dumps(rows)
where rows is the list of rows used to instantiate the object.