Problemas de Asignación - Sudoku

Problema del Sudoku

Modelo

Variables

$$\begin{array}{rlrl}I& =\{1,\dots ,9\}& & \text{conjunto de dıˊgitos}\\ J& =\{1,\dots ,81\}& & \text{conjunto de celdas}\\ F& =\{F_1,\dots ,F_9\}& & \text{conjunto de filas, cada }{F}_r\subseteq J\\ C& =\{C_1,\dots ,C_9\}& & \text{conjunto de columnas, cada }{C}_c\subseteq J\\ B& =\{B_1,\dots ,B_9\}& & \text{conjunto de bloques }3\times 3,\text{cada }{B}_b\subseteq J\\ K& =\{K_1,\dots ,K_{27}\}& & \text{configuraciones con }{K}_k\in F\cup C\cup B\\ & & & \text{(9 filas, 9 columnas, 9 bloques)}\\ P& \subseteq I\times J& & \text{pistas: si }(i,j)\in P,\text{la celda }j\text{ estaˊ fijada al dıˊgito }i\end{array}$$

Variables de decisión:

$$\begin{array}{rl}& x_{ij}\in \{0,1\}\forall i\in I,\forall j\in J\\ & \\ & \text{donde }{x}_{ij}=1\text{ si el dıˊgito }i\text{ se asigna a la celda }j;0\text{ en caso contrario}\end{array}$$

Función objetivo

$$\min \sum _{i\in I}\sum _{j\in J}{C}_{ij}\times X_{ij}$$

La función objetivo en este caso no es necesaria

Puesto que es un problema de factibilidad, pero con esta función estaríamos haciendo un sudoku modificado más interesante.

Restricciones

1. Asignación única por celda:

$$\sum _{i\in I}{x}_{ij}=1\forall j\in J$$

2. No repetir dígito en cada configuración $K_k$ (filas, columnas y bloques):

$$\sum _{j\in K_k}{x}_{ij}=1\forall i\in I,\forall k\in \{1,\dots ,27\}$$

3. Fijación de pistas (decisiones ya tomadas):

$$x_{ij}=1\forall (i,j)\in P$$

4. Dominio:

$$x_{ij}\in \{0,1\}\forall i\in I,\forall j\in J$$

Código

m=81 # nº Celdas
k=27 # nº Configuraciones: n filas + n columnas + n cuadrantes
n=9 # nº Digitos
C=1:m # Conjunto de celdas
F = [] # Array con los array de celdas correspondientes a cada configuración. Columnas/filas/cuadrantes
 
# Añadir filas (cada fila tiene celdas consecutivas)
for i in 1:9
	push!(F, [(i - 1) * 9 + j for j in 1:9]) # Ej: fila 1 tiene celdas 1 a 9
end
# Añadir columnas (cada columna tiene celdas separadas por 9)
 
for j in 1:9
	push!(F, [j + 9 * (i - 1) for i in 1:9]) # Ej: columna 1 tiene celdas 1, 10, 19...
end
 
# Añadir cuadrantes (3x3 bloques)
for q_row in 0:2
	for q_col in 0:2
		# Corregir el cálculo para que los índices estén en el rango de 1 a 81	
		start = 27 * q_row + 3 * q_col + 1	
		# println("Number: ",[start + i % 3 + 9 * div(i, 3) for i in 0:8])
		push!(F, [start + i % 3 + 9 * div(i, 3) for i in 0:8])
	
	end
end
 
# Verificación de que tenemos 27 configuraciones
 
@assert length(F) == 27 # F ahora tiene las celdas para 9 filas, 9 columnas y 9 cuadrantes
 
D=1:n
model = Model(HiGHS.Optimizer)
set_silent(model)
 
@variable(model, x[C,D], Bin)
 
@objective(model, Min, 0) # Tenemos como objetivo minimizar a 0, porque en este problema nos importa que simplemente se resuelva el sudoku
 
@constraint(model, [i in C], sum(x[i,:]) == 1) # cada celda tiene un único digito y por tanto cada celda tendrá un dígito
 
@constraint(model, [f in 1:k, j in D], sum(x[i,j] for i in F[f]) == 1) # Cada configuración sólo puede tener una vez al digito j
 
println(model)

status = optimize!(model)
@show termination_status(model)
println("Total: ",objective_value(model))
 
# Imprimir el sudoku en formato 9x9
println("\nSolución de Sudoku:")
 
for i in 1:m
	for j in 1:n
		# Verificar cuál valor de j está asignado a la celda i
		if value(x[i,j]) > 0.5
			print("$j ") # Imprimir el valor j asignado a la celda i
		end
	end
 
	# Formato para cada fila: después de cada 9 celdas, pasar a la siguiente línea
	if i % 9 == 0
		println()
	end
