Using it with PuLP
**************************

.. highlight:: python

Copied from :py:mod:`pulp`:

   PuLP is a free open source software written in Python. It is used to describe optimisation problems as mathematical models. PuLP can then call any of numerous external LP solvers (CBC, GLPK, CPLEX, Gurobi etc) to solve this model and then use python commands to manipulate and display the solution.


Nomenclature
=========================

.. glossary::

   Variable declaration
      A group of decision variables that share the same naming and significance. In `PuLP` they are all created within a single call to :py:meth:`pulp.LpVariable.dicts` and they are all accessed by slicing the created `python` variable as a dictionary. An optimization problem can have one variable declaration but thousands of variables.

   Variable domain
   	The complete space over which variables in a single variable declaration are created. The length of the domain is the number of variables in the declaration. Each variable declaration has its own domain and is indicated with the argument `index` when calling the function :py:meth:`pulp.LpVariable.dicts`. It usually consists of some kind of iterator where all its elements should be unique.

When using :py:mod:`pulp`, I use the following guidelines:

1. Use :py:meth:`pulp.LpVariable.dicts` for variable declaration, unless there is a very good reason not to.
2. Use a list of tuples to declare the variable domain.
3. Use `pytups` to index parts of the domain for clean, pretty and fast constraint generation.


Example: Scheduling problem
=============================

This example was taken with permission from the Naval Postgraduate School course Mathematical Programming given by Matt Carlyle in 2019.

Assume we are given a set of jobs :math:`j` with processing times :math:`p_j`. For a single machine non-preemptive scheduling problem (which we assume here), a schedule of the jobs :math:`N` is given by specifying a start time, :math:`Y_j` , for each job. If job j starts at time :math:`Y_j`, it is processing during the time interval :math:`[Y_j , Y_j + p_j ]`. A schedule is feasible if no two jobs have overlapping processing times.

This means that, for every pair of jobs :math:`i` and :math:`j`, we have that either :math:`Y_j \geq Y_i +p_i` , or :math:`Y_i \geq Y_j +p_j`.

Job :math:`j` will complete at time :math:`C_j =(Y_j + p_j )`, and if it also has an associated due date, :math:`d_j` , its tardiness, :math:`T_j` , is defined to be:

.. math::
   :nowrap:

   \begin{eqnarray}
      T_j    & = & (C_j - d_j)^+ \\
      T_j    & = & (Y_j + p_j - d_j)^+
   \end{eqnarray}

If we are given a set of weights, :math:`w_j` , which indicate a relative importance between individual jobs, we can calculate the total weighted tardiness of a given feasible schedule:

.. math::
   :nowrap:

   \begin{eqnarray}
      TWT    & = & \sum_{j \in N} w_j T_j \\
      TWT    & = & \sum_{j \in N} w_j (Y_j + p_j - d_j)^+
   \end{eqnarray}

The objective is to schedule all the jobs without overlapping them and minimizing the total weighted tardiness :math:`TWT`.


Mathematical formulation
===================================

The following is just one of many possible formulations to solve this problem.

SETS
      					
======================================  ====================================
:math:`j \in J`		                     jobs
:math:`k \in K = \{1, ..., C_{max}\}`   	periods
======================================  ====================================

DATA [UNITS]
     					
================ ====================================================
:math:`p_j`			processing time of job j [periods]
:math:`d_j`  		due date of job j [period]
:math:`w_j`			weight or priority of job j [dimensionless]
================ ====================================================


DERIVED DATA
   					
=================    =======================================================================================================
:math:`C_{max}`      Size of planning horizon.
:math:`JK`           Al possible starting combinations (j, k) such that job :math:`j \in J` can start in period :math:`k \in K`.
:math:`K_j`          Al possible starting periods for job :math:`j \in J`.
:math:`t_{jk}`       Penalty for starting job :math:`j \in J` in period :math:`k \in K`.
:math:`K2_{jk}`      Periods that become unavailable by starting job :math:`j` in period :math:`k \in K`.
:math:`JK_{k2}`      All possible starts of jobs :math:`(j, k) \in JK` that make period :math:`k2 \in K` unavailable.
=================    =======================================================================================================

.. math::
   :nowrap:

   \begin{eqnarray}
      &C_{max} 	&= &\sum_{j \in J} p_j \\
      &JK 		   &= &\{(j \in J, k \in K) \mid k + p_j \leq C_{max} \} \\
      &K_j 		   &= &\{k \in K \mid (j, k) \in JK \} & j \in J \\
      &K2_{jk} 	&= &\{k \in K \mid k \leq k2 \leq k + p_j \} & (j, k) \in JK \\
      &JK_{k2} 	&= &\{(j, k) \in JK \mid k_2 \in K2_{jk} \} & k_2 \in K \\
      &t_{jk} 	   &= &\max\{k + p_j -1 - d_j, 0\} \times w_j & (j, k) \in JK \\
   \end{eqnarray}

DECISION VARIABLES

:math:`X_{jk}`. Binary. 1 if job :math:`j` starts at time slot :math:`k`, 0 otherwise. :math:`(j, k) \in JK`

FORMULATION

.. math::
   :nowrap:

   \begin{eqnarray}
      \min \sum_{(j, k) \in JK} t_{jk} X_{jk} \\
   \end{eqnarray}

Subject to:

.. math::
   :nowrap:

   The first set of constraints enforces that each job is scheduled only once. The second set of constraints guarantees that each period of time is used by only one job.

   \begin{eqnarray}
      & \sum_{k \in K_j} X_{jk} = 1 & j \in J \\
      & \sum_{(j, k) \in JK_{k2}} X_{jk} = 1 & k2 \in K \\
   \end{eqnarray}


Implementation using pulp and pytups
========================================

We import libraries and get input data.

.. literalinclude:: ./../../examples/machine_scheduling.py
   :lines: 1-8

We then calculate intermediate sets and parameters. Note the use of `pytups` functions to filter and convert from tuple lists to dictionaries.

.. literalinclude:: ./../../examples/machine_scheduling.py
   :lines: 11-39

We now create the PuLP model and solve it.

.. literalinclude:: ./../../examples/machine_scheduling.py
   :lines: 42-62

We get the solution from the variable contents. Not how we also use `pytups` to extract the content from the variable.

.. literalinclude:: ./../../examples/machine_scheduling.py
   :lines: 65-73

Finally, we do some tests on the solution using `pytups` to guarantee the solution is feasible:

.. literalinclude:: ./../../examples/machine_scheduling.py
   :lines: 77-85

The whole code is shown below:

.. literalinclude:: ./../../examples/machine_scheduling.py