## Tag: optimization

0
QPSOLVE: A new SAS IML function for quadratic optimization

Since the pandemic began in 2020, the SAS IML developers have added about 50 new functions and enhancements to the SAS IML language in SAS Viya. Among these functions are new modern methods for optimization that have a simplified syntax as compared to the older 'NLP' functions that are available

0
Isotonic regression: An application of quadratic optimization

Isotonic regression (also called monotonic regression) is a type of regression model that assumes that the response variable is a monotonic function of the explanatory variable(s). The model can be nondecreasing or nonincreasing. Certain physical and biological processes can be analyzed by using an isotonic regression model. For example, a

0
Compute the geometric median in SAS

Given a set of N points in k-dimensional space, can you find the location that minimizes the sum of the distances to the points? The location that minimizes the distances is called the geometric median of the points. For univariate data, the "points" are merely a set of numbers \$\${p_1,

Analytics
0
3 ways Blyott and SAS are revolutionizing hospital operations with real-time location tracking

For hospitals, managing inventory is an ongoing logistical challenge. The right equipment in the right spot is essential for safe and efficient hospital operations. That's why hospitals around the world turn to Blyott. Blyott is a plug-and-play machine learning and modular real-time-location-services (RTLS) provider. Their technology tracks the location of

0
Estimate the pth root of a Markov transition matrix

You can use a Markov transition matrix to model the transition of an entity between a set of discrete states. A transition matrix is also called a stochastic matrix. A previous article describes how to use transition matrices for stochastic modeling. You can estimate a Markov transition matrix by using

Customer Intelligence
0
Assessing classifier performance based on a profit matrix in SAS Viya

The ultimate objective of a churn model is preventing churn by making a retention offer. To determine reasonable values for profit and loss information, consider the outcomes and the actions that you would take given knowledge of these outcomes. For example, the marketing department of a telecommunications company wants to offer a discount to people who are no longer on a fixed-term contract. To prevent churn, the company is willing to make an offer in exchange for a one-year contract extension.

Analytics
0

はじめに 前回のブログでは、電力平準化問題が数理最適化のスケジューリング問題として扱えること、SASのCLP Procedureで簡単にモデリング可能であることを紹介しました。今回は具体的にサンプル問題でCLP Procedureの使い方を見ていきます(ブログ末尾にサンプルコード記載)。 CLP Procedureの使い方 ここではプロシジャの使い方を分かりやすく示すため、図1のような3タスク、2設備の簡略化された問題のスケジューリングを例として説明します。タスクの詳細な設定は表1の通りとします。   中身の詳しい説明に入る前に、一つだけ最適化の処理で理解しておくべき概念として、Resourceというものを紹介します。Resourceとはタスクを実行するために必要な何かしらの資源で、CLP Procedureによるスケジューリングでは「ある時間帯の使用電力がXである＝電力という資源をX占有する」のように読み替えることがポイントです。図1を例にとると、全体のResourceとしては電力設備M1とM2が1つずつ、電力は設定した電力上限分が用意されており、タスクA実行中は電力設備M1というResourceを1つ、電力というResourceを電力波形で表される分だけ各時間で占有する、と見なすことができます。最終的に実行可能なスケジュール(同じ時間帯に複数のタスクが同じ設備で実行されない、電力上限を超過しない)を作成することは、各タスクが上限の範囲内で上手くResourceを分け合うような割り当てを作成することに置き換えられます。 では、実際にSASコードでCLP Procedureを呼び出してスケジューリングを行う部分ですが、必要なのは以下のコードだけです。 proc clp actdata=act resdata=res schedtime=outtime schedres=outres; run; “schedtime”と”schedres”は出力先データセットの指定なので、ユーザーが用意する必要があるのは入力データの”actdata”と”resdata”のみです。では、それぞれのデータセットの内容を確認してみましょう。 “resdata”ではResourceの設定を行います。上での説明の通り、電力設備M1とM2が1つずつで、使用可能な電力総量の上限が“12”であることを表現しており非常に簡潔な設定です。 “actdata”はスケジューリングの対象となる最小要素であるActivityの設定を行います。今回の例では、タスクを図1のように分割したフェーズそれぞれを一つのActivityと考えます。こちらのデータセットは様々な要素が一行に並んでいるのでやや複雑ですが、設定項目は大まかに5種類の系統に分かれます。 まず_ACTIVITY_列では、各Activityにそれぞれ固有のIDを設定します。タスクAを例にとると、各フェーズの電力使用に当たるA01～A05と、タスク全体として設備M1を使用することを表すA00を設定しています。今回の問題では「設備M1を使用している間電力を使用する」という前提なので、A00の_DURATION_とA01～A05の合計が一致していることが確認できます。問題によっては「待ち時間などで使用電力0だが設備は占有したまま」のような状況で、両者の_DURATION_が異なる設定もあり得ます。 _SUCCESSOR_は前後関係を設定する対象のActivityを示しており、前後関係の種類と程度は_LAG_と_LAGDUR_で指定します。例えばFSは、「当該ActivityのFinishと_SUCCESSOR_で指定するActivityのStartの差が_LAGDUR_で指定する値以上」を示しています。今回の例では一つのタスクを分割したフェーズに相当するActivityは常に間を空けることなく実行されるため、_LAG_=FSE(FinishとStartが_LAGDUR_にEqual)、_LAGDUR_=0と設定しています。6行目のように、「タスクAの後3時間単位空けてタスクBを開始する」という業務的な意味での前後関係を表すのにも使用できます。また1行目のA00では、_LAG_=SSE(StartとStartが_LAGDUR_にEqual)でA01と開始が一致するように設定されていることにも注意が必要です。設定の詳細はマニュアルをご覧ください。 _ALIGNDATE_と_ALIGNTYPE_の組み合わせは_SUCCESSOR_と_LAG_の関係に似ていて、当該Activityと_ALIGNDATE_で指定した期日の間に_ALIGNTYPE_で指定する前後関係を設定します。例えば作業に着手可能になる時期や納期を表すのに使用でき、12行目では_ALIGNTYPE_=FEQ(Finishが_ALIGNDATE_=24にEqual)で「タスクB(のフェーズ5)が時刻24丁度に終了すること」を指定しています。 この設定でCLP Procedureを実行すると以下のような結果が得られ、時間に関する結果の”schedtime”とResourceに関する結果の”schedres”が出力されます。”schedtime”は各Activityをどの時間枠に割り当てるかという関心のある結果そのもの、”schedres”には例えば(今回の問題とは異なり)タスクを実行する設備にも選択肢がある場合のResourceの割り当てが出力されています。 最後に少しデータの加工が必要ですが、以下のようにガントチャートや電力波形に可視化して、諸々の条件が満たされたスケジュールになっていることが確認できます。図2 では"resdata"(表2)で指定した、「使用可能な電力総量の上限が“12”」を下回っていることが確認できます。 なお前回も記載しましたが、「ピーク値をどこまで下げることができるか？」を知りたい場合は、「使用可能な電力総量の上限」の指定値を下げて計算し、その条件を満たすスケジュールが作成可能かを調べることで下限を得ることができます。 まとめ 本ブログでは電力平準化問題を例として、CLP Procedureの使い方を見てきました。手順の中心となる入力データ準備の部分は、他のプログラミング言語で用意したものを読み込ませても良いですし、規模が小さければExcel上で作成してしまうことも可能です。SAS言語の知識も最適化の知識も最小限で、便利にスケジューリング機能が使えると感じていただけたなら幸いです。(反響があれば、設備の割り当ても考える場合など、より高度なモデリング方法についても取り上げます) サンプルコード 入力データは全てdataステップで作成しています。ganttプロシジャはclpプロシジャの結果である"schedtime"をほとんどそのまま使用できます(今回はグループ化の処理だけ追加しています)。使用電力の棒グラフについては、今回説明していないデータ加工が多少必要になるため、ソースコードからは割愛しています。 data res; input _RESOURCE_ \$ _CAPACITY_; datalines; M1 1 M2 1 El 12 ;

Analytics
0

はじめに 2022年も半ばを過ぎましたが、今年は何かと電力需給関係の話題を耳にすることが多くなっています。まず3月下旬には、直前に発生した福島県沖地震の影響で火力発電所が停止したことと寒波が重なり、東京電力と東北電力の管内で電力需給ひっ迫警報(予備率3%以下)が発令されました。そして6月下旬にも想定外の猛暑により、東京電力管内で電力需給ひっ迫注意報(予備率5%以下)が発令されています。事業者の皆様にとっても、政府からの節電要請など対応の必要な課題の一つではないでしょうか。 さて、本ブログでは製造業のスケジューリングを例にとって、使用電力の平準化(ピーク時間帯をシフトする、またピークそのものを下げる)問題に対するSASのアプローチをご紹介します。そもそも一般的なスケジューリング問題は数理最適化問題として扱えることが知られていますが、電力平準化問題も同様の枠組みで解決可能です。数理最適化によるスケジューリングは事例も豊富で歴史もある分野なのですが、通常の最適化エンジンを使用したスケジューリング問題のモデリングには背景にある数理最適化の理解が必要不可欠で、経験の無い方にとっては中々手を出しにくい代物というのが実情です。一方SAS Optimization(またはSAS/OR)にはスケジューリング問題専用の機能があり、CLP Procedureにフォーマットに従ったデータを与えるだけで、ほとんど数理最適化の理論を意識することなく簡単にモデリングすることができます。SASにはあまり最適化のイメージは無いかもしれませんが、本ブログをきっかけに意外と便利な機能が揃っていることを知っていただけたら幸いです。 問題設定 本ブログのスケジューリングで対象にするタスクとは、製造業における一連の生産プロセスのように、一度開始すると所定時間まで途中で中断することのできない作業のまとまりを指し、その間継続的に電力を使用するものとします(タスクごとに使用電力の推移がどうなるかは、過去の実績や予測としてデータ化されている必要があります)。 そして「使用電力を平準化する」とは、非常に単純に表現すると図1のように、使用電力の大きいタスクの時間的重なりをできるだけ解消してピークを下げることです。もちろん現実の問題では、設備の数や納期など様々な制約が存在するので、それらを考慮したスケジュールを作成する必要があります。 では次に、スケジューリング問題として扱いやすくするため現実の問題に対して行う、二つの側面からの近似を説明します。一つ目は時間軸に関する近似で、最小の時間単位を決めてその単位に粒度を丸めます。例えば30分単位で1日分のスケジュールを立てる場合、各タスクの所要時間も30分単位に切り上げて丸めて、「1日分48個の時間枠のどこからどこに割り当てるか」という処理を行うようにします。もう一つは電力波形に関する近似で、もとの波形を階段状に近似します。階段状の近似では、実際の電力波形の傾向が変わるなどキリの良い時点で分割して(フェーズに分割)、各フェーズの使用電力は常に期間中の最大値と同じとみなすような近似を行います。30分単位のスケジューリングを行う場合は、フェーズの所要時間も30分単位になるよう切り分けます。ここでは実際の電力波形を四角いブロックで覆うように近似していますが、もとの波形から多めに余裕を見て使用電力を設定している状況に該当しますので、このシミュレーションで電力ピークを削減できれば、実際にはもっと大きく削減できる可能性があるということになります。「時間軸はどれくらい細かく設定するか」や「タスクを何フェーズに分割するか」は、最終的なスケジュールの精度に影響しますので、問題の設定者が処理時間(細かくすればするほど計算の処理時間は伸びる)との兼ね合いで決定していく要素になります。電力に限定すると、電力会社の集計が30分単位なので、30分単位のスケジューリングには妥当性があります。 このような設定のタスクが複数存在してそれぞれのタスクを実行可能な設備が決まっている場合に、「各タスクをいつ開始するか」を上手く調節して、使用電力合計のピークが所定の上限を超えないようなスケジュールを作成することが今回の目的です。 本手法で行うのは与えた使用電力の上限を超えないスケジュールを作成することなので、いくらまでピーク値を下げられるかは自動的には求められません。通常は業務的に意味のある目標値を指定しますが、「ピーク値をどこまで下げることができるか？」を知りたい場合は、電力上限の指定値を変えて複数回実行することで求められます。指定値が厳しすぎて実行可能なスケジュールが無い場合は解なしと出るので、そこに至るまで少しずつ指定値を下げて再実行する、もしくはそのような処理を自動で行うシステムを実装します。 以下はある程度複雑な問題(30分単位1週間分、10設備、20タスク、上限10kW)を解いた時の結果イメージです。弊社では実際のプロジェクトでも使用電力平準化の問題に取り組んだ事例があり、階段状近似によって実際より各タスクの使用電力を過大評価している分を加味しても、最適化によって作成したスケジュールの方が実績よりピークが低くなることを示せました。 次回はサンプル問題でCLP Procedureの使い方を詳しく説明します！ まとめ 最後に電力平準化問題のビジネスインパクトについてですが、この問題で行っているのは使用電力のピーク値の削減で、使用量そのものを削減している訳ではない(合計すると同じ)ことに注意が必要です。電力会社との契約はピーク値に基づいて決まるため、それを小さくすることができれば一定のコスト削減効果はあります。また契約によっては時間帯によって料金が異なるため、高い時間帯からピークをずらせればその分だけのコスト削減も見込めます。ただし事業規模にもよりますが、この両者を総合しても、電力平準化だけで十分な投資対効果を得るのは難しい可能性もあります。一方、節電要請への対応はコストだけに還元できない社会的意義もあり、今後のディマンドレスポンス進展や、既に今冬にも予想されている電力ひっ迫への対応など、昨今の不安定な情勢へのBCPの一つとして十分に検討に値するテーマであるとも考えています。また同じような考え方で、より利益に直結するスケジューリングを検討することも可能です。 SASでは既存のユーザー様に対するライセンス追加や活用方法のアドバイス、既存・新規関わらずドメイン知識の豊富なコンサルタントによるプロジェクト化の支援など幅広く受け付けておりますので、ご興味を持たれた方は是非ご連絡ください。

0
An introduction to genetic algorithms in SAS

A genetic algorithm (GA) is a heuristic optimization technique. The method tries to mimic natural selection and evolution by starting with a population of random candidates. Candidates are evaluated for "fitness" by plugging them into the objective function. The characteristics of the better candidates are combined to create a new

0
Crossover and mutation: An introduction to two operations in genetic algorithms

This article uses an example to introduce to genetic algorithms (GAs) for optimization. It discusses two operators (mutation and crossover) that are important in implementing a genetic algorithm. It discusses choices that you must make when you implement these operations. Some programmers love using genetic algorithms. Genetic algorithms are heuristic

0
Penalties versus constraints in optimization problems

Sometimes we can learn as much from our mistakes as we do from our successes. Recently, I needed to solve an optimization problem for which the solution vector was a binary vector subject to a constraint. I was in a hurry. Without thinking much about what I was doing, I

Learn SAS
0
The knapsack problem: Binary integer programming in SAS/IML

Many optimization problems in statistics and machine learning involve continuous parameters. For example, maximum likelihood estimation involves optimizing a log-likelihood function over a continuous domain, possibly with constraints. Recently, however, I had to solve an optimization problem for which the solution vector was a 0/1 binary variable. To solve the

0
The partition problem: An optimization approach

I previously wrote about one way to solve the partition problem in SAS. In the partition problem, you divide (or partition) a set of N items into two groups of size k and N-k such that the sum of the items' weights is the same in each group. For example,

0
The partition problem

The partition problem has many variations, but recently I encountered it as an interactive puzzle on a computer. (Try a similar game yourself!) The player is presented with an old-fashioned pan-balance scale and a set of objects of different weights. The challenge is to divide (or partition) the objects into

0
Automated linearization in SAS Optimization

Linear programming (LP) and mixed integer linear programming (MILP) solvers are powerful tools. Many real-world business problems, including facility location, production planning, job scheduling, and vehicle routing, naturally lead to linear optimization models. Sometimes a model that is not quite linear can be transformed to an equivalent linear model to reduce