Programació en sancers

Archiu:IP polytope with LP relaxation.svg

Programació en sancers

Un problema de programació en sancers és un programa d'optimisació o factibilidad matemàtica en el qual algunes o totes les variables tenen que ser sanceres. En molts escenaris el terme es referix a programació llineal en sancers (PLE), en el qual la funció objectiu i les restriccions (aparte de les restriccions sanceres) són llineals.

La programació en sancers és NP-dur. Un cas especial, la programació llineal en sancers 0-1, en el qual les incògnites són binarias, és un dels 21 problemes NP-complet de Karp.

Forma estàndar i canònica per als PLÉs

Un programa llineal en sancers en forma canònica s'expressa com:

$\begin{array}{cccc}& \text{maximizar}& & {𝐜}^{\mathrm{T}}𝐱\\ & \text{sujeto a}& & A𝐱\le 𝐛,\\ & & & 𝐱\ge \mathrm{𝟎},\\ & \text{y}& & 𝐱\in \mathbb{Z},\end{array}$,

i un PLE en forma estàndar s'expressa com

$\begin{array}{cccc}& \text{maximizar}& & {𝐜}^{\mathrm{T}}𝐱\\ & \text{sujeto a}& & A𝐱+𝐬=𝐛,\\ & & & 𝐬\ge \mathrm{𝟎},\\ & \text{y}& & 𝐱\in \mathbb{Z},\end{array}$

a on $𝐜,𝐛$ són vectores i $A$ és una matriu de valors sancers. Note que similar als programes llineals, els PLÉs que no estan en forma estàndar poden ser convertits a forma estàndar eliminant les desigualtats i introduint variables artificials ($𝐬$) i reemplaçant les variables que no estan restringides en signe en la diferència de dos variables restringides en signe

Eixemple

Archiu:Caps block 11 polytope with caps block 12 relaxation.png

IP polytope with LP relaxation

L'image a la dreta mostra el següent problema.

$\begin{array}{cc}\max & y\\ -x+y& \le 1\\ 3x+2y& \le 12\\ 2x+3y& \le 12\\ x,y& \ge 0\\ x,y& \in \mathbb{Z}\end{array}$

Els punts sancers factibles es mostren en roig, i les llínees roges discontínues delimiten la regió convexa, la qual és el poliedre més chicotet que conté tots eixos punts. Les llínees de blava, junt en l'eix de coordenades definixen el poliedre de la relaixació de el PL, el qual està donat per les desigualtats sense la restricció de sancera. La meta de l'optimisació és moure la llínea de punts negres tan dalt com es puga mentres que esta seguixca tocant el poliedre. Les solucions òptimes del problema sancer són els punts $(1,2)$ i $(2,2)$ els quals donen un valor de la funció objectiu de 2. L'òptim únic de la relaixació és $(1.8,2.8)$ en un valor de la funció objectiu de 2.8. Note que si la solució de la relaixació és redonejada al sancer més propenc, esta no és factible per a el PLE.