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

到目前为止,我在文档中发现了如下所示的简单变量设置:

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


是否有任何文档显示此类示例?

此外,是否可以将AMPL用于OR工具中的问题表述?

最佳答案

您只需为每对索引创建一个变量;即遍历ij并创建ArrayList<ArrayList<MPVariable>>;即执行以下操作,其中ninj分别表示索引ij的值数量:

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用于非平凡的问题。

10-02 23:50