Gurobi学习笔记—矩阵变量及八皇后问题案例
本节将介绍Gurobi中的矩阵变量MVar，并且以Gurobi案例目录下的八皇后案例进行解读
矩阵变量MVar与tupledict有所区别。
矩阵变量Mvar是NumPy ndarray形式的变量，只能使用下标索引，通过Numpy的矩阵与MVar相乘得到线性/多项式矩阵表达式MLinExpr或MQuadExpr。
矩阵变量的创建
-
Model.addMVar() 常用
addMVar ( shape, lb=0.0, ub=GRB.INFINITY, obj=0.0, vtype=GRB.CONTINUOUS, name="" ) shape：矩阵向量的维度 lb, ub：分别为变量的上下限（可选） obj：变量在目标函数表达式中的系数（可选） vtype：变量类型（可选） x = model.addMVar(10) # 包含10个变量的一维矩阵变量 y = model.addMVar((3,4), vtype GRB.BINARY) # 3x4的0-1变量矩阵
矩阵变量的运算
Gurobi中的矩阵变量可以当做Numpy中的矩阵，对其进行运算以创建表达式，需要注意的是维数一定要兼容。例如表示如下式子：
x + 2 y + 3 z <= 4
x + y >= 1
x, y, z binary
可写作
# 一维矩阵变量
x = m.addMVar(shape=3, vtype=GRB.BINARY, name="x")
# 左端项系数矩阵
A = np.array([[1,2,3],[1,1,0]])
# 右端项
rhs = np.array([4.0, -1.0])
m.addConstr(A @ x <= rhs, name ="c")
矩阵变量支持切片操作，使用[],:选取矩阵中特定的元素，这一点与tupledict对象（即addVars()）的select()不同，后者采用*表示通配符运算
矩阵变量支持求和操作，但与tupledict变量不同。矩阵变量采用切片选取元素，后直接调用sum()函数
y = model.addMVar((3,4), vtype GRB.BINARY) # 3x4的0-1变量矩阵
y[:,1]#选取第一列元素
与tuplelist对象的对比
tupledict变量由model.addVars()或者multidict()函数创建，通过创建时使用的indices进行访问，同时具有select(), sum(), prod() 的功能筛选元素并快速构建表达式。
model.addVars(*indices)方式创建的对象，本质上是多种集合的笛卡尔乘积的结果
x = m.addVars(2,3, vtype=GRB.BINARY)
# 生成的元素是
x(0,0) x(0,1) x(0,2)
x(1,0) x(1,1) x(1,2)
# 三个组的笛卡尔积
y = m.addVars((1,2),(1,3),(2,3))
x(1,1,2) x(1,1,3) x(1,3,2) x(1,3,3)
x(2,1,2) x(2,1,3) x(2,3,2) x(2,3,3)
tupledict对象支持采用字符串类型创建索引（字符串作为key），并且索引可使用通配符(select方法)
注意：方括号索引时不能使用*
MVar仅能通过数字按行列索引
commodities = ['Pencils', 'Pens']
nodes = ['Detroit', 'Denver']
flow = m.addVars(commodities, nodes, obj=cost, name="flow")
flow.select('*','*')
flow[*,*] # 错误的引用方式
flow['pencil','Detroit']
flow['Pencils','Denver']
八皇后案例
该案例存在于Gurobi目录下案例文件夹中根目录examplespythonmatrix2.py
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。（摘自百度百科）
假设决策变量x(i,j)为0-1变量，变量为1代表在第i行第j列放置皇后，需满足下列条件：
（1） 每行只放置一个皇后
（2）每列只放置一个皇后
（3）每条正对角线只放一个皇后
（4）每个斜对角线只放一个皇后
约束3，4由生成器生成，在代码中可能一下子看不懂，本人以n=4为例，推了一下正对角线的计算，斜对角线同理
#!/usr/bin/env python3.7
# Copyright 2019, Gurobi Optimization, LLC
# This example uses the Python matrix API to formulate the n-queens
# problem; it maximizes the number queens placed on an n x n
# chessboard without threatening each other.
#
# This example demonstrates NumPy slicing.
import numpy as np
import scipy.sparse as sp
import gurobipy as gp
from gurobipy import GRB
# Size of the n x n chess board
n = 8
try:
# Create a new model
m = gp.Model("matrix2")
# Create a 2-D array of binary variables
# x[i,j]=1 means that a queen is placed at square (i,j)
x = m.addMVar((n, n), vtype=GRB.BINARY, name="x")
# Set objective - maximize number of queens
m.setObjective(x.sum(), GRB.MAXIMIZE)
# Add row and column constraints
# 为每一行、列添加约束
for i in range(n):
# At most one queen per row
# 每一行最多放置一个皇后
m.addConstr(x[i, :].sum() <= 1, name="row"+str(i))
# At most one queen per column
# 每一列最多放置一个皇后
m.addConstr(x[:, i].sum() <= 1, name="col"+str(i))
# Add diagonal constraints
# 添加对角线约束
for i in range(1, 2*n):
# At most one queen per diagonal
# 每个正对角线最多防止一个皇后
# 生成器生成对矩阵的切片索引
diagn = (range(max(0, i-n), min(n, i)), range(min(n, i)-1, max(0, i-n)-1, -1))
m.addConstr(x[diagn].sum() <= 1, name="diag"+str(i))
# At most one queen per anti-diagonal
# 每个斜对角线最多防止一个皇后
# 生成器生成对矩阵的切片索引
adiagn = (range(max(0, i-n), min(n, i)), range(max(0, n-i), min(n, 2*n-i)))
m.addConstr(x[adiagn].sum() <= 1, name="adiag"+str(i))
# Optimize model
# 开始优化模型
m.optimize()
print(x.X)
print('Queens placed: %g' % m.objVal)
except gp.GurobiError as e:
print('Error code ' + str(e.errno) + ": " + str(e))
except AttributeError:
print('Encountered an attribute error')