{"id":176,"date":"2021-01-20T16:44:21","date_gmt":"2021-01-20T16:44:21","guid":{"rendered":"https:\/\/www.kindsonthegenius.com\/data-science\/?p=176"},"modified":"2021-01-20T16:44:21","modified_gmt":"2021-01-20T16:44:21","slug":"solving-constraints-optimization-problem-with-python","status":"publish","type":"post","link":"https:\/\/www.kindsonthegenius.com\/data-science\/solving-constraints-optimization-problem-with-python\/","title":{"rendered":"Solving Constraints Optimization Problem with Python"},"content":{"rendered":"

Constraint Optimization is the class of problems that requires identifying feasible solution among a very large set of possibilities. The problem can be modelled in terms of contraints<\/p>\n

Constraint Optmization(also called Constraint Programming – CP)<\/a> is based on finding a feasible solution(feasibility) rather than finding an optimal solution(optimization). Unlike normal linear, programming, the focus here is on the constraints rather than on the cost function.<\/p>\n

 <\/p>\n

Employee Scheduling Example<\/strong><\/p>\n

A typical example of where CP is applied is in the employee scheduling. For instance, a company that runs 3 8-hour daily shift for its employee. And there are four employees. Three of the 4 employees need to be assigned to different shift each day while the 4th employee has a day off. Here you can see that the number of possible schedules is much – 4! = 4 * 3 * 2 * 1 = 24. For a week we have 247. That is very much! Therefore, to narrow down the number, we need to apply some constraints.For example, each employee must work certain minimum number of days in a week. CP allows us to keep track of solutions that remains feasible as constraints are added.<\/p>\n

 <\/p>\n

A Simple Example with Python<\/strong><\/p>\n

There are three variables x, y and z that could assume on of three values: 0, 1, 2.<\/p>\n

There is once constraint that says: x \u2260 y<\/p>\n

Solution<\/strong><\/p>\n

We follow 5 steps to solve this problem in Python<\/p>\n

Step 1<\/strong>: Declare your model<\/p>\n

You will first import the cp_model from ortools.sat.python<\/em><\/p>\n

# Declare the model<\/span>\r\nfrom<\/span> ortools.sat.python<\/span> import<\/span> cp_model\r\nmodel =<\/span> cp_model.<\/span>CpModel()\r\n<\/pre>\n
 <\/p>\n
Step 2:<\/strong> Define the variables: x, y and z<\/p>\n
# Define your variables<\/span>\r\nnum_vars =<\/span> 3<\/span>\r\nx =<\/span> model.<\/span>NewIntVar(0<\/span>, num_vars -<\/span> 1<\/span>, 'x'<\/span>)\r\ny =<\/span> model.<\/span>NewIntVar(0<\/span>, num_vars -<\/span> 1<\/span>, 'y'<\/span>)\r\nz =<\/span> model.<\/span>NewIntVar(0<\/span>, num_vars -<\/span> 1<\/span>, 'z'<\/span>)\r\n<\/pre>\n
 <\/p>\n
Step 3:<\/strong> Add the constraint<\/p>\n
In this case, we have only one constraint: x \u2260 y<\/p>\n
# Add the constraint<\/span>\r\nmodel.<\/span>Add(x !=<\/span> y)\r\n<\/pre>\n
 <\/p>\n
Step 4:<\/strong> Invoke the solver<\/p>\n
You must call\u00a0 the CpSolve()<\/em> method of the solver<\/p>\n
# Invoke the solver<\/span>\r\nsolver =<\/span> cp_model.<\/span>CpSolver()\r\nstatus =<\/span> solver.<\/span>Solve(model)\r\n<\/pre>\n
 <\/p>\n
Step 5:<\/strong> Display your results<\/p>\n
In this case we would display the optimal solution<\/p>\n
# Display the results<\/span>\r\nif<\/span> status ==<\/span> cp_model.<\/span>OPTIMAL:\r\n    print<\/span>('x = <\/span>%i<\/span>'<\/span> %<\/span>solver.<\/span>Value(x))\r\n    print<\/span>('y = <\/span>%i<\/span>'<\/span> %<\/span>solver.<\/span>Value(y))\r\n    print<\/span>('z = <\/span>%i<\/span>'<\/span> %<\/span>solver.<\/span>Value(z))\r\n<\/pre>\n
The output is shown below:<\/p>\n
x = 1\r\ny = 0\r\nz = 0\r\n<\/pre>\n
 <\/p>\n
The complete program shown below displays all the the results, not just the optimal one.<\/p>\n
\"Contraints<\/a>
Contraints Programming in Python<\/figcaption><\/figure>\n","protected":false},"excerpt":{"rendered":"
Constraint Optimization is the class of problems that requires identifying feasible solution among a very large set of possibilities. The problem can be modelled in … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[29],"tags":[30],"class_list":["post-176","post","type-post","status-publish","format-standard","hentry","category-constraint-optimization","tag-constraint-optimization"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts\/176","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/comments?post=176"}],"version-history":[{"count":2,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts\/176\/revisions"}],"predecessor-version":[{"id":179,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts\/176\/revisions\/179"}],"wp:attachment":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/media?parent=176"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/categories?post=176"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/tags?post=176"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}