This section contains a number of examples which are intended to illustrate the usage of Gurobify. These examples also form a test suite (along with "Simple Example" in Chapter 2), which can be used to check that Gurobify is functioning properly. See Section 1.5 "Testing and documentation" for more on this aspect of the examples.
To solve a sudoku puzzle, the integers from 1 to 9 must be placed in each cell of a 9 \times 9 grid, such that every number in a column, row, or one of the nine subgrids, is different. A starting configuration is given which must be incorporated into the final solution. In this example we create a model which imposes the sudoku rules as constraints, takes an additional constraint for the starting configuration of the Sudoku puzzle, and then solves the puzzle.
To begin with we will define the variables that we will need for our model. Each variable will have a name of the form x_{ijk}, where i is the row of the sudoku puzzle, j is the column, and k is the value of the entry defined byt cell ij. The variables are binary, since a value of 1 indicates that the corresponding cell ij has value k, and a 0 indicates that it doesn't have that value.
Since the variable names are important to the fomulation of this problem, we must define the variable names.
gap> var_names :=[]; [ ] gap> for i in [1 .. 9] do > for j in [1 .. 9] do > for k in [1 .. 9] do > name := Concatenation("x", String(i), String(j), String(k));; > Add(var_names, name); > od; > od; > od;
Now create the model. We need to tell Gurobi that each variable is binary.
gap> var_types := ListWithIdenticalEntries( Size( var_names ), "Binary" );; gap> model := GurobiNewModel( var_types, var_names ); Gurobi model
Here we define a few basic functions which are purely for the purpose of this example. Firstly a way to go from the names of a subset of the variables to the corresponding index set. Secondly, a way of going back from the index set to identify the variable name. Lastly, a method of displaying the Sudoku board from the names of the variables which are in the solution set.
gap> ExampleFuncNamesToIndex := function( var_names, var_included ) > local vars, ind; > vars := ListWithIdenticalEntries( Size( var_names ), 0 ); > ind := List( var_included, t -> Position( var_names, t )); > vars{ ind }:=ListWithIdenticalEntries( Size( var_included ), 1 ); > return vars; > end; function( var_names, var_included ) ... end gap> ExampleFuncIndexToNames := function( var_names, index_set ) > local i, keep; > keep := []; > for i in var_names do > if index_set[Position( var_names, i)] = 1. then > Add(keep, i); > fi; > od; > return keep; > end; function( var_names, index_set ) ... end gap> gap> ExampleFuncDisplaySudoku := function( sol2 ) > local mat_sol, m, i, j, k; > mat_sol := NullMat(9, 0);; > for m in sol2 do > i := EvalString( [m[2]] ); > j := EvalString( [m[3]] ); > k := EvalString( [m[4]] ); > mat_sol[i][j] := k; > od; > Display(mat_sol); > end; function( sol2 ) ... end
Ensure that a square only takes a single value.
gap> for i in [1 .. 9] do > for j in [1 .. 9] do > uniqueness_constr :=[]; > for k in [1 .. 9] do > name := Concatenation("x", String(i), String(j), String(k));; > Add(uniqueness_constr, name); > od; > constr := ExampleFuncNamesToIndex( var_names, uniqueness_constr ); > GurobiAddConstraint( model, constr , "=", 1 ); > od; > od;
Ensure that each value occurs exactly once per row.
gap> for i in [1 .. 9] do > for k in [1 .. 9] do > row_constr :=[]; > for j in [1 .. 9] do > name := Concatenation("x", String(i), String(j), String(k));; > Add(row_constr, name ); > od; > constr := ExampleFuncNamesToIndex( var_names, row_constr ); > GurobiAddConstraint( model, constr, "=", 1 ); > od; > od;
Ensure that each value occurs exactly once per column.
gap> for j in [1 .. 9] do > for k in [1 .. 9] do > column_constr :=[]; > for i in [1 .. 9] do > name := Concatenation("x", String(i), String(j), String(k));; > Add(column_constr, name); > od; > constr := ExampleFuncNamesToIndex( var_names, column_constr ); > GurobiAddConstraint(model, constr, "=", 1); > od; > od;
Ensure that each value occurs exactly once per sub-square. We start at the top left corner of each square and work our way through them.
gap> starter_points := [ [1,1], [1,4], [1,7], [4,1], [4,4], > [4,7], [7,1], [7,4], [7,7]];; gap> for m in starter_points do > for k in [1 .. 9] do > square_constr := []; > for i in [0 .. 2] do > for j in [0 .. 2] do > name := Concatenation( > "x", String(m[1] + i), String(m[2] + j), String(k) > );; > Add(square_constr, name); > od; > od; > constr := ExampleFuncNamesToIndex( var_names, square_constr ); > GurobiAddConstraint(model, constr, "=", 1); > od; > od;
The model now has constraints that will ensure that the Sudoku rules are obeyed. We can put in the inital Sudoku configuration by assigning values to certain entries of the sudoku matrix.
gap> starter_squares := ["x112", "x123", "x164", "x217", "x248", "x326", > "x343", "x391", "x411", "x422", "x488", "x516", "x549", "x568", > "x595", "x625", "x682", "x693", "x719", "x767", "x785", "x865", > "x894", "x942", "x986", "x998"];; gap> constr := ExampleFuncNamesToIndex(var_names, starter_squares);; gap> GurobiAddConstraint( model, constr , "=", Sum( constr ), "StarterSquares"); true
Now we optimise. Change the solution into the set of variable names, and then display the solution.
gap> GurobiOptimiseModel( model ); 2 gap> sol := GurobiSolution( model );; gap> sol2 := ExampleFuncIndexToNames( var_names, sol );; gap> ExampleFuncDisplaySudoku( sol2 ); [ [ 2, 3, 1, 6, 5, 4, 8, 9, 7 ], [ 7, 9, 4, 8, 1, 2, 5, 3, 6 ], [ 5, 6, 8, 3, 7, 9, 2, 4, 1 ], [ 1, 2, 7, 5, 3, 6, 4, 8, 9 ], [ 6, 4, 3, 9, 2, 8, 7, 1, 5 ], [ 8, 5, 9, 7, 4, 1, 6, 2, 3 ], [ 9, 1, 6, 4, 8, 7, 3, 5, 2 ], [ 3, 8, 2, 1, 6, 5, 9, 7, 4 ], [ 4, 7, 5, 2, 9, 3, 1, 6, 8 ] ]
At this point we may wish to save the model as an lp file so that other Sudoku problems may be quickly and easily solved in the future. Of course, we do not want to save the starter configuration, only the general Sudoku constraints, and so we must first delete the the constraint "StarterSquares".
gap> GurobiDeleteConstraintsWithName( model, "StarterSquares" ); true gap> GurobiWriteToFile( model, "SudokuSolver.lp" ); true
We can now load the lp file to create a new model with all the generic Sudoku constraints. Assuming we have defined the functions ExampleFuncNamesToIndex, ExampleFuncIndexToNames and ExampleFuncDisplaySudoku as before, we may simply add a new constraint to the model to represent the starting configuration of the Sudoku problem. In case we do not remember the variable names or their order, we can first extract this information from the model. We then optimise the model and display the solution as before.
gap> model2 := GurobiReadModel( "SudokuSolver.lp" ); Gurobi model gap> var_names2 := GurobiVariableNames(model2);; gap> starter_squares := ["x118", "x124", "x132", "x145", "x161", "x219", > "x337", "x353", "x414", "x425", "x441", "x539", "x544", "x562", > "x573", "x669", "x686", "x691", "x754", "x778", "x894", "x947", > "x968", "x971", "x985", "x999"];; gap> constr := ExampleFuncNamesToIndex(var_names2, starter_squares);; gap> GurobiAddConstraint(model2, constr , "=", Sum( constr )); true gap> GurobiOptimiseModel(model2); 2 gap> sol := GurobiSolution(model2);; gap> sol2 := ExampleFuncIndexToNames(var_names2, sol);; gap> ExampleFuncDisplaySudoku( sol2 ); [ [ 8, 4, 2, 5, 9, 1, 7, 3, 6 ], [ 9, 3, 1, 6, 2, 7, 5, 4, 8 ], [ 5, 6, 7, 8, 3, 4, 9, 1, 2 ], [ 4, 5, 3, 1, 8, 6, 2, 9, 7 ], [ 6, 1, 9, 4, 7, 2, 3, 8, 5 ], [ 2, 7, 8, 3, 5, 9, 4, 6, 1 ], [ 1, 9, 6, 2, 4, 5, 8, 7, 3 ], [ 7, 8, 5, 9, 1, 3, 6, 2, 4 ], [ 3, 2, 4, 7, 6, 8, 1, 5, 9 ] ]
What if we removed a initial value from the Sudoku problem? How many solutions would there be? We remove set an entry from the starter configuration and then optimise. We feed this solution back in as a constraint, and then reoptimise. We can repeat this process until we have found all feasible solutions, which will be when the model becomes infeasible.
gap> model3 := GurobiReadModel( "SudokuSolver.lp" ); Gurobi model gap> var_names3 := GurobiVariableNames(model3);; gap> starter_squares := ["x118", "x124", "x132", "x145", "x161", "x219", > "x337", "x353", "x414", "x425", "x441", "x539", "x544", "x562", > "x573", "x669", "x686", "x691", "x754", "x778", "x894", "x947", > "x968", "x971", "x985"];; gap> constr := ExampleFuncNamesToIndex(var_names3, starter_squares);; gap> GurobiAddConstraint( model3, constr , "=", Sum( constr )); true gap> GurobiOptimiseModel( model3 ); 2 gap> number_of_solutions := 0;; gap> while GurobiOptimisationStatus( model3 ) = 2 do > sol := GurobiSolution( model3 );; > number_of_solutions := number_of_solutions + 1; > GurobiAddConstraint( model3, sol , "<", 80 ); > GurobiUpdateModel( model3 ); > GurobiReset(model3); > GurobiOptimiseModel( model3 ); > od; gap> Print( number_of_solutions, "\n"); 66
generated by GAPDoc2HTML