contratista de intervalo

Construcción matemática

En matemáticas , un contratista de intervalo (o contratista para abreviar) ^[1] asociado a un conjunto es un operador que se asocia a un hiperrectángulo en otra caja de tal que siempre se satisfacen las dos propiedades siguientes: ${\displaystyle X}$ ${\displaystyle C}$ ${\displaystyle [x]}$ ${\displaystyle {\mathbf {R}}^{n}}$ ${\displaystyle C([x])}$ ${\displaystyle {\mathbf {R}}^{n}}$

• ${\displaystyle C([x])\subset [x]}$(propiedad del contrato)

• ${\displaystyle C([x])\cap X=[x]\cap X}$(propiedad de integridad)

Un contratista asociado a una restricción (como una ecuación o una desigualdad ) es un contratista asociado al conjunto de todos los que satisfacen la restricción. Los contratistas permiten mejorar la eficiencia de los algoritmos de rama y límite utilizados clásicamente en el análisis de intervalos . ${\displaystyle X}$ ${\displaystyle x}$

Propiedades de los contratistas

Un contratista C es monótono si tenemos . ${\displaystyle [x]\subset [y]\Rightarrow C([x])\subset C([y])}$

Es mínimo si para todas las cajas [ x ] tenemos , donde [ A ] es el casco de intervalo del conjunto A , es decir, la caja más pequeña que encierra A . ${\displaystyle C([x])=[[x]\cap X]}$

El contratista C es delgado si para todos los puntos x , donde { x } denota el cuadro degenerado que encierra x como un solo punto. ${\displaystyle C(\{x\})=\{x\}\cap X}$

El contratista C es idempotente si para todas las cajas [ x ], tenemos ${\displaystyle C\circ C([x])=C([x]).}$

El contratista C es convergente si para todas las secuencias [ x ]( k ) de cajas que contienen x , tenemos ${\displaystyle [x](k)\rightarrow x\implies C([x](k))\rightarrow \{x\}\cap X.}$

Ilustración

La Figura 1 representa el conjunto X pintado de gris y algunas cajas, algunas de ellas degeneradas (es decir, corresponden a singletons). La figura 2 representa estas cajas después de la contracción . Tenga en cuenta que el contratista no ha eliminado ningún punto de X. El contratista es mínimo para la caja cian pero pesimista para la verde. Todos los cuadros azules degenerados se contraen al cuadro vacío . La caja magenta y la caja roja no se pueden contratar.

Figura 1: Cajas antes de la contracción

Figura 2: Cajas después de la contracción

Álgebra del contratista

Algunas operaciones se pueden realizar en contratistas para construir contratistas más complejos. ^[2] La intersección , la unión , la composición y la repetición se definen de la siguiente manera.

${\displaystyle (C_{1}\cap C_{2})([x])=C_{1}([x])\cap C_{2}([x])}$

${\displaystyle (C_{1}\cup C_{2})([x])=[C_{1}([x])\cup C_{2}([x])]}$

${\displaystyle (C_{1}\circ C_{2})([x])=C_{1}(C_{2}([x]))}$

${\displaystyle C^{\infty }([x])=C\circ C\circ C\circ \cdots \circ C([x])}$

Contratistas de la construcción

Existen diferentes formas de construir contratistas asociados a ecuaciones y desigualdades, digamos, f ( x ) en [ y ]. La mayoría de ellos se basan en la aritmética de intervalos. Uno de los más eficientes y simples es el contratista directo/inverso (también llamado HC4-revise). ^{[3] [4]}

El principio es evaluar f ( x ) usando aritmética de intervalos (este es el paso adelante). El intervalo resultante se cruza con [ y ]. Luego se realiza una evaluación hacia atrás de f ( x ) para contraer los intervalos para x _i (este es el paso hacia atrás). Ahora ilustraremos el principio con un ejemplo sencillo.

Considere la restricción. Podemos evaluar la función f ( x ) introduciendo las dos variables intermedias a y b , de la siguiente manera ${\displaystyle (x_{1}+x_{2})\cdot x_{3}\in [1,2].}$

${\displaystyle a=x_{1}+x_{2}}$

${\displaystyle b=a\cdot x_{3}}$

Las dos restricciones anteriores se denominan restricciones directas . Obtenemos las restricciones hacia atrás tomando cada restricción hacia adelante en orden inverso y aislando cada variable en el lado derecho. Obtenemos

${\displaystyle x_{3}={\frac {b}{a}}}$

${\displaystyle a={\frac {b}{x_{3}}}}$

${\displaystyle x_{1}=a-x_{2}}$

${\displaystyle x_{2}=a-x_{1}}$

El contratista hacia adelante/hacia atrás resultante se obtiene evaluando las restricciones hacia adelante y hacia atrás mediante el análisis de intervalos . ${\displaystyle C([x_{1}],[x_{2}],[x_{3}])}$

${\displaystyle [a]=[x_{1}]+[x_{2}]}$

${\displaystyle [b]=[a]\cdot [x_{3}]}$

${\displaystyle [b]=[b]\cap [1,2]}$

${\displaystyle [x_{3}]=[x_{3}]\ \cap \ {\frac {[b]}{[a]}}}$

${\displaystyle [a]=[a]\cap {\frac {[b]}{[x_{3}]}}}$

${\displaystyle [x_{1}]=[x_{1}]\ \cap \ \ [a]-[x_{2}]}$

${\displaystyle [x_{2}]=[x_{2}]\ \cap \ \ [a]-[x_{1}]}$

Referencias

1. Jaulín, Luc; Kieffer, Michel; Didrit, Olivier; Walter, Eric (2001). Análisis de intervalos aplicado . Berlín: Springer. ISBN 1-85233-219-0.
2. Chabert, G.; Jaulín, L. (2009). «Programación de contratistas» (PDF) . Inteligencia artificial . 173 (11): 1079-1100. doi : 10.1016/j.artint.2009.03.002 .
3. Messine, F. (1997). Método de optimización global basado en el análisis de intervalos para la resolución de problemas con restricciones. Thèse de doctorat, Institut National Polytechnique de Toulouse.
4. Benhamou, F.; Goualard, F.; Granvilliers, L.; Puget, JF (1999). Revisión de la coherencia del casco y la caja (PDF) . En Actas de la conferencia internacional de 1999 sobre programación lógica.