for s in S:
    # 割り当てられたクラスを取得
    assigned_class = [x[s,c].value() for c in C if x[s,c].value()==1]

ですとassigned_classには1しか入らないので、割り当てられたクラスを取得したいのでしたら、

for s in S:
    # 割り当てられたクラスを取得
    assigned_class = [c for c in C if x[s,c].value()==1]

とする必要があるのではないでしょうか？

p.276 の 1 行目

$p1 \geq p2 \geq p3$

は不等号逆ではないかと思います。
(第1版第1刷)

ご確認頂けると幸いです。

課題

M1チップ搭載Macにおいて、第7章で用いるライブラリCVXOPTのインストールがうまくいかない。

調査内容

現状、FFTW、GLPK、GSLのインストールをした上で、cvxoptをソースからインストールすれば可能と報告を受けているが確認、調査中。

参考URL

cvxopt/cvxopt#78
https://cvxopt.org/install/index.html

第7章の冒頭で機械学習モデルについて少しだけ触れられていますが、最近は、機械学習の知識のある読者も増えていると思うので、機械学習モデルとの具体的な比較があると、より理解が深まるかもと思い、scikit-learn で簡単な線形モデルとの比較をおこなってみました。

書籍の改訂を計画されているとの事でしたので、「こういう内容もあると面白いかな」というアイデアとして提供させていただきます。あくまで、一読者としての提案ですので、書籍の内容にそぐわないものであれば、無視していただいて結構です m(_ _)m

具体的なコードは、こちらを参照ください。（「機械学習による予測」以降が新しく追加した内容です。）

ポイントとしては、

• 書籍のモデルの場合は、単調性や凸性に関する制約条件を明示的にモデルに取り入れることができている

• 機械学習モデルの場合は、これらの制約条件を「明示的」に取り入れるのは難しく、この例の場合は、次のような状況になる

  • Recency と Frequency の線形予測モデル：線形モデルなので単調増加という制約は自動的に満たされるが、モデルが単純すぎてデータにうまくフィットしない（平均二乗誤差が大きくなる）
  • Recency と Frequency の 2 次までの項を用いた線形予測モデル：よりデータにフィットした自然な結果が得られるが、単調増加という制約は満たされなくなってしまう。

というあたりで、いずれも「データとの二乗誤差を最小化する」という意味での最適化を行なっているものの、モデルの構成方法において、制約条件を明示的に取り入れられるかどうかという違いがある点がわかると面白い気がしています。

誤植というわけではないのですが、第５章で実装されているロジックについて気づいた点があったので共有させてください。書籍改訂時などの参考にしていただければ幸いです。

p.165 の is_OK() 関数

「ルート関係」のコメント以下の部分では、指定された荷物の配送先を（部分集合として）含むすべての経路の中から、移動時間（移動距離の合計）が最小のものを検索しています。ただ今回の問題設定では、「指定された荷物の配送先だけを通る経路」が最短時間になるのは自明なので、余計な訪問先を含む経路を含めて探索する理由がわからず、書籍を読んでいて少し混乱しました。（より一般的な問題設定では、あえて回り道をした方が時間が短くなる場合もあるとは思いますが、この点について、書籍内で一言説明があればよかったです。）

DataFrame を使わない実装による高速化

上記の探索をやめて、「指定された荷物の配送先だけを通る経路」を最初から選択する形で再実装してみました。この際、DataFrame で中間データを取り回すのをやめて、List, Dictionary だけを使うようにした所、実行速度がかなり高速化されました。（リンク先の実行結果に実行時間が記録されていますが、並列実行なしでも十分気軽に（？）試せる実行時間になっていると思います。（is_OK() 関数内での探索をやめた影響もあると思いますが、それよりは、DataFrame の検索のオーバーヘッドが削減された影響の方が大きいと想像しています。）

書籍の実装との結果のズレについて

上記の再実装による結果と書籍の実装の結果を比較すると、（理屈の上では一致するはずですが）一致しない部分がありました。原因を調べてみたところ、2地点間の距離を計算する際に、np.floor で小数点以下を切り捨てているために丸め誤差が生じて、三角不等式が成り立たない場合がおきているようでした。

t = np.array([[np.floor(np.linalg.norm(_K[k] - _K[l])) for k in K] for l in K])

再実装の最後にある「距離の丸め誤差について」で具体例を示していますが、4 - 5 よりも（間に 7 を挟んだ） 4 - 7 - 5 の方が移動時間が短くなっています。

このため、書籍の実装では、余計な訪問先を含む方が移動時間が短くなるケースを発見して、そちらの経路を採用することがあるようです。

