- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在尝试形成一个具有多个索引的变量,例如$x_{i,j}$
到目前为止,我在文档中发现了如下简单的变量设置:
MPVariable x = solver.makeIntVar(0.0, infinity, "x");
是否有任何文档显示这样的示例?
此外,是否可以使用 AMPL 来表述 OR 工具中的问题?
最佳答案
您只需为每对索引创建一个变量即可;即循环i
和j
并创建一个 ArrayList<ArrayList<MPVariable>>
;即执行类似以下操作,其中 ni
和nj
表示索引 i
的值的数量和j
分别是:
var x = new ArrayList<ArrayList<MPVariable>>();
for (int i = 0; i < ni; i++) {
var inner = new ArrayList<MPVariable>();
for (int j = 0; j < nj; j++) {
var xij = solver.makeIntVar(0.0, infinity, String.format("x%d%d", i, j));
inner.add(xij);
}
x.add(inner);
}
此时可以通过x.get(i).get(j)
访问$x_{i,j}$ .
官方文档有这方面的示例,尽管是针对 CP 求解器;参见例如the solution to the N-queens problem 。此处的示例使用 Python API,但您可以将其转换为 Java;作为引用,上述嵌套循环在 Python 中如下所示:
x = [[solver.IntVar(0.0, infinity, f'x{i}{j}') for j in range(nj)] for i in range(ni)]
考虑到这一点,让我们尝试创建一个完整的示例。由整数变量的二维矩阵建模的一个简单问题是 linear assignment problem 。最简单的形式是,我们得到一个权重 $(w_{ij})_{ij}$ 的实数方阵,并尝试最小化 $\sum_{ij} w_{ij} x_{ij}$,其中每个 $x_ {ij}$ 为 0 或 1,其中对于每个 $i$,恰好有一个 $x_{ij}$ 为 1,同样,对于每个 $j$,恰好 $x_{ij}$ 为 1。
在这里,让我们创建一个 5x5 实例,其中 $w_{ij} = (i+1)(j+1)$。我们很容易验证,在这种情况下,最佳解决方案是让 $x_{04} = x_{13} = x_{22} = x_{31} = x_{40} = 1$,并让 $的所有其他值x_{ij}$ 为 0。则目标值为 5 + 8 + 9 + 8 + 5 = 35。
以下是解决此问题并打印结果的完整程序:
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
import java.util.ArrayList;
public class LinearAssignment {
public static void main(String[] args) {
System.loadLibrary("jniortools");
var solver = new MPSolver(
"LinearAssignmentProblem", MPSolver.OptimizationProblemType.valueOf("CBC_MIXED_INTEGER_PROGRAMMING"));
// Define the variables and the objective function
var x = new ArrayList<ArrayList<MPVariable>>();
var objective = solver.objective();
int n = 5;
for (int i = 0; i < n; i++) {
var inner = new ArrayList<MPVariable>();
for (int j = 0; j < n; j++) {
var xij = solver.makeBoolVar(String.format("x%d%d", i, j));
objective.setCoefficient(xij, (i+1)*(j+1));
inner.add(xij);
}
x.add(inner);
}
// Add the constraint that sum_j x_{ij} = 1 for every i.
for (int i = 0; i < n; i++) {
var ci = solver.makeConstraint(1, 1);
for (int j = 0; j < n; j++) ci.setCoefficient(x.get(i).get(j), 1);
}
// Add the constraint that sum_i x_{ij} = 1 for every j.
for (int i = 0; j < n; j++) {
var cj = solver.makeConstraint(1, 1);
for (int i = 0; i < n; i++) cj.setCoefficient(x.get(i).get(j), 1);
}
// Run the solver
solver.solve();
// Print the results
System.out.println("Objective at minimum = " + solver.objective().value());
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
System.out.print(String.format("x%d%d = %d, ", i, j, (int) x.get(i).get(j).solutionValue()));
System.out.println();
}
}
}
输出:
Objective at minimum = 35.0
x00 = 0, x01 = 0, x02 = 0, x03 = 0, x04 = 1,
x10 = 0, x11 = 0, x12 = 0, x13 = 1, x14 = 0,
x20 = 0, x21 = 0, x22 = 1, x23 = 0, x24 = 0,
x30 = 0, x31 = 1, x32 = 0, x33 = 0, x34 = 0,
x40 = 1, x41 = 0, x42 = 0, x43 = 0, x44 = 0,
需要注意的是,这里的解决方案主要是说明性的,这个问题实际上可以稍微简化一下:由于 $x_{ij}$ 要么是 0 要么是 1,我们可以使用 makeBoolVar
而不是makeIntVar
。但事实上,由于约束矩阵是完全幺模的,我们实际上根本不需要使用整数变量,而可以只使用实值 $0\leq x_{ij}\leq 1$。
此外,存在解决线性分配问题的有效算法;事实上,OR-Tools 本身捆绑了整数值权重的 CSA-Q 算法的实现,该算法在实践中效果很好。尽管如此,该解决方案对于较小的问题实例来说还是不错的,并希望能够作为如何使用 MPSolver
的说明性示例。对于不平凡的问题。
关于java - 在 Java 中设置具有多个索引的变量的 OR 工具,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57028467/
我是一名优秀的程序员,十分优秀!