1.. _chapQuick: 2 3Quick start 4=========== 5 6This chapter presents the main components needed to build and optimize models using Python-MIP. A full description of the methods and their parameters can be found at :ref:`Chapter 4 <chapClasses>`. 7 8The first step to enable Python-MIP in your Python code is to add: 9 10.. code-block:: python 11 12 from mip import * 13 14When loaded, Python-MIP will display its installed version: :: 15 16 Using Python-MIP package version 1.6.2 17 18Creating Models 19--------------- 20 21The model class represents the optimization model. 22The code below creates an empty Mixed-Integer Linear Programming problem with default settings. 23 24.. code-block:: python 25 26 m = Model() 27 28By default, the optimization sense is set to *Minimize* and the selected solver is set to CBC. If Gurobi is installed and configured, it will be used instead. You can change the model objective sense or force the selection of a specific solver engine using additional parameters for the constructor: 29 30.. code-block:: python 31 32 m = Model(sense=MAXIMIZE, solver_name=CBC) # use GRB for Gurobi 33 34After creating the model, you should include your decision variables, objective function and constraints. These tasks will be discussed in the next sections. 35 36Variables 37~~~~~~~~~ 38 39Decision variables are added to the model using the :py:meth:`~mip.Model.add_var` method. Without parameters, a single variable with domain in :math:`\mathbb{R}^+` is created and its reference is returned: 40 41.. code-block:: python 42 43 x = m.add_var() 44 45By using Python list initialization syntax, you can easily create a vector of variables. Let's say that your model will have `n` binary decision variables (n=10 in the example below) indicating if each one of 10 items is selected or not. The code below creates 10 binary variables :code:`y[0]`, ..., :code:`y[n-1]` and stores their references in a list. 46 47.. code-block:: python 48 49 n = 10 50 y = [ m.add_var(var_type=BINARY) for i in range(n) ] 51 52Additional variable types are :code:`CONTINUOUS` (default) and :code:`INTEGER`. 53Some additional properties that can be specified for variables are their lower and upper bounds (:py:attr:`~mip.Var.lb` and :py:attr:`~mip.Var.ub`, respectively), and names (property :attr:`~mip.Var.name`). 54Naming a variable is optional and it is particularly useful if you plan to save you model (see :ref:`save-label`) in .LP or .MPS file formats, for instance. 55The following code creates an integer variable named :code:`zCost` which is restricted to be in range :math:`\{-10,\ldots,10\}`. 56Note that the variable's reference is stored in a Python variable named :code:`z`. 57 58.. code-block:: python 59 60 z = m.add_var(name='zCost', var_type=INTEGER, lb=-10, ub=10) 61 62You don't need to store references for variables, even though it is usually easier to do so to write constraints. 63If you do not store these references, you can get them afterwards using the Model function :func:`~mip.Model.var_by_name`. 64The following code retrieves the reference of a variable named :code:`zCost` and sets its upper bound to 5: 65 66.. code-block:: python 67 68 vz = m.var_by_name('zCost') 69 vz.ub = 5 70 71Constraints 72~~~~~~~~~~~ 73 74Constraints are linear expressions involving variables, a sense of :code:`==`, :code:`<=` or :code:`>=` for equal, less or equal and greater or equal, respectively, and a constant. 75The constraint :math:`x+y \leq 10` can be easily included within model :code:`m`: 76 77.. code-block:: python 78 79 m += x + y <= 10 80 81Summation expressions can be implemented with the function :py:func:`~mip.xsum`. 82If for a knapsack problem with :math:`n` items, each one with weight :math:`w_i`, we would like to include a constraint to select items with binary variables :math:`x_i` respecting the knapsack capacity :math:`c`, then the following code could be used to include this constraint within the model :code:`m`: 83 84.. code-block:: python 85 86 m += xsum(w[i]*x[i] for i in range(n)) <= c 87 88Conditional inclusion of variables in the summation is also easy. 89Let's say that only even indexed items are subjected to the capacity constraint: 90 91.. code-block:: python 92 93 m += xsum(w[i]*x[i] for i in range(n) if i%2 == 0) <= c 94 95Finally, it may be useful to name constraints. 96To do so is straightforward: include the constraint's name after the linear expression, separating it with a comma. 97An example is given below: 98 99.. code-block:: python 100 101 m += xsum(w[i]*x[i] for i in range(n) if i%2 == 0) <= c, 'even_sum' 102 103As with variables, reference of constraints can be retrieved by their names. 104Model function :func:`~mip.Model.constr_by_name` is responsible for this: 105 106.. code-block:: python 107 108 constraint = m.constr_by_name('even_sum') 109 110Objective Function 111~~~~~~~~~~~~~~~~~~ 112 113By default a model is created with the *Minimize* sense. 114The following code alters the objective function to :math:`\sum_{i=0}^{n-1} c_ix_i` by setting the :attr:`~mip.Model.objective` attribute of our example model :code:`m`: 115 116.. code-block:: python 117 118 m.objective = xsum(c[i]*x[i] for i in range(n)) 119 120To specify whether the goal is to *Minimize* or *Maximize* the objetive function, two useful functions were included: :func:`~mip.minimize` and :func:`~mip.maximize`. Below are two usage examples: 121 122.. code-block:: python 123 124 m.objective = minimize(xsum(c[i]*x[i] for i in range(n))) 125 126.. code-block:: python 127 128 m.objective = maximize(xsum(c[i]*x[i] for i in range(n))) 129 130You can also change the optimization direction by setting the :attr:`~mip.Model.sense` model property to :code:`MINIMIZE` or :code:`MAXIMIZE`. 131 132.. _save-label: 133 134Saving, Loading and Checking Model Properties 135--------------------------------------------- 136 137Model methods :func:`~mip.Model.write` and :func:`~mip.Model.read` can be used to save and load, respectively, 138MIP models. 139Supported file formats for models are the `LP file format 140<https://www.ibm.com/support/knowledgecenter/SSSA5P_12.9.0/ilog.odms.cplex.help/CPLEX/GettingStarted/topics/tutorials/InteractiveOptimizer/usingLPformat.html>`_, which is more readable and suitable for debugging, and the `MPS file format <https://en.wikipedia.org/wiki/MPS_(format)>`_, which is recommended for extended compatibility, since it is an older and more widely adopted format. 141When calling the :meth:`~mip.Model.write` method, the file name extension (.lp or .mps) is used to define the file format. 142Therefore, to save a model :code:`m` using the lp file format to the file model.lp we can use: 143 144.. code-block:: python 145 146 m.write('model.lp') 147 148Likewise, we can read a model, which results in creating variables and constraints from the LP or MPS file read. 149Once a model is read, all its attributes become available, like the number of variables, constraints and non-zeros in the constraint matrix: 150 151.. code-block:: python 152 153 m.read('model.lp') 154 print('model has {} vars, {} constraints and {} nzs'.format(m.num_cols, m.num_rows, m.num_nz)) 155 156Optimizing and Querying Optimization Results 157-------------------------------------------- 158 159MIP solvers execute a Branch-&-Cut (BC) algorithm that in *finite time* will provide the optimal solution. 160This time may be, in many cases, too large for your needs. 161Fortunately, even when the complete tree search is too expensive, results are often available in the beginning of the search. 162Sometimes a feasible solution is produced when the first tree nodes are processed and a lot of additional effort is spent improving the *dual bound*, which is a valid estimate for the cost of the optimal solution. 163When this estimate, the lower bound for minimization, matches exactly the cost of the best solution found, the upper bound, the search is concluded. 164For practical applications, usually a truncated search is executed. 165The :func:`~mip.Model.optimize` method, that executes the optimization of a formulation, accepts optionally processing limits as parameters. 166The following code executes the branch-&-cut algorithm to solve a model :code:`m` for up to 300 seconds. 167 168.. code-block:: python 169 :linenos: 170 171 m.max_gap = 0.05 172 status = m.optimize(max_seconds=300) 173 if status == OptimizationStatus.OPTIMAL: 174 print('optimal solution cost {} found'.format(m.objective_value)) 175 elif status == OptimizationStatus.FEASIBLE: 176 print('sol.cost {} found, best possible: {}'.format(m.objective_value, m.objective_bound)) 177 elif status == OptimizationStatus.NO_SOLUTION_FOUND: 178 print('no feasible solution found, lower bound is: {}'.format(m.objective_bound)) 179 if status == OptimizationStatus.OPTIMAL or status == OptimizationStatus.FEASIBLE: 180 print('solution:') 181 for v in m.vars: 182 if abs(v.x) > 1e-6: # only printing non-zeros 183 print('{} : {}'.format(v.name, v.x)) 184 185Additional processing limits may be used: :code:`max_nodes` restricts the maximum number of explored nodes in the search tree and :code:`max_solutions` finishes the BC algorithm after a number of feasible solutions are obtained. 186It is also wise to specify how tight the bounds should be to conclude the search. 187The model attribute :attr:`~mip.Model.max_mip_gap` specifies the allowable percentage deviation of the upper bound from the lower bound for concluding the search. 188In our example, whenever the distance of the lower and upper bounds is less or equal 5\% (see line 1), the search can be finished. 189 190The :meth:`~mip.Model.optimize` method returns the status 191(:class:`~mip.OptimizationStatus`) of the BC search: 192:attr:`~mip.OptimizationStatus.OPTIMAL` if the search was concluded and the optimal solution was found; :attr:`~mip.OptimizationStatus.FEASIBLE` if a feasible solution was found but there was no 193time to prove whether this solution was optimal or not; 194:attr:`~mip.OptimizationStatus.NO_SOLUTION_FOUND` if in the truncated search no solution was found; :attr:`~mip.OptimizationStatus.INFEASIBLE` or :attr:`~mip.OptimizationStatus.INT_INFEASIBLE` if no feasible solution exists for the model; 195:attr:`~mip.OptimizationStatus.UNBOUNDED` if there are missing constraints or :attr:`~mip.OptimizationStatus.ERROR` if 196some error occurred during optimization. In the example above, if a feasible 197solution is available (line 8), variables which have value different from zero 198are printed. Observe also that even when no feasible solution is available 199the dual bound (lower bound in the case of minimization) is available (line 8): if a truncated execution was performed, i.e., the solver stopped due to the time limit, you can check this dual bound which is an estimate of 200the quality of the solution found checking the :attr:`~mip.Model.gap` 201property. 202 203During the tree search, it is often the case that many different feasible solutions 204are found. The solver engine stores this solutions in a solution pool. The following code 205prints all routes found while optimizing the :ref:`Traveling Salesman Problem <tsp-label>`. 206 207 208.. code-block:: python 209 210 for k in range(model.num_solutions): 211 print('route {} with length {}'.format(k, model.objective_values[k])) 212 for (i, j) in product(range(n), range(n)): 213 if x[i][j].xi(k) >= 0.98: 214 print('\tarc ({},{})'.format(i,j)) 215 216 217 218Performance Tuning 219~~~~~~~~~~~~~~~~~~ 220 221Tree search algorithms of MIP solvers deliver a set of improved feasible 222solutions and lower bounds. Depending on your application you will 223be more interested in the quick production of feasible solutions than in improved 224lower bounds that may require expensive computations, even if in the long term 225these computations prove worthy to prove the optimality of the solution found. 226The model property :attr:`~mip.Model.emphasis` provides three different settings: 227 2280. default setting: 229 tries to balance between the search of improved feasible 230 solutions and improved lower bounds; 231 2321. feasibility: 233 focus on finding improved feasible solutions in the 234 first moments of the search process, activates heuristics; 235 2362. optimality: 237 activates procedures that produce improved lower bounds, focusing 238 in pruning the search tree even if the production of the first feasible solutions 239 is delayed. 240 241Changing this setting to 1 or 2 triggers the activation/deactivation of 242several algorithms that are processed at each node of the search tree that 243impact the solver performance. Even though in average these settings 244change the solver performance as described previously, depending on your 245formulation the impact of these changes may be very different and it is 246usually worth to check the solver behavior with these different settings 247in your application. 248 249Another parameter that may be worth tuning is the :attr:`~mip.Model.cuts` 250attribute, that controls how much computational effort should be spent in generating 251cutting planes. 252 253 254