https://github.com/ohmsha/PyOptBook/blob/main/2.tutorial/tutorial.ipynb

「⑧実装した数理最低聴かモデルのまとめ」ではなく、正しくは「⑧実装した数理最適化モデルのまとめ」です。
テキスト（第1版第2刷）には正しい文面で載っています。

指摘事項

P.60の要件(7)の数理モデリングの説明のところで、特定ペアの生徒は同一クラスに割り当てないという要件を以下のように数式で書かれていますが、

正しくは、以下ではないでしょうか？（第2項がxではなくsになっている）

背景

数理最適化ソルバーSCIPが、2022年11月4日からApache 2.0ライセンスとなり、商用での利用が可能となった。

License
Since November 4, SCIP is licensed under the Apache 2.0 License.
https://www.scipopt.org/index.php#license

モデリング言語PuLPからソルバーSCIPの呼び出しについて

以下のようにPuLPからSCIPを呼び出して実行可能であることを確認した。

ファイル（test.py）

import pulp

problem = pulp.LpProblem('LP', pulp.LpMaximize)

x = pulp.LpVariable('x', cat='Integer')
y = pulp.LpVariable('y', cat='Integer')

problem += 1 * x + 3 * y <= 30
problem += 2 * x + 1 * y <= 40
problem += x >= 0
problem += y >= 0
problem.objective = x + 2 * y

solver = pulp.SCIP_CMD()
status = problem.solve(solver)

print('Status:', pulp.LpStatus[status])
print('x=', x.value(), 'y=', y.value(), 'obj=', problem.objective.value())

実行

$python test.py

出力

SCIP version 8.0.2 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: Soplex 6.0.2] [GitHash: 5f0473c4fb]
Copyright (C) 2002-2022 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)

External libraries: 
  Readline EditLine w  GNU library for command line editing (gnu.org/s/readline)
  Soplex 6.0.2         Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 45f6420d]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.2.11          General purpose compression library by J. Gailly and M. Adler (zlib.net)
  GMP 6.2.1            GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  AMPL/MP 4e2d45c4     AMPL .nl file reader library (github.com/ampl/mp)

user parameter file <scip.set> not found - using default parameters


read problem </var/folders/5f/6t2pl2pd5l53yt6l2ms05lww0000gn/T/2c5b92d0c2a94cd7970564ff31af6f16-pulp.lp>
============

original problem has 2 variables (0 bin, 2 int, 0 impl, 0 cont) and 4 constraints

feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
(round 1, fast)       0 del vars, 2 del conss, 0 add conss, 2 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 2, fast)       0 del vars, 2 del conss, 0 add conss, 5 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 3, exhaustive) 0 del vars, 2 del conss, 0 add conss, 5 chg bounds, 0 chg sides, 0 chg coeffs, 2 upgd conss, 0 impls, 0 clqs
   Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).
presolving (4 rounds: 4 fast, 2 medium, 2 exhaustive):
 0 deleted vars, 2 deleted constraints, 0 added constraints, 5 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolved problem has 2 variables (0 bin, 2 int, 0 impl, 0 cont) and 2 constraints
      2 constraints of type <varbound>
transformed objective value is always integral (scale: 1)
Presolving Time: 0.00
transformed 1/1 original solutions to the transformed problem space

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
p 0.0s|     1 |     0 |     0 |     - | vbounds|   0 |   2 |   2 |   2 |   0 |  0 |   0 |   0 | 4.000000e+01 | 2.000000e+01 | 100.00%| unknown
p 0.0s|     1 |     0 |     0 |     - | vbounds|   0 |   2 |   2 |   2 |   0 |  0 |   3 |   0 | 4.000000e+01 | 2.100000e+01 |  90.48%| unknown
* 0.0s|     1 |     0 |     2 |     - |    LP  |   0 |   2 |   2 |   2 |   0 |  0 |   4 |   0 | 2.600000e+01 | 2.600000e+01 |   0.00%| unknown
  0.0s|     1 |     0 |     2 |     - |   580k |   0 |   2 |   2 |   2 |   0 |  0 |   4 |   0 | 2.600000e+01 | 2.600000e+01 |   0.00%| unknown

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes      : 1
Primal Bound       : +2.60000000000000e+01 (4 solutions)
Dual Bound         : +2.60000000000000e+01
Gap                : 0.00 %


written solution information to file </var/folders/5f/6t2pl2pd5l53yt6l2ms05lww0000gn/T/2c5b92d0c2a94cd7970564ff31af6f16-pulp.sol>


