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.

  • 8
    $\begingroup$ FYI - this is not about Moms I'd like to Punch... $\endgroup$ Oct 31 '11 at 5:24
  • 1
    $\begingroup$ @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! $\endgroup$ Oct 31 '11 at 9:58

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$.

  • $\begingroup$ what is the purpose of the target function? $\endgroup$
    – hhh
    Oct 31 '11 at 8:07
  • $\begingroup$ Target (goal) function is needed when your solution method requires a function to be minimized or maximized. $\endgroup$
    – Jiri Kriz
    Oct 31 '11 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.