import sys
try:
    import docplex.mp
except:
    raise Exception('Please install docplex. See https://pypi.org/project/docplex/')

"""
Explanation: Benders decomposition with decision optimization
This tutorial includes everything you need to set up decision optimization engines, build a mathematical programming model, then use the benders decomposition on it.
When you finish this tutorial, you'll have a foundational knowledge of Prescriptive Analytics.

This notebook is part of Prescriptive Analytics for Python
It requires either an installation of CPLEX Optimizers or it can be run on IBM Cloud Pak for Data as a Service (Sign up for a free IBM Cloud account
and you can start using IBM Cloud Pak for Data as a Service right away).
CPLEX is available on <i>IBM Cloud Pack for Data</i> and <i>IBM Cloud Pak for Data as a Service</i>:
   - <i>IBM Cloud Pak for Data as a Service</i>: Depends on the runtime used:
        - <i>Python 3.x</i> runtime: Community edition
        - <i>Python 3.x + DO</i> runtime: full edition
   - <i>Cloud Pack for Data</i>: Community edition is installed by default. Please install DO addon in Watson Studio Premium for the full edition

Table of contents:

Describe the business problem
How decision optimization (prescriptive analytics) can help
Use decision optimization
Step 1: Import the library
Step 2: Set up the prescriptive model
Step 3: Solve the problem with default CPLEX algorithm
Step 4: Apply a Benders strategy
Step 5: Use the CPLEX annotations to guide CPLEX in your Benders decomposition


Summary


Benders decomposition is an approach to solve mathematical programming problems with a decomposable structure.
Starting with 12.7, CPLEX can decompose the model into a single master and (possibly multiple) subproblems. 
To do so, CPLEX can use of annotations that you supply for your model or can automatically do the decomposition. 
This approach can be applied to mixed-integer linear programs (MILP). For certain types of problems, this approach can offer significant performance improvements.
Note:
If your problem does not match such decomposition, CPLEX will raise an error at solve time.
CPLEX will produce an error CPXERR_BAD_DECOMPOSITION if the annotated decomposition does not yield disjoint subproblems
Learn more bout Benders decomposition
Directs a reader to more sources about Benders algorithm.
The popular acceptance of the original paper suggesting a decomposition or partitioning of a model to support solution of mixed integer programs gave rise to "Benders algorithm" as the name.

J. Benders. <i>Partitioning procedures for solving mixed-variables programming problems in Numerische Mathematik, volume 4, issue 1, pages 238–252, 1962</i>

Other researchers developed the theory of cut-generating linear programs (CGLP) to further this practice.
* M. Fischetti, D. Salvagnin, A. Zanette. <i>A note on the selection of Benders’ cuts in Mathematical Programming, series B, volume 124, pages 175-182, 2010</i>
Still others applied the practice to practical operations research. This technical report describes Benders algorithm in "modern" terms and offers implementation hints.
* M. Fischetti, I. Ljubic, M. Sinnl. <i>Benders decomposition without separability: a computational study for capacitated facility location problems in Technical Report University of Padova, 2016</i>
How  decision optimization can help


Prescriptive analytics (decision optimization) technology recommends actions that are based on desired outcomes.  It takes into account specific scenarios, resources, and knowledge of past and current events. With this insight, your organization can make better decisions and have greater control of business outcomes.  


Prescriptive analytics is the next step on the path to insight-based actions. It creates value through synergy with predictive analytics, which analyzes data to predict future outcomes.  


Prescriptive analytics takes that insight to the next level by suggesting the optimal way to handle that future situation. Organizations that can act fast in dynamic conditions and make superior decisions in uncertain environments gain a strong competitive advantage.
<br/>


<u>With prescriptive analytics, you can:</u> 

Automate the complex decisions and trade-offs to better manage your limited resources.
Take advantage of a future opportunity or mitigate a future risk.
Proactively update recommendations based on changing events.
Meet operational goals, increase customer loyalty, prevent threats and fraud, and optimize business processes.

Use decision optimization
Step 1: Import the library
Run the following code to import Decision Optimization CPLEX Modeling library.  The DOcplex library contains the two modeling packages, Mathematical Programming and Constraint Programming, referred to earlier.
End of explanation
"""