Status: Optimal
x= 18.0 y= 4.0 obj= 26.0

モデリング言語Python-MIPからソルバーSCIPの呼び出しについて

python-mipはscipに未対応（2022年11月5日）。
しかしながらコードに将来的にSCIP対応する計画があるとの記述がされている。
https://github.com/coin-or/python-mip/blob/master/mip/constants.py#L32

SCIP = "SCIP"  # we plan to support SCIP in the future

なお、Python-MIPの場合、次のコードで実行することになる想定。

import mip

problem = mip.Model(solver_name=mip.SCIP)

x = problem.add_var(var_type='I')
y = problem.add_var(var_type='I')

problem += 1 * x + 3 * y <= 30
problem += 2 * x + 1 * y <= 40
problem.objective = mip.maximize(x + 2 * y)

problem.optimize()

print('Status:', problem.status)
print('x=', x.x, 'y=', y.x, 'obj=', problem.objective.x)

検討事項

本書のコードを将来的にSCIP対応するかどうかだったり、本レポジトリでSCIP対応コードを公開するかどうか検討する。

@jiro-iwanaga

第7章 商品推薦のための興味のスコアリング

第1版 第1刷の誤植についてご報告します.

(1) 誤植

p. 241 図中の文言
誤: 閲覧は同じ日だけれど item2 のほうが多く見ているので ...
正: 閲覧は同じ日だけれど item3 のほうが多く見ているので ...

8月3日に item 3 と item4 を閲覧した回数を比較しているため, item2 は無関係です.

(2) 誤植

p. 247 上から10行目
誤: 同様に、商品IDが item3 の商品は、頻度 (freq) が3、
正: 同様に、商品IDが item3 の商品は、頻度 (freq) が2、

頻度 (freq) は8月1日から8月3日までに閲覧した総数であるので, 8月4日の閲覧数 (1 pv) を含めない(加算しない)と思います.

なお, p. 248 以降は目を通しておりません.

ご検討いただけると幸いです. よろしくお願いします.

@jiro-iwanaga

何気なく推薦図書のページを見ていたら, また見つけてしまいました.

(1) 誤植

p. 297 下から2行目

誤: 齋藤正彦『基礎数学 1 線形代数入門』東京大学出版会 (1966)
正: 齋藤正彦『基礎数学 1 線型代数入門』東京大学出版会 (1966)

齋藤正彦先生の著書では, 「線形」ではなく「線型」と表記されています.

(2) 誤植

p. 297 下から1行目

誤: 齋藤正彦『基礎数学 4 線形代数演習』東京大学出版会 (1985)
正: 齋藤正彦『基礎数学 4 線型代数演習』東京大学出版会 (1985)

ご検討いただけますと幸いです. よろしくお願いします.

In [51] 4行目のx = {}はxsm = {}ではないでしょうか？
xsmが宣言済みのため動作に影響はないですが。

はじめまして。書籍、楽しく読ませて頂いてます。

「第5章：配送計画」の改善後の定式化について質問があります。この定式化だとdeliv_countが0以上であればどのような値でも取れるので、同じ注文（request）を何度も運んでしまうような気がするのですが、この理解で正しいでしょうか？試しに、Jupyter Notebookのコード（5.routing/routing.ipynb）を動かしてdeliv_countの値を確認してみると、幾つかの注文に対してdeliv_countが2以上になっているようです。

また、deliv_countを1以下に抑えるような制約を追加すると、pulp.LpStatus[prob.status]がOptimalからInfeasibleになってしまい、答えも直感に反するものが出てきてしまいました。

もし、deliv_countが2以上になるのが想定内だとすると、ある程度の解を出しておいて、配送済みの注文は後処理で取り除くようにして運用するというのが一つの手となるのでしょうか？

とんちんかんな質問かもしれないのですが、周りに頼れる人もいないので、ここで質問させていただきました。

P.S. 数理最適化は初心者なのですが、この書籍だと順を追って学んでゆけるので、非常に助かっています。ありがとうございます。

概要

本書のP8にあるナップサック問題の例で「遠足のおやつは200円まで」と記述したが、大学の先生から「300円のほうが普通だ」という指摘が入った。調査したところ「300円」の意見（声？）が大きいようだ。ただし、最近は上限がなくなりつつあるという情報もある。正誤表に載せるかどうか決めたい。

【参考】遠足へ持っていくおやつの値段に上限が無くなった⁉︎その訳とは。

論点

安易に書籍の内容を変更してはならないというスタンスは保ちつつ、以下の観点で修正を議論する余地がある。

