線形計画法を使用した、数理的最適化の旅（Ⅰ）

門前パソコン学習所
令和４年皐月(2022/05/20)
2023-05-06

ページ末尾

理論的学習はさておき、入門的な実践を試みた。

使用パソコン環境

Microsoft の Windows(Win10) を使用した PC(CPU インテルi5、メモリ 8GB)
統合開発環境は Visual Studio 2017
ウエブブラウザとして Google Chrome
Python の開発環境は anaconda を使用

最初に制約整数プログラム SCIP(Solving Constraint Integer Programs) の簡単な使用方法を見ていく。

詳細な SCIP については (HTTP://scipopt.org) のウエブサイトを参照。

SCIP ソルバーを C++ 言語で使用する方法

まず標準線形計画法的な問題のソルバーとして活用する。

SCIP バイナリーの取得とインストール。

（ここでは３２ビット版を使用）

SCIP インストール

Visual Studio 2017 のコンソールアプリケーションプロジェクトを作成し、プロパティーを設定する。

VC++ディレクトリ	インクルードディレクトリ	"C:\Program Files (x86)\SCIPOptSuite 8.0.0\include"
	ライブラリ	"C:\Program Files (x86)\SCIPOptSuite 8.0.0\lib"
リンカー	追加の依存ファイル	"libscip.lib"

Quickstart 問題（これは SCIP のウエブサイトにある）

目的関数（最大化）

2*x2

3*x3

制約式

10*x4

≤

3*x2

≤

3.5*x4

0 ≤ x1 ≤ 40,

x2,x3 ≥ 0,

2 ≤ x4 ≤ 3,

x4 = General

ソースファイルを取り込む。

ソースファイルの主要部分をリストする。

問題の定義

決定変数の定義

制約式の定義

目的関数の定義

解決

#include <iostream>

#include "Header.h"

SCIP_RETCODE quichstart()
{
	SCIP *	scip = nullptr;
	// SCIP 環境を初期化
	SCIP_CALL(SCIPcreate(&scip));
	// デフォールトプラグインを設定
	SCIP_CALL(SCIPincludeDefaultPlugins(scip));

	// 問題の定義
	SCIP_CALL(SCIPcreateProbBasic(scip, "SCIP_simple_example"));
	// 目的関数を最大化に変更
	SCIP_CALL(SCIPsetObjsense(scip, SCIP_OBJSENSE_MAXIMIZE));

	// 決定変数の定義
	SCIP_VAR* x1 = nullptr;
	SCIP_VAR* x2 = nullptr;
	SCIP_VAR* x3 = nullptr;
	SCIP_VAR* x4 = nullptr;

	SCIP_CALL(SCIPcreateVarBasic(scip,
		&x1,                       // 変数への参照
		"x1",                      // 名前
		0.0,                       // 下限値
		40.0,			   // 上限値
		1.0,                       // 目的関数の係数
		SCIP_VARTYPE_CONTINUOUS)); // 変数のタイプ（実数）

	SCIP_CALL(SCIPaddVar(scip, x1));   // 最初の変数を scip に追加する

	// 以下同様

	// SCIP に制約式を追加する
	SCIP_CONS* cons1 = nullptr;

	SCIP_CALL(SCIPcreateConsBasicLinear(scip, // SCIP ポインタ
		&cons1,               // SCIP 制約へのポインタ
		"cons1",              // 制約の名前
		0,                    // ここで追加する変数の数
		nullptr,              // 空のポインタ
		nullptr,              // 空のポインタ
		-SCIPinfinity(scip),  // 制約式の左辺値 (LHS)
		20));                 // 制約式の右辺値 (RHS)
	  
	// 変数 x1 の係数 -1.0
	SCIP_CALL(SCIPaddCoefLinear(scip, cons1, x1,-1.0));
	// 変数 x2 の係数 1.0
	SCIP_CALL(SCIPaddCoefLinear(scip, cons1, x2, 1.0));
	// 変数 x3 の係数 1.0
	SCIP_CALL(SCIPaddCoefLinear(scip, cons1, x3, 1.0));
	// 変数 x4 の係数 10.0
	SCIP_CALL(SCIPaddCoefLinear(scip, cons1, x4,10.0));
	// 制約を scip に追加
	SCIP_CALL(SCIPaddCons(scip, cons1));

	SCIP_CONS* cons2 = nullptr;
	SCIP_CONS* cons3 = nullptr;

	// 以下同様

	// SCIP model に制約を追加したので、以下の解放を行う。
	SCIP_CALL(SCIPreleaseCons(scip, &cons1));
	SCIP_CALL(SCIPreleaseCons(scip, &cons2));
	SCIP_CALL(SCIPreleaseCons(scip, &cons3));
	// 以上で準備が完了。

	// 問題を解決する。
	SCIP_CALL(SCIPsolve(scip));

	// 解を検索するためにソリューションオブジェクトを作成する。
	SCIP_SOL* sol;
	sol = SCIPgetBestSol(scip);
	std::cout << "x1: " << SCIPgetSolVal(scip, sol, x1) << " "
		<< "x2: " << SCIPgetSolVal(scip, sol, x2) << " "
		<< "x3: " << SCIPgetSolVal(scip, sol, x3) << " "
		<< "x4: " << SCIPgetSolVal(scip, sol, x4) << "\n";

	// 変数を解放する。
	SCIP_CALL(SCIPreleaseVar(scip, &x1));
	SCIP_CALL(SCIPreleaseVar(scip, &x2));
	SCIP_CALL(SCIPreleaseVar(scip, &x3));
	SCIP_CALL(SCIPreleaseVar(scip, &x4));

	// SCIP 環境を解放する。
	SCIP_CALL(SCIPfree(&scip));

	return SCIP_OKAY;
}

// Header.h
#pragma once

#pragma warning(disable:4819)
#include <scip/scip.h>
#include <scip/scipdefplugins.h>
#pragma warning(error:4819)

主たる SCIP API （アプリケーションインターフェース）の一覧

この部分は現在調整中。

Quickstart の実行結果

計算結果を比較するためパイソン(Python) で処理した結果を示す。

ソルバーは GUROBI 類似のインターフェースを使用。

目的関数が最小化の小さな例（制約式に≧を含む）

（参考、文科系の線形計画法入門、平本巌・栗原和夫牧野書店 2000年03月30日）

目的関数（最小化） 40*x1 + 25*x2

制約式 270*x1 + 60*x2 ≧ 2500

8*x1 + 3*x2 ≧ 70

11*x1 + 100*x2 ≧ 600

x1,x2 ≥ 0,

ソースファイルを取り込む。

#include <iostream>

#include "Header.h"

SCIP_RETCODE calorie()
{
	SCIP *	scip = nullptr;
	SCIP_CALL(SCIPcreate(&scip));
	SCIP_CALL(SCIPincludeDefaultPlugins(scip));

	SCIP_CALL(SCIPcreateProbBasic(scip, "SCIP_my_example"));
	//SCIP_CALL(SCIPsetObjsense(scip, SCIP_OBJSENSE_MAXIMIZE));

	// min		 40*x1 +  25*x2
	// subject to	270*x1 +  60*x2 ≧ 2500
	//		  8*x1 +   3*x2 ≧ 70
	//		 11*x1 + 100*x2 ≧ 600
	//		x1,x2 ≥ 0

	SCIP_VAR* x1 = nullptr;
	SCIP_VAR* x2 = nullptr;

	SCIP_CALL(SCIPcreateVarBasic(scip,
		&x1,
		"x1",
		0.0, 
		SCIPinfinity(scip),
		40.0, 
		SCIP_VARTYPE_CONTINUOUS));

	SCIP_CALL(SCIPaddVar(scip, x1));

	SCIP_CALL(SCIPcreateVarBasic(scip,
		&x2, 
		"x2",
		0.0, 
		SCIPinfinity(scip),
		25.0,
		SCIP_VARTYPE_CONTINUOUS));

	SCIP_CALL(SCIPaddVar(scip, x2));

	SCIP_CONS* cons1 = nullptr;

	SCIP_CALL(SCIPcreateConsBasicLinear(scip,
		&cons1,
		"cons1", 
		0,
		nullptr,
		nullptr,
		-SCIPinfinity(scip),	// LHS
		-2500.0));		// RHS

	SCIP_CALL(SCIPaddCoefLinear(scip, cons1, x1, -270.0));
	SCIP_CALL(SCIPaddCoefLinear(scip, cons1, x2, -60.0));
	SCIP_CALL(SCIPaddCons(scip, cons1));

	SCIP_CONS* cons2 = nullptr;

	SCIP_CALL(SCIPcreateConsBasicLinear(scip,
		&cons2,
		"cons2",
		0,
		nullptr,
		nullptr,
		-SCIPinfinity(scip),
		-70.0));

	SCIP_CALL(SCIPaddCoefLinear(scip, cons2, x1, -8.0));
	SCIP_CALL(SCIPaddCoefLinear(scip, cons2, x2, -3.0));
	SCIP_CALL(SCIPaddCons(scip, cons2));

	SCIP_CONS* cons3 = nullptr;

	SCIP_CALL(SCIPcreateConsBasicLinear(scip,
		&cons3,
		"cons3",
		0,
		nullptr,
		nullptr,
		-SCIPinfinity(scip),
		-600.0));

	SCIP_CALL(SCIPaddCoefLinear(scip, cons3, x1, -11.0));
	SCIP_CALL(SCIPaddCoefLinear(scip, cons3, x2, -100.0));
	SCIP_CALL(SCIPaddCons(scip, cons3));

	SCIP_CALL(SCIPreleaseCons(scip, &cons1));
	SCIP_CALL(SCIPreleaseCons(scip, &cons2));
	SCIP_CALL(SCIPreleaseCons(scip, &cons3));

	SCIP_CALL(SCIPsolve(scip));

	SCIP_SOL* sol;
	sol = SCIPgetBestSol(scip);
	std::cout << "x1: " << SCIPgetSolVal(scip, sol, x1) << " "
		<< "x2: " << SCIPgetSolVal(scip, sol, x2) << "\n";

	SCIP_CALL(SCIPreleaseVar(scip, &x1));
	SCIP_CALL(SCIPreleaseVar(scip, &x2));

	SCIP_CALL(SCIPfree(&scip));

	return SCIP_OKAY;
}

目的関数が最小化の小さな例の実行結果

パイソンによる結果

ページ先頭

本頁の内容については、提示された文章や画像をそのまま、ご覧になる方の責任において判断していただくことを前提にしており、
当学習所は如何なる責任も負いません。
また会員登録者のみ閲覧可能な頁があります。登録については下記の連絡先にお問い合わせください。

この頁の如何なる情報も著作権についてはご注意ください。

『線形計画法を使用した、数理的最適化の旅（Ⅰ）』