Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
8  
FYI - this is not about Moms I'd like to Punch... –  The Chaz 2.0 Oct 31 '11 at 5:24
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! –  Mariano Suárez-Alvarez Oct 31 '11 at 9:58
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
what is the purpose of the target function? –  hhh Oct 31 '11 at 8:07
    
Target (goal) function is needed when your solution method requires a function to be minimized or maximized. –  Jiri Oct 31 '11 at 9:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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