• 本修正により文脈上の不整合は起きない
• 金額は読者層が小学生であったときの金額を採用したい
• 本書のスタンスは実務書であり、可能な限り身近に感じられる記述を心がけてきた。そのため、読者が遠足のおやつは「200円」までという記述よりも「300円」のほうしっくりくるのであれば「300円」のほうが適切である。
• 著者が小学生の頃は「200円」であった（地域：北海道札幌市手稲区 / 消費税：3%）。

備考

• 参考リンク：Twitter
• Twitter上でのコメント：300円・500円・200円・400円・250円

はじめまして.

第1版 第1刷 を読解中です.
まだすべてを読めていないのですが, 誤植と思われる部分を以下に挙げます.

• p. 2 上から1行目

  • 誤: 扱う扱う
  • 正: 扱う

• 表記ゆれ

  • 本文 (p. 17 問題と解答, p. 21 上から2行目) では: 利得
  • 図 (p. 17), 本文 (p. 20 最下行) では: 利益

• p. 18 上から3-4行目

  • 誤: 線形計画問題と連立一次方程式と異なる箇所として
  • 正: 線形計画問題が連立一次方程式と異なる箇所として

• p. 27 下から3行目

  • 誤: それぞれ require_df, gain_df, stock_df から取得します。
  • 正: それぞれ stock_df, require_df, gain_df から取得します。

• p. 38 2.4の上から2行目

  • 誤: 二次方程式と線形計画問題の実装はよく似ており、制約式や目的関数の設定に違いがあること
  • 正: 連立一次方程式と線形計画問題の実装はよく似ているが、制約式や目的関数の設定には違いがあること

• p. 296 上から7行目

  • 誤: 今日から使える! 組み合わせ最適化 離散問題ガイドブック
  • 正: 今日から使える! 組合せ最適化 離散問題ガイドブック

よろしくお願いします.

@jiro-iwanaga @nnnnishi

第4章 割引クーポンキャンペーンの効果最大化

第1版 第1刷の誤植や表記ゆれについてご報告します.

(1) 誤植

p. 91 下から2行目
誤: 最大する
正: 最大化する

(2) 表記のゆれ

ゆれ 1: 利用回数, 来店回数
ゆれ 2: 組, 組み合わせ, 組合せ

p. 92 上から2-3行目: 年齢区分と昨年度利用回数区分
p. 92 上から5-6行目: 年齢区分と昨年度利用回数区分の組
p. 94 上から14-15行目: 年齢区分と昨年度利用回数区分の組み合わせ
p. 97 いちばん下の表 および 本文下から2行目: 年齢区分と昨年度来店回数区分
p. 98 下から8行目: 年齢区分と昨年度来店回数区分の組合せ

ゆれ 1 について. 目視で読む限りは, p. 98 以降では, 「来店回数」に統一されているようです.

(3) 定数とされている量

p. 111 下から2行目
誤: 定数: 会員 $i (\in I)$ がセグメント $s (\in S)$ に属する場合 1、 そうでない場合に 0 となる定数
正: 変数: 会員 $i (\in I)$ がセグメント $s (\in S)$ に属する場合に 1、 そうでない場合に 0 となる変数

コメント 1: 「0-1 変数」という用語からもわかるように, Z_{is} の値は変わるため定数とは呼べないのではないでしょうか. Z_{is} を変数と呼ぶことに(決定変数とは区別したいという理由で)抵抗があるようでしたら, 久保幹雄先生の流儀にのっとり, 「パラメータ」と呼ぶのはいかがでしょうか. いずれにしろ, 変更する場合は, p. 112 以降に現れる「定数」という用語にも影響するかと思います.

(参考)
https://orsj.org/wp-content/corsj/or61-10/or61_10_674.pdf

コメント 2: p. 105 の破線の枠内の記述にそろえるならば, 「場合」のうしろに助詞「に」が必要です.

同じことが, P_{im}, N_s, C_m にも当てはまり, 添字によって値が変わるため, これらは定数ではありません.

(4) 表記のゆれ

p. 111

本文では「会員」と書かれているのに対して, コードのコメント文では「顧客」に変わっています.
モデリング 2 (p. 122) でも, 「会員の予算消費期待値」と表記されています.

現状: # (4) 顧客の消費する費用の期待値の合計は100万円以下
こうでは? : # (4) 会員の消費する費用の期待値の合計は100万円以下

(5) 表記のゆれ

p. 112

本文では, 「会員数」と書かれているのに対して, コードのコメント文では「顧客数」に変わっています.

