或工具在 Java 中设置具有多个索引的变量

Question

我正在尝试构建一个具有多个索引的变量，例如$x_{i,j}$

到目前为止，我在文档中找到了如下简单的变量设置：

MPVariable x = solver.makeIntVar(0.0, infinity, "x");

是否有文档显示这样的示例？

此外，是否可以使用 AMPL 来制定 OR 工具中的问题？

Answer 1

您只需为每对索引创建一个变量；即循环 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)]

完整工作示例：分配问题

考虑到这一点，让我们尝试创建一个完整的示例。 two-dimensional 整数变量矩阵建模的一个简单问题是 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。那么，objective 的值为 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。但事实上，由于约束矩阵是完全幺模的，我们实际上根本不必使用整数变量，可以只使用 real-valued $0 \leq x_{ij} \leq 1$.

此外，存在解决线性分配问题的有效算法；事实上，OR-Tools 本身捆绑了 CSA-Q 算法的 integer-valued 权重的实现，这在实践中运行良好。尽管如此，该解决方案适用于较小的问题实例，并有望作为如何使用 MPSolver 解决 non-trivial 问题的说明性示例。

或工具在 Java 中设置具有多个索引的变量

OR Tools setting a variable with multiple indices in Java

java

ampl

or-tools

integer-programming

完整工作示例：分配问题