{"id":164,"date":"2021-01-20T14:25:57","date_gmt":"2021-01-20T14:25:57","guid":{"rendered":"https:\/\/www.kindsonthegenius.com\/data-science\/?p=164"},"modified":"2021-01-20T14:25:57","modified_gmt":"2021-01-20T14:25:57","slug":"an-mip-problem-with-python-with-constraints-define-with-arrays","status":"publish","type":"post","link":"https:\/\/www.kindsonthegenius.com\/data-science\/an-mip-problem-with-python-with-constraints-define-with-arrays\/","title":{"rendered":"An MIP Problem with Python with Constraints Define with Arrays"},"content":{"rendered":"
In the previous tutorial, we learnt how to solve a Mixed Integer Program(MIP) problem in Python. In that example there were very few constraints and so we manually specified them.<\/p>\n
We would now look at situation where there are many constraints such that they have to be represented as an array. Let’s take an example:<\/p>\n
Example 1 – Maximize the function 7x1<\/sub>\u00a0+ 8x2<\/sub>\u00a0+ 2x3<\/sub>\u00a0+ 9x4<\/sub>\u00a0+ 6x5<\/sub><\/em> with respect to the following constraints:<\/strong><\/p>\n
\n\n
\n
5x1<\/sub><\/em><\/td>\n
+<\/td>\n
7x2<\/sub><\/em><\/td>\n
+<\/td>\n
9x3<\/sub><\/em><\/td>\n
+<\/td>\n
2x4<\/sub><\/em><\/td>\n
+<\/td>\n
1x5<\/sub><\/em><\/td>\n
\u2264<\/td>\n
250<\/td>\n<\/tr>\n
\n
18x1<\/sub><\/em><\/td>\n
+<\/td>\n
4x2<\/sub><\/em><\/td>\n
–<\/td>\n
9x3<\/sub><\/em><\/td>\n
+<\/td>\n
10x4<\/sub><\/em><\/td>\n
+<\/td>\n
12x5<\/sub><\/em><\/td>\n
\u2264<\/td>\n
285<\/td>\n<\/tr>\n
\n
4x1<\/sub><\/em><\/td>\n
+<\/td>\n
7x2<\/sub><\/em><\/td>\n
+<\/td>\n
3x3<\/sub><\/em><\/td>\n
+<\/td>\n
8x4<\/sub><\/em><\/td>\n
+<\/td>\n
5x5<\/sub><\/em><\/td>\n
\u2264<\/td>\n
211<\/td>\n<\/tr>\n
\n
5x1<\/sub><\/em><\/td>\n
+<\/td>\n
13x2<\/sub><\/em><\/td>\n
+<\/td>\n
16x3<\/sub><\/em><\/td>\n
+<\/td>\n
3x4<\/sub><\/em><\/td>\n
–<\/td>\n
7x5<\/sub><\/em><\/td>\n
\u2264<\/td>\n
315<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Also x1<\/sub><\/em>, x2<\/sub><\/em>, x3<\/sub><\/em>, x4<\/sub><\/em>, x5 <\/sub><\/em>are integers<\/p>\n
Solution:<\/strong><\/p>\n
We would follow the same 5 step procedure we followed previously<\/p>\n
First let’s represent the given problem using the following:<\/p>\n
\n
a 2-d array of coefficients – coefs<\/li>\n
array of the maximums(right-hand-side) – maxs<\/li>\n
array of unknowns (x1, x2,…, x5) – unknowns<\/li>\n
array of cost function coefficients – cost_fn<\/li>\n<\/ul>\n
# IMPORT THE SOLVER<\/span>\r\nfrom<\/span> ortools.linear_solver<\/span> import<\/span> pywraplp\r\nsolver =<\/span> pywraplp.<\/span>Solver.<\/span>CreateSolver('SCIP'<\/span>)\r\n<\/pre>\n
<\/p>\n
Step 2<\/strong> – Declare the variables<\/p>\n
To do this, we loop through the unknown and populate the variables array as shown below: \n<\/p>\n
# DECLARE THE VARIABLES<\/span>\r\nvariables =<\/span> [[]] *<\/span> len<\/span>(unknowns)\r\nfor<\/span> i in<\/span> range<\/span>(0<\/span>, len<\/span>(unknowns)):\r\n variables[i] =<\/span> solver.<\/span>IntVar(0<\/span>, solver.<\/span>infinity(), unknowns[i])\r\n<\/pre>\n
<\/p>\n
Step 3<\/strong> – Create the contraints.<\/p>\n
We do this by looping\u00a0 through the constraints with an outer loop. Then, for each iteration, create a new constraint. Then we use an inner loop to iterate through the coefficients and assign the coefficients of each variable.<\/p>\n
Step 4<\/strong> – Setup the Objective function<\/p>\n
To do this, we loop through the cost_fn array and assign coefficients to the corresponding variable<\/p>\n
# DEFINE THE OBJECTIVE FUNCTION 7x1\u00a0+ 8x2\u00a0+ 2x3\u00a0+ 9x4\u00a0+ 6x5<\/span>\r\nobj =<\/span> solver.<\/span>Objective()\r\nfor<\/span> i in<\/span> range<\/span>(0<\/span>, len<\/span>(cost_fn)):\r\n obj.<\/span>SetCoefficient(variables[i], cost_fn[i])\r\n\r\nobj.<\/span>SetMaximization() # set the problem goal as maximization<\/span>\r\n<\/pre>\n
<\/p>\n
Step 5<\/strong> – Call the Solver() and print the result<\/p>\n
# CALL THE SOLVER AND SHOW THE RESULT<\/span>\r\nstatus =<\/span> solver.<\/span>Solve()\r\nprint<\/span>('Objective value = '<\/span>, obj.<\/span>Value())\r\n\r\n# PRINT THE RESULTS<\/span>\r\nfor<\/span> i in<\/span> range<\/span>(0<\/span>, len<\/span>(unknowns)):\r\n print<\/span>('<\/span>%s<\/span> = <\/span>%f<\/span>'<\/span> %<\/span>(unknowns[i], variables[i].<\/span>solution_value()))\r\n<\/pre>\n
![\"MIP](\"https:\/\/www.kindsonthegenius.com\/data-science\/wp-content\/uploads\/sites\/12\/2021\/01\/Screenshot-2021-01-20-at-15.24.18.png\")
<\/a>