{ "cells": [ { "attachments": {}, "cell_type": "markdown", "id": "9ec1907b-db93-4840-9439-c9005902b968", "metadata": {}, "source": [ "# Learning Solver\n", "\n", "On previous pages, we discussed various components of the MIPLearn framework, including training data collectors, feature extractors, and individual machine learning components. In this page, we introduce **LearningSolver**, the main class of the framework which integrates all the aforementioned components into a cohesive whole. Using **LearningSolver** involves three steps: (i) configuring the solver; (ii) training the ML components; and (iii) solving new MIP instances. In the following, we describe each of these steps, then conclude with a complete runnable example.\n", "\n", "### Configuring the solver\n", "\n", "**LearningSolver** is composed by multiple individual machine learning components, each targeting a different part of the solution process, or implementing a different machine learning strategy. This architecture allows strategies to be easily enabled, disabled or customized, making the framework flexible. By default, no components are provided and **LearningSolver** is equivalent to a traditional MIP solver. To specify additional components, the `components` constructor argument may be used:\n", "\n", "```python\n", "solver = LearningSolver(\n", " components=[\n", " comp1,\n", " comp2,\n", " comp3,\n", " ]\n", ")\n", "```\n", "\n", "In this example, three components `comp1`, `comp2` and `comp3` are provided. The strategies implemented by these components are applied sequentially when solving the problem. For example, `comp1` and `comp2` could fix a subset of decision variables, while `comp3` constructs a warm start for the remaining problem.\n", "\n", "### Training and solving new instances\n", "\n", "Once a solver is configured, its ML components need to be trained. This can be achieved by the `solver.fit` method, as illustrated below. The method accepts a list of HDF5 files and trains each individual component sequentially. Once the solver is trained, new instances can be solved using `solver.optimize`. The method returns a dictionary of statistics collected by each component, such as the number of variables fixed.\n", "\n", "```python\n", "# Build instances\n", "train_data = ...\n", "test_data = ...\n", "\n", "# Collect training data\n", "bc = BasicCollector()\n", "bc.collect(train_data, build_model)\n", "\n", "# Build solver\n", "solver = LearningSolver(...)\n", "\n", "# Train components\n", "solver.fit(train_data)\n", "\n", "# Solve a new test instance\n", "stats = solver.optimize(test_data[0], build_model)\n", "\n", "```\n", "\n", "### Complete example\n", "\n", "In the example below, we illustrate the usage of **LearningSolver** by building instances of the Traveling Salesman Problem, collecting training data, training the ML components, then solving a new instance." ] }, { "cell_type": "code", "execution_count": 3, "id": "92b09b98", "metadata": { "collapsed": false, "jupyter": { "outputs_hidden": false } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (linux64)\n", "\n", "CPU model: AMD Ryzen 9 7950X 16-Core Processor, instruction set [SSE2|AVX|AVX2|AVX512]\n", "Thread count: 16 physical cores, 32 logical processors, using up to 32 threads\n", "\n", "Optimize a model with 10 rows, 45 columns and 90 nonzeros\n", "Model fingerprint: 0x6ddcd141\n", "Coefficient statistics:\n", " Matrix range [1e+00, 1e+00]\n", " Objective range [4e+01, 1e+03]\n", " Bounds range [1e+00, 1e+00]\n", " RHS range [2e+00, 2e+00]\n", "Presolve time: 0.00s\n", "Presolved: 10 rows, 45 columns, 90 nonzeros\n", "\n", "Iteration Objective Primal Inf. Dual Inf. Time\n", " 0 6.3600000e+02 1.700000e+01 0.000000e+00 0s\n", " 15 2.7610000e+03 0.000000e+00 0.000000e+00 0s\n", "\n", "Solved in 15 iterations and 0.00 seconds (0.00 work units)\n", "Optimal objective 2.761000000e+03\n", "Set parameter LazyConstraints to value 1\n", "Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (linux64)\n", "\n", "CPU model: AMD Ryzen 9 7950X 16-Core Processor, instruction set [SSE2|AVX|AVX2|AVX512]\n", "Thread count: 16 physical cores, 32 logical processors, using up to 32 threads\n", "\n", "Optimize a model with 10 rows, 45 columns and 90 nonzeros\n", "Model fingerprint: 0x74ca3d0a\n", "Variable types: 0 continuous, 45 integer (45 binary)\n", "Coefficient statistics:\n", " Matrix range [1e+00, 1e+00]\n", " Objective range [4e+01, 1e+03]\n", " Bounds range [1e+00, 1e+00]\n", " RHS range [2e+00, 2e+00]\n", "\n", "User MIP start produced solution with objective 2796 (0.00s)\n", "Loaded user MIP start with objective 2796\n", "\n", "Presolve time: 0.00s\n", "Presolved: 10 rows, 45 columns, 90 nonzeros\n", "Variable types: 0 continuous, 45 integer (45 binary)\n", "\n", "Root relaxation: objective 2.761000e+03, 14 iterations, 0.00 seconds (0.00 work units)\n", "\n", " Nodes | Current Node | Objective Bounds | Work\n", " Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time\n", "\n", " 0 0 2761.00000 0 - 2796.00000 2761.00000 1.25% - 0s\n", " 0 0 cutoff 0 2796.00000 2796.00000 0.00% - 0s\n", "\n", "Cutting planes:\n", " Lazy constraints: 3\n", "\n", "Explored 1 nodes (16 simplex iterations) in 0.01 seconds (0.00 work units)\n", "Thread count was 32 (of 32 available processors)\n", "\n", "Solution count 1: 2796 \n", "\n", "Optimal solution found (tolerance 1.00e-04)\n", "Best objective 2.796000000000e+03, best bound 2.796000000000e+03, gap 0.0000%\n", "\n", "User-callback calls 110, time in user-callback 0.00 sec\n" ] }, { "data": { "text/plain": [ "{'WS: Count': 1, 'WS: Number of variables set': 41.0}" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import random\n", "\n", "import numpy as np\n", "from scipy.stats import uniform, randint\n", "from sklearn.linear_model import LogisticRegression\n", "\n", "from miplearn.classifiers.minprob import MinProbabilityClassifier\n", "from miplearn.classifiers.singleclass import SingleClassFix\n", "from miplearn.collectors.basic import BasicCollector\n", "from miplearn.components.primal.actions import SetWarmStart\n", "from miplearn.components.primal.indep import IndependentVarsPrimalComponent\n", "from miplearn.extractors.AlvLouWeh2017 import AlvLouWeh2017Extractor\n", "from miplearn.io import write_pkl_gz\n", "from miplearn.problems.tsp import (\n", " TravelingSalesmanGenerator,\n", " build_tsp_model,\n", ")\n", "from miplearn.solvers.learning import LearningSolver\n", "\n", "# Set random seed to make example reproducible.\n", "random.seed(42)\n", "np.random.seed(42)\n", "\n", "# Generate a few instances of the traveling salesman problem.\n", "data = TravelingSalesmanGenerator(\n", " n=randint(low=10, high=11),\n", " x=uniform(loc=0.0, scale=1000.0),\n", " y=uniform(loc=0.0, scale=1000.0),\n", " gamma=uniform(loc=0.90, scale=0.20),\n", " fix_cities=True,\n", " round=True,\n", ").generate(50)\n", "\n", "# Save instance data to data/tsp/00000.pkl.gz, data/tsp/00001.pkl.gz, ...\n", "all_data = write_pkl_gz(data, \"data/tsp\")\n", "\n", "# Split train/test data\n", "train_data = all_data[:40]\n", "test_data = all_data[40:]\n", "\n", "# Collect training data\n", "bc = BasicCollector()\n", "bc.collect(train_data, build_tsp_model, n_jobs=4)\n", "\n", "# Build learning solver\n", "solver = LearningSolver(\n", " components=[\n", " IndependentVarsPrimalComponent(\n", " base_clf=SingleClassFix(\n", " MinProbabilityClassifier(\n", " base_clf=LogisticRegression(),\n", " thresholds=[0.95, 0.95],\n", " ),\n", " ),\n", " extractor=AlvLouWeh2017Extractor(),\n", " action=SetWarmStart(),\n", " )\n", " ]\n", ")\n", "\n", "# Train ML models\n", "solver.fit(train_data)\n", "\n", "# Solve a test instance\n", "solver.optimize(test_data[0], build_tsp_model)" ] }, { "cell_type": "code", "execution_count": null, "id": "e27d2cbd-5341-461d-bbc1-8131aee8d949", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.12" } }, "nbformat": 4, "nbformat_minor": 5 }