PuLPでの変数固定

  • 投稿日:
  • by

PuLPで変数の値を固定するには,lowBoundとupBoundに固定したい値を代入すればよい.例を次に示す.

prob=LpProblem('LP',LpMinimize)
x1=LpVariable('x1',0,3)
x2=LpVariable('x2',0,2)
prob += x1+x2
prob += x1+x2<=4
x1.lowBound=0
x1.upBound=0

PuLPでのcolumnwise modeling

  • 投稿日:
  • by

PuLPでは,列(column,変数)主体のモデリングの方法がある.

問題を定義して

prob=LpProblem("LP",LpMinimize)

制約式を定義するには,LpConstraintVar()を用いる.まずは目的関数を定義する.

obj=LpConstraintVar("Obj")
prob.setObjective(obj)

リストca=['a','b','c']を用意して,その各要素に一つずつ制約式を定義する.

constraints={}
for c in ca:
    constraints[c]=LpConstraintVar(c,LpConstraintEQ,1)
    prob+=constraint[c]

これにより,制約式が3つ定義される.LpConstraintVar()の第二引数LpConstraintEQはこの制約式を等式として定義することを指定し,第三引数は右辺の値を1と定義することを表わす.第二引数に指定できるものには他にLpConstraintLE,LpConstraintGEがある.こうして定義した制約式の左辺に含まれる変数は,この時点では,ない.

つぎに,問題に追加する変数を定義する.変数を定義する際に,その変数の各制約式における係数を指定する.すでに問題probには,目的関数objと3つの制約式constraint['a'],constraint['b'],constraint['c']が追加されている.新たに変数を生成して問題probに追加するには,次のようにする.ここではリストcaの各要素に一つずつ変数を生成するとする.

xVars=[LpVariable("x_"+c,0,1,LpContinuous,1*obj+2*constraints[c]) for c in ca]

LpVariable()の第一引数は,生成する変数の名前の指定である.第二引数と第三引数は定数の範囲を表わす.第四引数は変数のタイプを表わす.ここでは連続変数として定義している.ここでのポイントは第五引数である.この第五引数で,生成する変数の各制約式における係数を指定する.1obj+2constraints[c]の意味は,生成する変数の「目的関数における係数は1,制約式constraints[c]における係数は2」であることを指定している.

Weber問題をPICOSで解く

  • 投稿日:
  • by

PICOSは錐最適化のためのPythonのインターフェイス.これで,Weber問題を二次錐最適化問題として定式化して解くPythonコードはつぎのとおり.データは,久保ほか「あたらしい数理最適化 Python言語とGurobiで解く」から引用した.

\[
\begin{array}{ll}
\min & \displaystyle \sum_{i \in H} w_i z_i \\
\text{s.t.} & \sqrt{(x_i-X)^2+(y_i-Y)^2} \leq z_i \ (\forall i \in H)
\end{array}
\]

import numpy as np
import picos as pic
socp=pic.Problem()
H=[0,1,2,3,4,5,6]
xy=[[24,54],[60,63],[1,84],[12,100],[84,48],[15,64],[52,74]]
w=[2,1,2,3,4,5,4]
XY=socp.add_variable('XY',2)
z=[socp.add_variable('z['+str(i)+']',1) for i in H]
objective=sum(w[i]*z[i] for i in H)
socp.set_objective('min',objective)
socp.add_list_of_constraints([abs(xy[i]-XY) < z[i] for i in H])
socp.solve(solver='cvxopt')

SCIPでよく使う命令

  • 投稿日:
  • by

SCIPでよくつかう関数などの命令を,ここに抜き出します.沢山の引数を指定できる関数が多いのですが,どの引数が何の意味かわからなくなるのです.

  SCIPcreateConsLinear(scip,
         &tcon, // pointer to hold the created constraint
         "flow_s", //name of constraints
          0, //number of non zeros in the constraint
          NULL, //array with variables of constraint entries 
          NULL, //array with coefficients of constraint entries
          1, //left hand side of constraint
          1.0, //right hand side of constraint
          TRUE, TRUE,TRUE,TRUE,TRUE,TRUE,
          FALSE,FALSE,FALSE,FALSE//省略
          );