d1 = 25
d2 = 35

Costs = [[20,  15,  22,  27,  13,  4,  15,  6,  15,  22,  25,  13,  7,  28,  14,  5,  8,  1,  17,  3,  19,  17,  22,  12,  14],
   [2,  15,  16,  16,  10,  13,  4,  2,  6,  29,  10,  8,  20,  11,  8,  11,  28,  17,  10,  29,  3,  24,  12,  11,  11],
   [13,  14,  6,  17,  14,  13,  8,  29,  19,  26,  22,  0,  8,  29,  15,  20,  5,  20,  26,  17, 24, 10, 24, 9, 1],
   [7, 27, 24, 3, 4, 23, 11, 9, 18, 1, 29, 24, 16, 9, 8, 3, 18, 24, 10, 12, 1, 3, 15, 29, 3],
   [25, 26, 29, 6, 24, 8, 2, 10, 17, 0, 4, 7, 2, 17, 2, 27, 24, 20, 18, 5, 5, 2, 21, 26, 20],
   [29, 5, 15, 5, 4, 26, 18, 8, 2, 14, 13, 6, 14, 28, 16, 28, 23, 8, 5, 8, 10, 28, 17, 0, 23],
   [12, 16, 10, 16, 17, 10, 29, 11, 28, 22, 25, 8, 27, 12, 10, 28, 7, 5, 3, 9, 18, 10, 15, 16, 2],
   [12, 9, 14, 23, 26, 4, 3, 3, 22, 12, 11, 9, 19, 5, 6, 16, 1, 1, 9, 20, 23, 23, 27, 4, 11],
   [18, 13, 28, 29, 3, 28, 16, 11, 9, 2, 7, 20, 13, 23, 6, 10, 3, 16, 14, 2, 15, 17, 1, 19, 27],
   [29, 17, 17, 14, 21, 18, 8, 21, 9, 20, 14, 6, 29, 24, 24, 4, 18, 16, 21, 24, 26, 0, 26, 9, 5],
   [27, 24, 21, 28, 17, 18, 10, 10, 26, 25, 13, 18, 2, 9, 16, 26, 10, 22, 5, 17, 15, 0, 9, 0, 16],
   [13, 15, 17, 21, 25, 9, 22, 13, 20, 15, 1, 17, 18, 10, 2, 27, 19, 21, 14, 26, 29, 13, 28, 28, 15],
   [16, 12, 2, 2, 9, 27, 11, 14, 12, 2, 14, 29, 3, 12, 18, 6, 7, 9, 1, 5, 19, 14, 11, 29, 4],
   [1, 15, 27, 29, 16, 17, 10, 10, 17, 19, 6, 10, 20, 20, 19, 10, 19, 26, 15, 7, 20, 19, 13, 3, 22],
   [22, 14, 12, 3, 22, 6, 15, 3, 6, 10, 9, 13, 11, 21, 6, 19, 29, 4, 5, 21, 7, 12, 13, 11, 22],
   [9, 27, 22, 29, 11, 14, 1, 19, 21, 2, 4, 13, 17, 9, 10, 17, 13, 8, 24, 13, 26, 27, 23, 4, 21],
   [3, 14, 26, 18, 17, 3, 1, 11, 13, 8, 22, 3, 18, 26, 17, 15, 22, 10, 19, 23, 13, 14, 17, 18, 27],
   [21, 14, 1, 28, 28, 0, 0, 29, 12, 23, 22, 17, 19, 2, 10, 19, 4, 18, 28, 13, 27, 12, 9, 29, 22],
   [29, 3, 20, 5, 5, 23, 28, 16, 1, 8, 26, 23, 11, 11, 21, 17, 13, 21, 3, 8, 6, 15, 18, 6, 24],
   [14, 20, 26, 10, 17, 20, 5, 9, 25, 20, 14, 22, 5, 12, 0, 18, 7, 0, 8, 15, 21, 12, 26, 7, 21],
   [7, 7, 1, 9, 24, 29, 0, 3, 29, 24, 1, 6, 14, 0, 11, 5, 21, 12, 15, 1, 25, 4, 7, 17, 16],
   [8, 18, 15, 6, 1, 22, 26, 13, 19, 20, 12, 15, 19, 27, 13, 3, 22, 22, 22, 20, 0, 4, 24, 13, 25],
   [14, 6, 29, 23, 8, 5, 4, 18, 21, 29, 18, 2, 2, 3, 7, 13, 12, 9, 2, 18, 26, 3, 18, 7, 7],
   [5, 8, 4, 8, 25, 4, 6, 20, 14, 21, 18, 16, 15, 11, 7, 8, 20, 27, 22, 7, 5, 8, 24, 11, 8],
   [0, 8, 29, 25, 29, 0, 12, 25, 19, 9, 19, 25, 27, 21, 2, 23, 2, 25, 17, 6, 0, 6, 15, 2, 15],
   [23, 24, 10, 26, 7, 5, 5, 26, 1, 16, 22, 8, 24, 9, 16, 17, 1, 26, 20, 23, 18, 20, 23, 2, 19],
   [16, 3, 9, 21, 15, 29, 8, 26, 20, 12, 18, 27, 29, 15, 24, 9, 17, 24, 3, 5, 21, 28, 7, 1, 12],
   [1, 11, 21, 1, 13, 14, 16, 14, 17, 25, 18, 9, 19, 26, 1, 13, 15, 6, 14, 10, 12, 19, 0, 15, 7],
   [20, 14, 7, 5, 8, 16, 12, 0, 5, 14, 18, 16, 24, 27, 20, 7, 11, 3, 16, 8, 2, 2, 4, 0, 3],
   [26, 19, 27, 29, 8, 9, 8, 10, 18, 4, 6, 0, 5, 17, 12, 18, 17, 17, 13, 0, 16, 12, 18, 19, 16],
   [3, 12, 11, 28, 3, 2, 14, 14, 17, 29, 18, 14, 19, 24, 9, 27, 4, 19, 6, 24, 19, 3, 28, 20, 4],
   [2, 0, 21, 14, 21, 12, 27, 6, 20, 29, 13, 21, 23, 0, 20, 4, 11, 27, 3, 11, 21, 11, 21, 4, 17],
   [20, 26, 5, 8, 18, 14, 12, 12, 24, 3, 8, 0, 25, 16, 19, 21, 7, 4, 23, 21, 20, 28, 6, 21, 19],
   [16, 18, 9, 1, 9, 7, 14, 6, 28, 26, 3, 14, 27, 4, 9, 9, 1, 9, 24, 3, 14, 13, 18, 3, 27],
   [1, 19, 7, 20, 26, 27, 0, 7, 4, 0, 13, 8, 10, 17, 14, 19, 21, 21, 14, 15, 22, 14, 5, 27, 0]];

