> Interesting to note that in many cases (even in the cases when the > puzzle is classified as very hard) the lp relaxation is yet integer > feasible and therefore branching is not needed, though Sudoku is > proven to be np-hard. Moreover, many instances can be solved by the > mip presolver (--intopt in glpsol 4.9).
The following data section describes a hard Sudoku puzzle and being used with the model sudoku.mod http://lists.gnu.org/archive/html/help-glpk/2006-03/msg00013.html causes branching: /* sudoku.dat, a hard Sudoku puzzle which causes branching */ data; param givens : 1 2 3 4 5 6 7 8 9 := 1 1 . . . . . 7 . . 2 . 2 . . . . 5 . . 3 6 . . 3 8 . . . . 4 . 7 8 . . . . . . 5 . . . 6 . 9 . . . 6 . . . . . . 1 4 . 7 . . . . 2 5 . . 9 8 . . 3 . . . . 6 . 9 . . 4 . . . . . 2 ; end; _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