公式ページのもの(SCIPcreateConsLinear)

 SCIPaddVar(scip,&var)

 SCIPcreateVar(scip,var)

 SCIPcreate(&scip)

 SCIPincludeDefaultPlugins(scip);

 SCIPcreateProb(scip,"a Problem",
       NULL,NULL,NULL,NULL,NULL,NULL,NULL //省略
         );

 SCIPsetObjsense(scip,SCIP_OBJSENSE_MAXIMIZE);

 SCIPcreateVar(scip,&var,var_name,
                       0.0, //変数のlower bound
                       SCIPinfinity(scip), //変数のupper bound
                       alpha, //coefficient in the objective function
                       SCIP_VARTYPE_CONTINUOUS, //変数のタイプ. 0-1ならSCIP_VARTYPE_BINARY,
                       false,false,0,0,0,0,0 //略
         );


 SCIPaddCoefLinear(scip,
                     cons, //SCIP_CONS*
                     var, //SCIP_VAR*
                     val //SCIP_Real);

 SCIPprintCons(scip,
                    cons,//SCIP_CONS*
                    FILE* file)

SCIPcreateConsSOC数式過去のメモ

PICOSを使って錐計画問題を解く

  • 投稿日:
  • by
PICOS: A Python Interface for Conic Optimization Solvers は,公式ドキュメントに書いているように,Python版YALMIP LP・MIPだけでなく,錐計画のモデルが,数式に近い形で書くことができる. 対応しているソルバは,次のとおり.
  • cvxopt (LP, SOCP, SDP, GP)
  • smcp (LP, SOCP, SDP)
  • mosek (LP, MIP, (MI)SOCP, convex QCQP, MIQP)
  • cplex (LP, MIP, (MI)SOCP, convex QCQP, MIQP)
  • gurobi (LP, MIP, (MI)SOCP, convex QCQP, MIQP)
  • zibopt (soplex + scip : LP, MIP, MIQP, general QCQP)
では,使い方.まず,Pythonで,picosを使えようにする.
import picos as pic

次に問題をつくる.
pb=pic.Problem()

さて,ここにネットワーク上の枝を表すsetを定義する.ここで,ネットワークは,4つの点s,0,1,2,tと,5つの枝s->0, 0->1, 1->2, 2->tからなるとする.

arcs=set([])
arcs.add(('s',0))
arcs.add((0,1))
arcs.add((1,2))
arcs.add((2,'t'))

arcsの要素である各枝に対して変数を定義する.

for ta in arcs:   v[ta]=pb.add_variable('v[{0}]'.format(ta),1)

これで,変数vが定義された.vを表示してみると,次のように表示される.
> v {(0, 1): # variable v[(0, 1)]:(1 x 1),continuous #, ('s', 0): # variable v[('s', 0)]:(1 x 1),continuous #, (2, 't'): # variable v[(2, 't')]:(1 x 1),continuous #, (1, 2): # variable v[(1, 2)]:(1 x 1),continuous #}

すなわち,arcsの要素taに対して1x1(スカラー)の連続変数が定義されてv[ta]に入れられた.

さて,枝ta上のコストがv[ta]の二次関数として表されるとする.すなわち,\( a\cdot v[ta]^2+b\cdot v[ta]+c \cdot v[ta] \) とする.ここで,a=1, b=-4, c=9とする.このとき,s->0->1->2->tと4本の枝を通るときの最小コストのv[ta]を求める問題を解く.これは,最小化問題 \( \min. \quad \sum_{ta \in arcs} a\cdot v_{ta}^2 + b \cdot v_{ta} + c \) を解けばよい. ここで,補助変数u[ta]を導入して,二次の項を制約条件に移す.すると,二次錐制約をもった線形関数の最適化問題となる \begin{align} \min. \quad &\sum_{ta \in arcs} a\cdot u_{ta} + b \cdot v_{ta} + c \\ \mbox{s.t.} \quad & u_{ta} \geq v_{ta}^2 \end{align} この制約条件は, \( u_{ta}+1 \geq || (u_{ta}-1,2 v_{ta}) || \) という不等式として表すことができる.picosは,\( t \geq ||x|| \)という形の制約式があると,二次錐制約として扱ってくれる.そこで,この制約式を\(u_{ta}+1 \geq || (u_{ta}-1,2 v_{ta}) ||\)の形式で入力してみる.
u={}
for ta in arcs:
  u[ta]=pb.add_variable('u[{0}]'.format(ta),1)
for ta in arcs:
  pb.add_constraint( abs( (u[ta]-1)&(2*v[ta]))<(u[ta]+1)

ここで,abs()で絶対値を計算したいのは二次元のベクトル\( ( u_{ta}-1,2v_{ta} ) \)だが,それはpicosでは&を用いて(u[ta]-1)&(2*v[ta])と表される.
さて,目的関数を定義する.目的関数の定義には,係数a,b,cを使う.これには細工が必要である.すなわち
a,b,c=1,-4,9
a=pic.new_param('a',a)
b=pic.new_param('b',b)
c=pic.new_param('c',c)

として,変数xやuとの積をとれる形式にしておく.
pb.set_objective('min',pic.sum([a*u[ta]+b*v[ta]+c for ta in arcs]))

CBLIB

  • 投稿日:
  • by

CBLIB. The Conic Benchmark Libraryは,混合錐計画問題におけるベンチマークライブラリ.LPにおけるNetlib,MIPにおけるMIPLIBの役割を,Conic optimizationで果たす,という目的らしい.MOSEKのE. D. Andersen と H. A. Fribergがはじめて,いまはZIBがやっているようだ.121のインスタンスのうち,80には整数変数が含まれている.

121問すべてに二次錐が含まれている.半正定値錐を含む問題は最初のリリースには含まれていない.

インスタンスのtarballは4.6Gある.ファイル形式は,Conic Benchmark Format(CBF).

含まれるインスタンスは,

  1. シュタイナー木の問題
  2. 回転機のバランス問題
  3. 指向性アンテナの調整の問題 DIMACS
  4. プラスチック板の解析問題 DIMACS
  5. ジョブショップスケジューリング DIMACS
  6. 待ち行列によるサービスシステム設計の問題
  7. 施設配置の問題
  8. The chained singular function
  9. 生産計画の問題
  10. FIRの問題
  11. ポートフォリオ最適化の問題

3,4,5は,The DIMACS library of mixed semidefinite-quadratic-linear programsの問題だろう(インスタンス名が同じだし).8はKobayashi et al. 2008の実験で使ったインスタンスが入っている.

121個のインスタンスのうち,66個は3次元の二次錐しか含まないということだ.それ以外のうちの20個は,4次元以上の二次錐を一つだけ含む.9個は千以上の次元の二次錐を含む.二次錐の数は,1のものから100,000のものまである.

AIS関連情報へのリンク

  • 投稿日:
  • by

関連ページへのリンク

日本のVTS(通航ガイド)

AISの仕組み 古野電気

MarineTraffic

exactEarth

IMO E-navigation

東洋信号通信社

1974年の海上における人命の安全のための国際条約 (SOLAS条約),国土交通省

第5回海上人命安全条約(SOLAS)締約国政府会議の  結果について,国土交通省

国総研資料 第 768 号, 衛星AISを活用した北極海航路航行実態分析手法に関する検討

AIS情報を用いた次世代ナビ プロジェクト, 海上技術安全研究所 

JAXAによるSPAISE: 衛星搭載船舶自動識別装置システム(AIS)実験

海上保安庁 AISを活用した航行支援システム

日本沿岸安全航行用資料 海上保安庁 PDF

日本航路標識協会

International Association of Lighthouse Authorities

電子海図とその船舶搭載要件の実際 2010/1, 日本水路協会

ABLOS

国際水路機関 International Hydrographic Organization, IHO

国際測地学協会 International Association of Geodesy

交通政策審議会 海事分科会

日本海難防止協会情報誌 海と安全2010夏 No.545 【特集】AISが安全運航に果たす役割

電子情報通信学会 知識ベース | 11群 社会情報システム 2編 電子航法・ナビゲーションシステム

宇宙技術による船舶動静把握 平成23年11月17日 ALOS-2ワークショップ 宇宙航空研究開発機構 衛星利用推進センター 押村 康一氏による資料 PDF

DGPSの解説

鹿児島船舶通航信号所 AISをもっと活用しよう

国土地理院 高度な国土管理のための複数の衛星測位システム(マルチGNSS)による高精度測位技術の開発

海と安全2003春号 AISの導入

SCIP Optimization Suiteを使ってMINLPを解く

  • 投稿日:
  • by

SCIPは,http://scip.zib.de/から入手可能。非線形計画問題を解くために,CppADと,lpoptを使う.

ZIBの提供するSCIP Optimization Suite(以下,SCIP)は,整数変数を含む数理計画問題を解くことができます。 非商用には無料で使用可能です。(詳しくはライセンスを確認ください。) このSCIPを使って,混合整数非線形計画問題を解いてみます。
SCIPにはZIMPLというモデリング言語が含まれています。 ZIMPLを使うと,数式に近い形で数理計画問題を記述してソルバに与えることができます。 ZIMPLは非線形計画問題を記述することはできますが, SCIPにはそれらを解く機能が含まれていません.非線形計画問題を解くには, COIN-ORによって提供されているソフトウェアIPOPTをインストールし,SCIPのコンパイル時にIPOPTを使うことを 示す必要があります。そうすることで,SCIPによって非線形計画問題を解くことができるようになります。
IPOPTとSCIPのインストールはそれなりの手間がかかるかもしれませんが,ここでは,それらのインストールについては 述べません.コマンドラインから

    $scip
によってSCIPが実行可能な状態になっている,ということを仮定して話を進めます。

準備体操として,次の二次関数の最小化問題を,ZIMPLで書いて解きます。

min f(v):=0.0036*v^2-0.1015*v+0.8848 
subject to 11 <= v <= 19
これを解くためのZIMPLファイルは,次の通りです。
param vmin:=11;
param vmax:=19;
param alpha:=0.0036;
param beta:=-0.1015;
param gamma:=0.8848;
var v;
var q;
minimize cost: alpha*q+beta*v+gamma;
subto vmin:
        vmin<=v;
subto vmax:
        v<=vmax;
subto quad:
        q>=v^2;
        
これをex1.zplとして保存して
$ scip -f ex1.zpl
とすると,v=14.0972222235149が得られます。この解は,二次関数を平方完成すれば得られることは,高校の数学の範囲内です。

ZIMPLのモデルでは,目的関数が線形でなければなりません。いまは,二次関数を最小化しようとしているので,補助変数qを導入して,

    min. alpha*v^2+beta*v+gamma
    
の代わりに
    min. alpha*q+beta*v+gamma
    s.t. q>=v^2
    
としていることに注意してください。これで,二次の要素は制約式に移し,目的関数は線形にすることができます.

次に,最短路問題に毛を生やした問題を解いてみます。

まず,基本的な最短路問題の例題として,ZIMPL User Guide version 3.3.1 Section 2 Introductionのネットワークを 使います。そのZIMPLモデルはUser Guideにあるとおり, 次のように書けます。

set V := {"a","b","s","t"};
set A := {<"s","a">,<"s","b">,<"a","b">,<"a","t">,<"b","t">};
param c[A] := <"s","a">17,<"s","b">47,<"a","b">19,<"a","t">53,<"b","t">23;
defset dminus(v):={<i,v> in A};
defset dplus(v):={<v,j>in A};
var x[A] binary;
minimize cost: sum in A: c[i,j] * x[i,j];
subto fc:
        forall  in V - {"s","t"}:
                sum in dminus(v):x[i,v] == sum in dplus(v): x[v,i];
subto uf:
        sum in dplus("s"):x[s,i]==1;
ここでは、アークの費用c[i,j]は定数として与えられています。そして, 変数は,各アークに対して定義された0-1変数x[i,j]のみです。

この最短路問題に毛を生やしてみましょう。
目的関数を定数ではなく,アーク上を移動する 際の速度vの関数とします。 速度vで移動するときの単位距離あたりの移動コストが, 上の二次関数f(v)で得られるとします。c[i,j]は,アーク上の距離と解釈することにします。 アーク(i,j)上の速度は,実数変数sp[i,j]と表しています。

set V := {"a","b","s","t"};
set A := {<"s","a">,<"s","b">,<"a","b">,<"a","t">,<"b","t">};
param c[A] := <"s","a">17,<"s","b">47,<"a","b">19,<"a","t">53,<"b","t">23;
param alpha:=0.0036;
param beta:=-0.1015;
param gamma:=0.8848;
param vmin:=11;
param vmax:=19;
defset dminus(v):={<i,v>in A};
defset dplus(v):={<v,j>in A};
var x[A] binary;
var sp[A];
var ecost[A];
minimize cost: sum in A: ecost[i,j]*c[i,j];
subto fc:
        forall  in V - {"s","t"}:
                sum in dminus(v):x[i,v] == sum in dplus(v): x[v,i];
subto uf:
        sum in dplus("s"):x[s,i]==1;
subto ecost:
        forall  in A:
                ecost[i,j]>=alpha*sp[i,j]^2+beta*sp[i,j]+gamma*x[i,j];
subto vmin:
        forall  in A:
                vmin*x[i,j]<=sp[i,j];
subto vmax:
        forall  in A:
                sp[i,j]<=vmax*x[i,j];
このZIMPLモデルをたとえばsp.zplという名前のファイルとして保存して
$scip -f sp.zpl
とすると,s->a->b->tと行くのが最適で,s->a,a->b, b->tのいずれも14.1の速度で行くのが最適である,と いう解が得られます。これは最初の最短路と同じです。当たり前です。距離が最も短い経路を,最もコストの小さい速度14.1で行くのが最適だといっているのですから。

次に,各ノードを訪問できる時刻に制限をつけます。これを時間枠制約といいます。 時間枠制約を表すために,各ノードへの訪問時刻(ノードを出発する時刻)を表す変数が必要です。 ノードiからの出発時刻をvtime[i]とします。 アーク(i,j)を使用するときは,次の関係が成り立つ必要があります。

    vtime[i]+c[i,j]/sp[i,j]<=vtime[j]
ここで,c[i,j]はアーク(i,j)の距離,sp[i,j]はアーク(i,j)上の移動速度とします。つまりこの式は,ノードiを出発する時刻に,アーク(i,j)上の移動時間を足したものより,ノードjを出発する時刻の方が大きい,ということを表しています。
この関係式は,アーク(i,j)を使用するときだけ成り立てばよいものです。
ただし,ZIMPLはc[i,j]/sp[i,j]という分数の表現が使えないので,かわりに両辺にsp[i,j]をかけた
    vtime[i]*sp[i,j]+c[i,j]<=vtime[j]*sp[i,j]

を使います。
アーク(i,j)を使用することは,x[i,j]が1であることで示されます。ZIMPLでは,変数の値を用いた分岐処理を書くことができます。この場合の処理は,具体的には次の通りに書けます。

subto tm_trans:
    forall  in A:
        vif x[i,j]>0
        then vtime[i]*sp[i,j]+c[i,j]<=vtime[j]*sp[i,j] end;

ここで,x[i,j]が1であるという条件は,x[i,j]>0と表しています。
変数の値による分岐処理が気持ち悪い,という方は,上の制約のかわりに次の書き方があります。

subto tm_trans:
    forall  in A:
        vtime[i]*sp[i,j]+c[i,j]*x[i,j]<=vtime[j]*sp[i,j];

この書き方では,c[i,j]の代わりにc[i,j]*x[i,j]を用いています。 こうすると,x[i,j]が0のときには両辺がともに0で成り立ち, x[i,j]が1のときにはvtime[i],vtime[j],sp[i,j]間の制約を意図通りに表します。
ノードiへの最早訪問時刻(earliest arrival time)をearliest[i], 最遅訪問時刻(latest arrival time)をlatest[i]と表します これらの値はパラメータとして指定するのですが,その方法は次のとおりです。

param latest[V]:=<"s"> 0,<"a"> 0.8,<"b">2,<"t"> 1.8 default 10000;
param earliest[V]:=<"s"> 0,<"a"> 0,<"b">0,<"t"> 0 default 0;

これらを用いて,時間枠制約は次のように表すことができます。

subto tm_latest:
        forall  in V:
                vtime[v]<=latest[v];
subto tm_earliest:
        forall  in V:
                earliest[v]<=vtime[v];

これらをまとめたZIMPLモデルは次のとおりです。これを例えばsp_tw.zplという名前のファイルに保存し,

$scip -f sp_tw.zpl

を実行すれば,答えが得られます。

set V:={"s","a","b","t"};
set A := {<"s","a">,<"s","b">,<"a","b">,<"a","t">,<"b","t">};
param c[A] := <"s","a">14,<"s","b">14,<"a","b">14,<"a","t">42,<"b","t">14;
param latest[V]:=<"s"> 0,<"a"> 0.8,<"b">2,<"t"> 1.8 default 10000;
param earliest[V]:=<"s"> 0,<"a"> 0,<"b">0,<"t"> 0 default 0;
param alpha:=0.0036;
param beta:=-0.1015;
param gamma:=0.8848;
param vmin:=11;
param vmax:=19;
defset dminus(v):={ in A};
defset dplus(v):={ in A};
var x[A] binary;
var sp[A];
var ecost[A];
var vtime[V] >=0 <=1000;
minimize cost: sum in A: ecost[i,j]*c[i,j];
subto fc:
        forall  in V - {"s","t"}:
                sum in dminus(v):x[i,v] == sum in dplus(v): x[v,i];
subto uf:
        sum in dplus("s"):x[s,i]==1;
subto ecost:
        forall  in A:
                ecost[i,j]>=alpha*sp[i,j]^2+beta*sp[i,j]+gamma*x[i,j];
subto vmin:
        forall  in A:
                vmin*x[i,j]<=sp[i,j];
subto vmax:
        forall  in A:
                sp[i,j]<=vmax*x[i,j];
subto tm_trans:
        forall  in A:
                vtime[i]*sp[i,j]+c[i,j]*x[i,j]<=vtime[j]*sp[i,j];
subto tm_latest:
        forall  in V:
                vtime[v]<=latest[v];
subto tm_earliest:
        forall  in V:
                earliest[v]<=vtime[v];

このモデルは,非線形のコストをもった時間枠制約付き最短路問題です。数理計画問題のクラスとしては,整数変数を含んでいて,非線形の項をもったものです。このクラスの問題を解くことのできるソルバは,ありがたいです。
(2014.1.9)

networkx, numpy, decimalを使います.
networkxの有向グラフのノードを複製し,離散時刻とのペアを作って時間拡大ネットワークを定義します.
元の有向グラフは,8〜12行で示すように,5本の枝を持つとします.各枝には移動時間とコストが関連づけられています.
離散時刻の最小時刻は,0, 最大時刻は5,その間は0.25の等間隔に離散時刻を設定します.
等間隔の離散時刻を設定する為に,np.arange()を使います(16行目)
時間拡大ネットワークは,networkxの有向グラフ(DiGraph)として表し,tGと呼んでいます(20行目).
G.adjacency_iter()で,ネットワークGの各ノードの隣接リストの各要素に対する処理をしています.
25行目のdata = eattr['weight']で,元のネットワークの枝に対する属性(time,cost)をdataに代入しています.
data['time'], data['cost']によって,枝の移動時間と移動コストが得られます.


  1 import networkx as nx
  2 import numpy as np
  3 from decimal import *
  4 from math import *
  5 G=nx.DiGraph()
  6 tedges=[]
  7 #tail,head,time,cost
  8 tedges+=[(1,2,{'time':2,'cost':3})]
  9 tedges+=[(1,3,{'time':2,'cost':2})]
 10 tedges+=[(2,3,{'time':1,'cost':5})]
 11 tedges+=[(2,4,{'time':3,'cost':10})]
 12 tedges+=[(3,4,{'time':4.1,'cost':7})]
 13 G.add_weighted_edges_from(tedges)
 14 tstart,tend,tint=0.0,5.0,0.25
 15 epsilon=1e-7
 16 tdisctime=np.arange(tstart,tend+tint,tint)
 17 disctime=[]
 18 for t in tdisctime:
 19         disctime+=[float(Decimal(t).quantize(Decimal('.00'),
               rounding=ROUND_HALF_UP))]
 20 tG=nx.DiGraph()
 21 tedges=[]
 22 for tail,nbrs in G.adjacency_iter():
 23         for head,eattr in nbrs.items():
 24                 for tail_t in disctime:
 25                         data = eattr['weight']
 26                         arr_t=tail_t+data['time']
 27                         if arr_t>floor(arr_t/tint)*tint+1e-7:
 28                                 arr_t=(floor(arr_t/tint)+1)*tint
 29                         else:
 30                                 arr_t=floor(arr_t/tint)*tint
 31                         if arr_t<=tend:
 32                                 tcost=data['cost']
 33                                 tedges+=[((tail,tail_t),(head,arr_t),
                        {'weight':tcost})]
 34 tG.add_edges_from(tedges)
 35 for e in tG.edges_iter():
 36         print e