1
$\begingroup$

My homework contains a word (freely-translated) "target-function" that I should generate somehow for 9x9 sudoku solver with some MILP problem. But I am bit lost what they mean. I have sofar described the problem as below. Is this the target function for MILP problem (apparently meaning mixed integer linear problem or something like that)?

\begin{cases} \forall r\in {1,2,...,9}\sum_{c=1}^{9}V_{rc}=45 \\ \forall c\in{1,2,...,9}\sum_{r=1}^{9}V_{rc}=45 \\ \forall r\in{1,2,...,9}\forall n\in {1,2,...,9} \sum_{c=1}^{9}x_{rcn} = 1 \\ \forall c\in{1,2,...,9}\forall n\in{1,2,...,9}\sum_{r=1}^{9}x_{rcn} = 1 \ \end{cases}

where $x_{rcn}$ is a binary function with $r$ for row, $c$ for column and $n$ for number between 1 and 9. $V_{rc}$ means the number $n$ in the position $(r,c)$. When I look at wikipedia about the mathematics of sudoku here, I am worried that my way of formulating the problem is not right at all. When I google for MILP, I do not get descriptive hits -- what does this MILP function thing mean?

I have not yet understood how I can formulate the above messy formulates more elegantly, perhaps with the group tabels...sorry I am bit puzzled with the tables in the wikipedia article.

  • 1
    @hhh: if you don't know «what the purpose of the target function» is while doing this kind of homework, you should *really* get your notes/textbook and take the time read them carefully and at leisure, and/or ask your instructor... You are doing homework about MILPs and you do not even know what the letters mean: even asking here infinitely many questions is nt the way to learn the material!2011-10-31

1 Answers 1

4

The linear program can be formulated just using the binary 0/1-variables $x_{rcn}$ with the meaning $x_{rcn} = 1$ if and only if there is the number $n$ in the cell $rc$, i.e in the row $r$ and the column $c$. There are $9*9*9 = 729$ variables $x_{rcn}$.

The constaints are:

(1) There is exactly one number in a cell: $x_{rc1} + x_{rc2} + ... + x_{rc9} = 1; r, c = 1, .., 9$

(2) The number $n$ appears exactly once in each column and each row: $x_{r1n} + x_{r2n} + ... + x_{r9n} = 1; r, n = 1, .., 9$ $x_{1cn} + x_{2cn} + ... + x_{9cn} = 1; c, n = 1, .., 9$

(3) The number $n$ appears exactly once in each of the nine 3x3 boxes: $x_{11n} + x_{12n} + ... + x_{33n} = 1; n = 1, .., 9$ $...$ $x_{77n} + x_{78n} + ... + x_{99n} = 1; n = 1, .., 9$

The number of constrains is: (1) 81, (2) 81 + 81 = 162, (3) 81, totally 324. Additional constrains are given by predefined positions. For example if there is the number 3 in the position (2, 5), then $x_{253} = 1$.

There is no explicit target function. If a target function is needed, then any linear function of the free binary variables can be taken, e.g. $x_{111} = min/max$.

  • 0
    Target (goal) function is needed when your solution method requires a function to be minimized or maximized.2011-10-31