1.8 C
New York
Monday, December 5, 2022

Exploring mixed integer programming – INDIAai

In-depth and nuanced coverage of leading trends in AI One
Latest updates in the world of AI
Information repositories on AI for your reference
A collection of the most relevant and critical research in AI today
Read the latest case studies in the field of AI
Curated sets of data to aid research initiatives
The best of AI brought to you in bite-sized videos
World-class policy developments and accepted standards in AI development
Roles spanning various verticals and domains in big data and AI
Latest events in AI locally and internationally
Pieces covering the most current and interesting topics
VCs, PEs and other investors in AI today
Top educational institutions offering courses in AI
Profiles of visionary companies leading AI research and innovation
India’s brightest and most successful minds in AI research and development
A glimpse into research, development & initiatives in AI shaping up in countries round the world
Read all about the various AI initiatives spearheaded by the Government of India
Latest initiatives, missions & developments by GoI to drive AI adoption
Follow INDIAai
About INDIAai
Subscribe to our emails

By Dr Nivash Jeevanandam
Linear programming maximizes or minimizes a linear objective function under limits. Mixed integer programming requires at least one variable to be an integer. Operations research heavily uses this strategy.
An optimization or feasibility problem in mathematics where some or all variables must be integers is known as an integer programming problem. The phrase frequently applies to integer linear programming (ILP), where the objective function and constraints (aside from the integer constraints) are linear.
Programming in integers is NP-complete. One of Karp’s 21 NP-complete problems is the case of 0-1 integer linear programming, in which the unknowns are binary, and only the limitations need to be met.
The issue is a mixed-integer programming problem if some decision variables are not discrete.
Mixed-Integer Programming (MIP) Problems
When some of the decision variables must have integer values at the best solution (i.e. whole integers like -1, 0, 1, 2, etc.), the problem is referred to as mixed-integer programming (MIP). When you employ integer variables, you may define and solve a far more comprehensive range of practical optimization problems.
A decision variable, X1 that can only be either 0 or 1 at the solution is a particularly significant situation. These variables, also known as 0-1 or binary integer variables, can simulate yes-or-no choices, such as whether to construct a plant or purchase a piece of machinery. Unfortunately, an optimization problem becomes non-convex and much more challenging to solve when it has integer variables. In addition, as you add more integer variables, your memory and solution time might increase rapidly.
Despite modern approaches and supercomputers, models with a few hundred integer variables have never been optimally solved. It is due to the need to test numerous combinations of particular integer values for the variables. We must solve a “typical” linear or nonlinear optimization problem for each variety. The possible combinations might grow exponentially as the challenge gets more extensive.
Constraint Programming (CP) Problems
The phrase “constraint programming” is derived from artificial intelligence research, where various issues call for assigning symbolic values to variables that adhere to particular limitations, such as locations on a chessboard. The symbolic values are drawn from a finite set of possibilities that integers may quantify.
“Higher-level” constraints that apply to integer variables are defined through constraint programming. For example, the most common and practical higher-level restriction demands a set of n choice variables to adopt a permutation (non-repeating ordering) of numbers from 1 to n.
Solving MIP and CP Problems
Some systematic, potentially exhaustive searches must resolve MIP and CP problems because they are non-convex. Branch and Bound is the name of the “traditional” approach to handling these issues. This method finds the optimal “relaxation” solution without integer limitations (via standard linear or nonlinear optimization methods). There is no need for additional effort if the decision variables with integer constraints in this solution have integer values. The Branch and Bound approach select one of the integer variables with non-integral solutions and “branches,” generating two new subproblems where the variable’s value is more strictly bound. Until a solution that fulfils all integer constraints is discovered, these subproblems are resolved, and the procedure is repeated.
Alternative techniques, including genetic and evolutionary algorithms, produce potential solutions randomly while adhering to the integer limitations. These methods start with initial solutions that are typically far from optimal. Still, they then use techniques like integer- or permutation-preserving mutation and crossover to turn existing solutions into new candidate solutions that still satisfy the integer constraints but may have better objective values. Iterations of this method are carried out until a “good solution” is attained. Unfortunately, these techniques typically cannot “prove the optimality” of the solution.
About the author
Senior Research Writer at INDIAai
Share via
The top seven Twitter bots for 2022
Exploring DeepSpeed-MII – an open-source python library
Join our newsletter to know about important developments in AI space


Related Articles


Please enter your comment!
Please enter your name here

Latest Articles