end

---

Notas

• La restricción (2) compacta filas $F_r$, columnas $C_c$ y bloques $B_b$.
• Expansión alternativa:
  • Filas $$\sum _{j\in F_r}{x}_{ij}=1\forall i\in I,\forall r=1,\dots ,9$$
  • Columnas $$\sum _{j\in C_c}{x}_{ij}=1\forall i\in I,\forall c=1,\dots ,9$$
  • Bloques $$\sum _{j\in B_b}{x}_{ij}=1\forall i\in I,\forall b=1,\dots ,9$$

Problema de gestión de un almacén de una fábrica single-item uncapacitated lot-sizing problem.

Tengo una fábrica y me dedico a fabricar un producto.

$$\begin{array}{rl}t& =1,2,\dots ,n\\ d_t& =\text{demanda del dıˊa}t\\ c_t& =\text{costo de fabricar una unidad el dıˊa}t\\ f_t& =\text{costo fijo de fabricrar el dıˊa}t\\ h_t& =\text{costo de almacenar una unidad el dıˊa}t\end{array}$$

Modelo

Variables

$$\begin{array}{rl}{x}_t& =\text{cantidad de productos a fabricar el dıˊa}t\\ z_t& =\text{cantidad de productos a tener en el almacen}\\ y_t& =\{\begin{array}{ll}1,& \text{si se fabrica el dıˊa }t\\ 0,& \text{en otro caso}\end{array}\end{array}$$

Función Objetivo

$$\begin{array}{rl}& \min \sum _t{f}_t\cdot y_t+\sum _t{c}_t\cdot x_t+\sum _t{h}_t\cdot z_t\\ \text{oˊ}& \\ & \min \sum _t{f}_t\cdot y_t+c_t\cdot x_t+h_t\cdot z_t\end{array}$$

Restricción

$$\begin{array}{rlrl}{M}_t& =\sum _{k\ge t}{d}_k& & \\ x_t,z_t& \ge 0& & ,\forall t\\ x_t& \le M_t\cdot y_t& & ,\forall t\\ x_t+z_t& =d_t+z_{t+1}& & ,\forall t\\ y_t& \in \{0,1\}& & ,\forall t\\ z_1& =0& & \end{array}$$

Modelo 2

Variables

$$\begin{array}{rlrl}& W_{t,l}=\text{cantidad, a fabricar el dıˊa t para cubrir la demanda},& & \forall t\forall l:t\le l\\ & y_t\in \{0,1\},& & \forall t=1,\dots ,n\\ & x_t\le M_t{z}_t,z_t\in \{0,1\},& & \forall t=1,\dots ,n\end{array}$$

Función Objetivo

$$\min \sum _{t=1}^n{f}_t{y}_t+\sum _{t=1}^n\sum _{l=t}^n\left(c_t+\sum _{j=t}^{l-1}{h}_j\right)W_{t,l}$$

Restricciones

$$\begin{array}{rlrl}& \sum _{t=1}^l{W}_{t,l}=d_l,& & ,\forall l=1,\dots ,n\\ & W_{t,l}\le d_e\cdot y_t& & ,\forall t\\ & W_{t,l}\ge 0,& & ,\forall t\\ & y_t\in \{0,1\}& & ,\forall t\end{array}$$

Problema de Concentrados

Modelo

$$\begin{array}{rl}V& =\{1,\dots ,n\}\\ d& =[D_{ij}]\\ f& =[f_i]\\ c& =[C_{ij}]\\ \alpha & =\text{cliente-hub}\\ \beta & =\text{hub-cliente}\\ \delta & =\text{hub-hub}\end{array}$$

Variables

$$\begin{array}{rlrl}{Z}_{ik}& =\{\begin{array}{l}1siiak\\ 0\text{otro caso}\end{array}& & \forall i,k\in V\end{array}$$

Función Objetivo

$$\begin{array}{cc}\min & {\sum }_{k\in N}{f}_k{z}_{kk}+{\sum }_{i,k\in N}(\pi O_i+\delta D_i)c_{ik}{z}_{ik}+{\sum }_{i,j,k,m\in N}\alpha c_{km}{d}_{ij}{z}_{ik}{z}_{jm}\end{array}$$

Restricciones

$$\begin{array}{rlr}& \sum _{k\in N}{z}_{ik}=1& i\in N\\ & z_{ik}\le z_{kk}& i,k\in N\\ & z_{ik}\in \{0,1\}& i,k\in N\end{array}$$

Problema Redes

$$\begin{array}{rl}V& =\{\text{ }1,\dots ,n\}\\ C& =[c_{ij}]\end{array}$$