R1 = range(1,d1)
R2 = range(1,d2);

dim  = range(1,d1*d2+1)

"""
Explanation: A restart of the kernel might be needed.
Step 2: Set up the prescriptive model
We will write a toy model just in order to show how to use the annotation api.
This model is not important: it just matche a benders decomposition, that is CPLEX can apply its new algorithm without any error.
The aim of this notebook is to discover and learn how to successfully apply Benders, not to see huge performance differences between a standard solve and a Benders based solve.
End of explanation
"""


# first import the Model class from docplex.mp
from docplex.mp.model import Model

m = Model(name='benders', log_output=True)

X = m.continuous_var_dict([(i,j) for i in R2 for j in R1])
Y = m.integer_var_dict(R1, 0, 1)


bendersPartition = {(i,j) : i for i in R2 for j in R1}

m.minimize( m.sum( Costs[i][j]*X[i,j] for i in R2 for j in R1) + sum(Y[i] for i in R1) )


m.add_constraints( m.sum( X[i,j] for j in R1) ==1 for i in R2)
    
m.add_constraints( X[i,j] - Y[j] <= 0 for i in R2 for j in R1)

"""
Explanation: Create one model instance, with a name. We set the log output to true such that we can see when CPLEX enables the Benders algorithm.
End of explanation
"""


