{"id":12345,"date":"2013-06-10T14:26:33","date_gmt":"2013-06-10T13:26:33","guid":{"rendered":"http:\/\/www.decidesoluciones.es\/linealizaciones-programacion-matematica-2\/"},"modified":"2020-03-27T13:21:13","modified_gmt":"2020-03-27T13:21:13","slug":"linearization-mathematical-programming","status":"publish","type":"post","link":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/","title":{"rendered":"Some cases of linearization in mathematical programming"},"content":{"rendered":"<p>In general, studying the properties of linear systems and their solution is much simpler than for non-linear systems. Throughout history, linearization of functions around certain values is a highly used technique to analyse the performance of non-linear systems. Linearization consists thus of finding a linear function that can approximate a given function around a point.<\/p>\n<p>The first step to resolve an <strong>optimization problem<\/strong> is to model reality with mathematical language, that is, rewrite it with variables and their relations. Often, reality leads to non-linear relations between the variables defining it. <strong>In mathematical programming, the concept of linearization consists of approximating a given function using a linear function in an interval<\/strong> to be able to apply techniques and optimization solutions used for linear problems. For anyone not familiar with this concept, a linear function is a first degree polynomial function, in other words, something like:<\/p>\n<p><a href=\"\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter\" src=\"\" alt=\"\" width=\"244\" height=\"59\" \/><\/a><\/p>\n<p>This article aims to describe some of the most frequent cases of linearization used in the modelling of optimization problems.<\/p>\n<ul>\n<li><strong>Continuous Non-Linear Function:<\/strong> A continuous non-linear function can be approached with linear segments so that the result gives a set of linear restrictions to be included in the model.<a href=\"http:\/\/www.decidesoluciones.es\/wp-content\/uploads\/2013\/06\/Aproximacion-lineal2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-medium wp-image-1041\" src=\"\" alt=\"\" width=\"300\" height=\"214\" \/><\/a><\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">The formulation of this linearization can be found in the blog article\u00a0 \u201c<a title=\"How to formulate a Piecewise Linear Function\" href=\"http:\/\/www.decidesoluciones.es\/en\/how-to-formulate-a-piecewise-linear-function\/\" target=\"_blank\" rel=\"noopener noreferrer\">How to Formulate a Piecewise Linear Function<\/a>\u201d.<\/p>\n<ul>\n<li><strong>Discontinuous Functions:<\/strong> Likewise, a non-continuous function can be modelled with finite jump discontinuities with a discontinuous piecewise function. The way this linearization is formulated can be found in the blog article \u201cDiscounts and penalties. Non-continuous PWL\u201d.<\/li>\n<\/ul>\n<ul>\n<li>Discontinuous Ranges of Decision Variables: Many times, the range of a decision variable x is defined with discontinuous intervals such as\u00a0 a\u2264 x \u2264 b or c\u2264 x \u2264d. To represent this situation, a \u03c3 binary variable is introduced so that:<\/li>\n<\/ul>\n<p><a href=\"\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-1033\" src=\"\" alt=\"\" width=\"167\" height=\"59\" \/><\/a><\/p>\n<ul>\n<li><strong>Maximum and minimum:\u00a0<\/strong>Modelling of the condition [math]max_{i in I} (x_{i})[\/math] is represented with the following requirements:<\/li>\n<\/ul>\n<p style=\"padding-left: 60px;\">1. The variable y must be greater than any of the variables x, that is,<\/p>\n<p><a href=\"\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-1053\" src=\"\" alt=\"\" width=\"128\" height=\"42\" \/><\/a><\/p>\n<p style=\"padding-left: 60px;\">2. There is at least one i \u03f5 I so that [math]y=x_{i}[\/math]<\/p>\n<p style=\"padding-left: 60px;\"><span style=\"vertical-align: sub;\">is [math]sigma_{i}[\/math] binary variable so that [math]sigma_{i}=1 hspace{0.3cm}sihspace{0.3cm}yleq x_{i}[\/math], and 0 otherwise, with i \u03f5 I . The following condition assures condition 2 is met.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"padding-left: 30px;\"><span style=\"vertical-align: sub;\"><a href=\"\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-1035\" src=\"\" alt=\"\" width=\"72\" height=\"26\" \/><\/a><\/span><\/p>\n<p style=\"padding-left: 60px;\">You would now just have to model the definition of \u03c3 adding the set of restrictions<\/p>\n<p style=\"padding-left: 30px;\"><a href=\"\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-1036\" src=\"\" alt=\"\" width=\"212\" height=\"31\" \/><\/a><\/p>\n<p style=\"padding-left: 60px;\">Being [math]M_{i}[\/math] higher than [math]y \u2013 x_{i}[\/math]<\/p>\n<p>If the variable y were in the target function in a minimization problem, we could consider eliminating the restrictions of point 2. In practice, this simplification can only be carried out if you are certain you are always going to reach the optimal point, otherwise the condition cannot be met.<\/p>\n<p>Modelling of minimum would be done in a similar way.<\/p>\n<ul>\n<li><strong>Product of variables:<\/strong> The product of two variables can be linearized if one of the two is bounded. The most frequent case is the product of two binary variables \u03b4 = \u03b1\u2219\u03b2 which can be modelled as follows:<\/li>\n<\/ul>\n<p><a href=\"\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-1037\" src=\"\" alt=\"\" width=\"141\" height=\"104\" \/><\/a><\/p>\n<p>There are more cases of linearization and modelling than those described in this article. Trying to write them all down would be absurd, if not impossible. For anyone wanting to learn more about modelling techniques, the book <a href=\"http:\/\/eu.wiley.com\/WileyCDA\/WileyTitle\/productCd-1118443330.html\" target=\"_blank\" rel=\"noopener noreferrer\">\u201cModel Building in Mathematical Programming<\/a>\u201d by H. Paul Williams is very interesting.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In general, studying the properties of linear systems and their solution is much simpler than for non-linear systems. Throughout history, linearization of functions around certain values is a highly used technique to analyse the performance of non-linear systems. <\/p>\n","protected":false},"author":30,"featured_media":24847,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[770,262],"tags":[787],"class_list":["post-12345","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-tecnologia","category-uncategorized","tag-simulacion","category-770","category-262","description-off"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.6 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Some cases of linearization in mathematical programming - Decide<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Some cases of linearization in mathematical programming - Decide\" \/>\n<meta property=\"og:description\" content=\"In general, studying the properties of linear systems and their solution is much simpler than for non-linear systems. Throughout history, linearization of functions around certain values is a highly used technique to analyse the performance of non-linear systems.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/\" \/>\n<meta property=\"og:site_name\" content=\"Decide\" \/>\n<meta property=\"article:published_time\" content=\"2013-06-10T13:26:33+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-03-27T13:21:13+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/decidesoluciones.es\/wp-content\/uploads\/2013\/06\/why-humanizing-algorithms-is-a-good-idea.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"878\" \/>\n\t<meta property=\"og:image:height\" content=\"527\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"decide4AI\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@canaldecide\" \/>\n<meta name=\"twitter:site\" content=\"@canaldecide\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"decide4AI\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/linearization-mathematical-programming\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/linearization-mathematical-programming\\\/\"},\"author\":{\"name\":\"decide4AI\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/#\\\/schema\\\/person\\\/c5a2787a44b67d8f84604a8b87c76075\"},\"headline\":\"Some cases of linearization in mathematical programming\",\"datePublished\":\"2013-06-10T13:26:33+00:00\",\"dateModified\":\"2020-03-27T13:21:13+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/linearization-mathematical-programming\\\/\"},\"wordCount\":546,\"image\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/linearization-mathematical-programming\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/decidesoluciones.es\\\/wp-content\\\/uploads\\\/2013\\\/06\\\/why-humanizing-algorithms-is-a-good-idea.jpg\",\"keywords\":[\"Simulaci\u00f3n\"],\"articleSection\":[\"Tecnolog\u00eda\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/linearization-mathematical-programming\\\/\",\"url\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/linearization-mathematical-programming\\\/\",\"name\":\"Some cases of linearization in mathematical programming - Decide\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/linearization-mathematical-programming\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/linearization-mathematical-programming\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/decidesoluciones.es\\\/wp-content\\\/uploads\\\/2013\\\/06\\\/why-humanizing-algorithms-is-a-good-idea.jpg\",\"datePublished\":\"2013-06-10T13:26:33+00:00\",\"dateModified\":\"2020-03-27T13:21:13+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/#\\\/schema\\\/person\\\/c5a2787a44b67d8f84604a8b87c76075\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/linearization-mathematical-programming\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/linearization-mathematical-programming\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/linearization-mathematical-programming\\\/#primaryimage\",\"url\":\"https:\\\/\\\/decidesoluciones.es\\\/wp-content\\\/uploads\\\/2013\\\/06\\\/why-humanizing-algorithms-is-a-good-idea.jpg\",\"contentUrl\":\"https:\\\/\\\/decidesoluciones.es\\\/wp-content\\\/uploads\\\/2013\\\/06\\\/why-humanizing-algorithms-is-a-good-idea.jpg\",\"width\":878,\"height\":527,\"caption\":\"programacion matem\u00e1tica\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/linearization-mathematical-programming\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Portada\",\"item\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/decide-2\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Some cases of linearization in mathematical programming\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/#website\",\"url\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/\",\"name\":\"Decide\",\"description\":\"Advanced Analytics. Smart Decisions\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/decidesoluciones.es\\\/en\\\/#\\\/schema\\\/person\\\/c5a2787a44b67d8f84604a8b87c76075\",\"name\":\"decide4AI\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/5a16f5f3009bc3081c68bd986b0dd38c75f3bfbf37ebdb7e7cdc0594d063a16c?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/5a16f5f3009bc3081c68bd986b0dd38c75f3bfbf37ebdb7e7cdc0594d063a16c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/5a16f5f3009bc3081c68bd986b0dd38c75f3bfbf37ebdb7e7cdc0594d063a16c?s=96&d=mm&r=g\",\"caption\":\"decide4AI\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Some cases of linearization in mathematical programming - Decide","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/","og_locale":"en_US","og_type":"article","og_title":"Some cases of linearization in mathematical programming - Decide","og_description":"In general, studying the properties of linear systems and their solution is much simpler than for non-linear systems. Throughout history, linearization of functions around certain values is a highly used technique to analyse the performance of non-linear systems.","og_url":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/","og_site_name":"Decide","article_published_time":"2013-06-10T13:26:33+00:00","article_modified_time":"2020-03-27T13:21:13+00:00","og_image":[{"width":878,"height":527,"url":"https:\/\/decidesoluciones.es\/wp-content\/uploads\/2013\/06\/why-humanizing-algorithms-is-a-good-idea.jpg","type":"image\/jpeg"}],"author":"decide4AI","twitter_card":"summary_large_image","twitter_creator":"@canaldecide","twitter_site":"@canaldecide","twitter_misc":{"Written by":"decide4AI","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/#article","isPartOf":{"@id":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/"},"author":{"name":"decide4AI","@id":"https:\/\/decidesoluciones.es\/en\/#\/schema\/person\/c5a2787a44b67d8f84604a8b87c76075"},"headline":"Some cases of linearization in mathematical programming","datePublished":"2013-06-10T13:26:33+00:00","dateModified":"2020-03-27T13:21:13+00:00","mainEntityOfPage":{"@id":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/"},"wordCount":546,"image":{"@id":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/#primaryimage"},"thumbnailUrl":"https:\/\/decidesoluciones.es\/wp-content\/uploads\/2013\/06\/why-humanizing-algorithms-is-a-good-idea.jpg","keywords":["Simulaci\u00f3n"],"articleSection":["Tecnolog\u00eda"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/","url":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/","name":"Some cases of linearization in mathematical programming - Decide","isPartOf":{"@id":"https:\/\/decidesoluciones.es\/en\/#website"},"primaryImageOfPage":{"@id":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/#primaryimage"},"image":{"@id":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/#primaryimage"},"thumbnailUrl":"https:\/\/decidesoluciones.es\/wp-content\/uploads\/2013\/06\/why-humanizing-algorithms-is-a-good-idea.jpg","datePublished":"2013-06-10T13:26:33+00:00","dateModified":"2020-03-27T13:21:13+00:00","author":{"@id":"https:\/\/decidesoluciones.es\/en\/#\/schema\/person\/c5a2787a44b67d8f84604a8b87c76075"},"breadcrumb":{"@id":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/#primaryimage","url":"https:\/\/decidesoluciones.es\/wp-content\/uploads\/2013\/06\/why-humanizing-algorithms-is-a-good-idea.jpg","contentUrl":"https:\/\/decidesoluciones.es\/wp-content\/uploads\/2013\/06\/why-humanizing-algorithms-is-a-good-idea.jpg","width":878,"height":527,"caption":"programacion matem\u00e1tica"},{"@type":"BreadcrumbList","@id":"https:\/\/decidesoluciones.es\/en\/linearization-mathematical-programming\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Portada","item":"https:\/\/decidesoluciones.es\/en\/decide-2\/"},{"@type":"ListItem","position":2,"name":"Some cases of linearization in mathematical programming"}]},{"@type":"WebSite","@id":"https:\/\/decidesoluciones.es\/en\/#website","url":"https:\/\/decidesoluciones.es\/en\/","name":"Decide","description":"Advanced Analytics. Smart Decisions","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/decidesoluciones.es\/en\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/decidesoluciones.es\/en\/#\/schema\/person\/c5a2787a44b67d8f84604a8b87c76075","name":"decide4AI","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/5a16f5f3009bc3081c68bd986b0dd38c75f3bfbf37ebdb7e7cdc0594d063a16c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/5a16f5f3009bc3081c68bd986b0dd38c75f3bfbf37ebdb7e7cdc0594d063a16c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/5a16f5f3009bc3081c68bd986b0dd38c75f3bfbf37ebdb7e7cdc0594d063a16c?s=96&d=mm&r=g","caption":"decide4AI"}}]}},"_links":{"self":[{"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/posts\/12345","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/users\/30"}],"replies":[{"embeddable":true,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/comments?post=12345"}],"version-history":[{"count":3,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/posts\/12345\/revisions"}],"predecessor-version":[{"id":21433,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/posts\/12345\/revisions\/21433"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/media\/24847"}],"wp:attachment":[{"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/media?parent=12345"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/categories?post=12345"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/decidesoluciones.es\/en\/wp-json\/wp\/v2\/tags?post=12345"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}