Tengo un programa lineal entero (ILP) con algunas variables que están destinadas a representar valores booleanos. Las están restringidas a ser enteros y a contener 0 o 1 ( ).x i 0 ≤ x i ≤ 1xixix_ixixix_i0≤xi≤10≤xi≤10 \le x_i \le 1 Quiero expresar operaciones booleanas en estas variables con valor...
Hay nnn contenedores mmm tipo de bolas. El iii th bin tiene etiquetas ai,jai,ja_{i,j} para 1≤j≤m1≤j≤m1\leq j\leq m , es el número esperado de bolas de tipo jjj . Comienzas con bjbjb_j bolas de tipo jjj . Cada bola de tipo jjj tiene peso wjwjw_j , y desea colocar las bolas en los contenedores de...
Entonces, como se sabe, el problema de decisión 0-1 de ILP es NP-completo. Mostrar que está en NP es fácil, y la reducción original fue de SAT; desde entonces, se ha demostrado que muchos otros problemas de NP-Complete tienen formulaciones de ILP (que funcionan como reducciones de esos problemas a...
Me pregunto, ¿cuál es el algoritmo más conocido, en términos de notación Big- , para resolver la programación lineal entera?OOO Sé que el problema es completo, por lo que no espero nada polinomial. Y sé que hay muchas heurísticas y otras que se usan en aplicaciones prácticas como CPLEX, pero estoy...
Según tengo entendido, el problema de asignación está en P ya que el algoritmo húngaro puede resolverlo en tiempo polinómico - O (n 3 ). También entiendo que el problema de asignación es un problema de programación lineal de enteros , pero la página de Wikipedia dice que esto es NP-Hard. Para mí,...
Quiero expresar la siguiente restricción, en un programa lineal entero: y={01if x=0if x≠0.y={0if x=01if x≠0.y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases} Ya tengo las variables enteras y me prometieron que . ¿Cómo puedo expresar la restricción anterior, en una forma...
Me dan un conjunto A≜{1,…,k}A≜{1,…,k}A\triangleq\{1,\ldots,k\} , un número entero s⩽ks⩽ks\leqslant k y números enteros no negativos aijaija_{ij} . Mi problema es encontrar sss subconjuntos disjuntos SjSjS_j de {1,…,k}{1,…,k}\{1,\ldots,k\} modo que: ⋃sj=1Sj=A⋃j=1sSj=A\bigcup_{j=1}^s S_j=A ;...
Dado un programa entero (binario) de la forma:0,10,10,1 mins.t.f(x)Ax=bxi≥0xi∈{0,1}∀i∀iminf(x)s.t.Ax=bxi≥0∀ixi∈{0,1}∀i \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} & \quad \forall i \end{array} Tenga en cuenta que el...
Asumiendo yyy es una variable booleana en un programa ILP (es decir y∈Zy∈Zy \in Z, S t 0<=y<=10<=y<=10