m.print_information()

"""
Explanation: Solve with Decision Optimization
If you're using a Community Edition of CPLEX runtimes, depending on the size of the problem, the solve stage may fail and will need a paying subscription or product installation. On IBM Cloud Pak for Data as a Service, you need to switch the jupyter environment to Python 3.x + DO.
You will get the best solution found after n seconds, thanks to a time limit parameter.
End of explanation
"""


msol = m.solve()
assert msol is not None, "model can't solve"
m.report()

"""
Explanation: Step 3: Solve the problem with default CPLEX algorithm
End of explanation
"""


obj1 = m.objective_value

"""
Explanation: Inspect the CPLEX Log.
If you inspect the CPLEX, you will see that it is a very standard log.
CPLEX needed 63 iterations to solve it.
End of explanation
"""


m.parameters.benders.strategy = 3

m.print_information()

"""
Explanation: Step 4: Apply a Benders strategy
CPLEX implements a default Benders decomposition in certain situations.
If you want CPLEX to apply a Benders strategy as it solves your problem, but you do not specify cpxBendersPartition annotations yourself, CPLEX puts all integer variables in master and continuous variables into subproblems. 
If there are no integer variables in your model, or if there are no continuous variables in your model, CPLEX raises an error stating that it cannot automatically decompose the model to apply a Benders strategy.
You just need to set the Benders strategy parameter.
CPLEX supports 4 values for this parameter, from -1 to 3:
* OFF (default value) will ignore Benders.
* AUTO, USER, WORKERS, FULL will enable Benders.
Refer to the CPLEX documentation to understand the differences between the 4 values that trigger it.
End of explanation
"""


msol = m.solve(clean_before_solve=True)
assert msol is not None, "model can't solve"
m.report()

"""
Explanation: We call cplex solve, but with the <i>clean_before_solve</i> flag because we want it to forget everything about previous solve and solution.
End of explanation
"""


obj2 = m.objective_value

"""
Explanation: Inspect the CPLEX Log.
Inspect the CPLEX log: you can now see that the log are different and you can see the message
<code>
Benders cuts applied:  3
</code>
which proves CPLEX applied successfully
You can see that CPLEX needed only 61 cumulative iterations, while it needed 63 previously.
End of explanation
"""


m.parameters.benders.strategy = 1

"""
Explanation: Step 5: Use the CPLEX annotations to guide CPLEX in your Benders decomposition
End of explanation
"""


for i in R2:
    for j in R1:
        X[i,j].benders_annotation =  i%2

m.print_information()

msol = m.solve(clean_before_solve=True)
assert msol is not None, "model can't solve"
m.report()

"""
Explanation: Settings benders annotation in docplex is very simple.
You just need to use the <i>benders_annotation</i> property available on variables and constraints to state which worker they belong to.
End of explanation
"""


obj3 = m.objective_value

assert (obj1 == obj2) and (obj2 == obj3)

"""
Explanation: Inspect the CPLEX Log.
Inspect the CPLEX log: you can see that you now need only 57 cumulative iterations instead of 61 with default Benders and 63 with no Benders.
If you look at the <i>Best Bound</i> column, you will also see that the listed sub problems are not the same as CPLEX applied the decomposition provided by the annotations.
End of explanation
"""