現状: # 各セグメントとそのセグメントに属する顧客数を対応させる辞書の作成
こうでは?: # 各セグメントとそのセグメントに属する会員数を対応させる辞書の作成

(6) 誤植

p. 113 下から6行目 (コード中のコメント文)

誤: ...... の 10% 以上送付
正: ...... の 10% 以上に送付

助詞「に」が抜けています. 本文 (p. 111) では, 正しく「10% 以上に送付」と書かれています.

(7) 誤植

p. 119 上から1行目

誤: (1) 各会員に対してどのパターンのダイレクトメールを送付するかを決定
正: (1) 各セグメントに対してどのパターンのダイレクトメールを送付するかを決定

(8) 誤植

p. 119 コードの中のコメント文

誤: # (1) 各会員に対してどのパターンのダイレクトメールを送付するかを決定
正: # (1) 各セグメントに対してどのパターンのダイレクトメールを送付するかを決定

(9) 誤植

これは3か所あります.

p. 120 上から3行目
p. 120 上から5行目
p. 120 上から11行目 (コード中のコメント文)

誤: (2) 各会員に対して送付するダイレクトメールはいずれか1パターン
正: (2) 各セグメントに対して送付するダイレクトメールはいずれか1パターン

(10) 誤植

これは3か所あります.

p. 122 上から5行目 (本文)
p. 122 8行目 (破線の囲み枠内)
p. 122 13行目 (コード中のコメント文)

誤: ...... の 10% 以上送付
正: ...... の 10% 以上に送付

上記の(6)と同様に, 助詞「に」が抜けています.

(11) 誤植

p. 127 下から9行目
誤: 効果がなく無駄ある
正: 効果がなく無駄である

(12) 誤植

p. 128 上から4行目と6行目

誤:
要件 (1) ...... 各会員に対してどのダイレクトメールを送付するかを決定
要件 (2) 各会員に対して送付するダイレクトメールはいずれか1パターン

正:
要件 (1) ...... 各セグメントに対してどのダイレクトメールを送付するかを決定
要件 (2) 各セグメントに対して送付するダイレクトメールはいずれか1パターン

(13) 誤植

p. 129 上から4行目

誤: 要件 (1) ...... 各会員に対して
正: 要件 (1) ...... 各セグメントに対して

(14) 誤植

p. 129 上から6-7行目

誤: さきほどまでの各会員に
正: さきほどまでの各セグメントに

(15) 誤植

これは2か所あります.

p. 129 コード中 (下側の背景が黒色エリア) のコメント文
p. 133 コード中のコメント文

誤: ... 下限値と各会員に対して ...
正: ... 下限値と各セグメントに対して ...

(16) 誤植

これは3か所あります.

p. 129 コード中 (下側の背景が黒色エリア) のコメント文
p. 133 コード中のコメント文
p. 136 コード中のコメント文

誤: # 会員に対してどのダイレクトメールを送付するか
正: # セグメントに対してどのダイレクトメールを送付するか

(17) 誤植

これは3か所あります.

p. 131 上から1行目 (コード中のコメント文)
p. 134 上から2行目 (コード中のコメント文)
p. 136 コード中のコメント文

誤: # (2) 各会員に対して ...
正: # (2) 各セグメントに対して ...

(18) 表記のゆれ

p. 136 コード中のコメント文

現状: # (3) 割引券付与による来客増加数を最大化
こうでは?: # (3) クーポン付与による来客増加数を最大化

それまで一貫して「クーポン」と表記されていましたが, ここでは「割引券」と書かれています.

(19) 誤植

p. 136 コード中のコメント文

誤: # (1) 各セグメントへのそれぞれパターンのダイレクトメールの送付率の下限値と各会員に対してどのダイレクトメールを送付するかを決定
正: (コメント自体が不要?)

現状では上のように「送付率の下限値」を決定すると書かれていますが, 本文にあるようにここでは下限は 10% に固定されていて, 計算で求めるわけではないですよね. となると, このコメント自体が不要ではないかと思いました.

(20) 表記のゆれ および 複数形

p. 138 上から3行目 (コード)

現状: label='Incremental visitor'
修正案: label='Incremental Customers'

p. 138 上から12行目 (コード)

現状: ax1.set_ylabel('Incremental visitor')
修正案: ax1.set_ylabel('Incremental Customers')

誤りとも思わず重要度は低いですが, p. 109 までは会員のことを指すのに, customers.csv や customer_id と表記されています. もしこの表記に合わせるのであれば, 'Incremental customers' と書くのがより適切かと思いました.

長くなりましたが, ご検討いただけると幸いです. よろしくお願いします.