Mixed Integer Linear Programming (MILP) Tutorial
Vložit
- čas přidán 24. 01. 2014
- Optimization with continuous and integer variables is more challenging than problems with only continuous variables. This tutorial and example problem gives details on exhaustive search and branch and bound techniques for solving Mixed Integer Linear Programming (MILP) problems.
- Věda a technologie
It's amazing how you were able to explain ILP and the methods to solve them in 10 minutes. And even more impressive when using this APMonitor tool
Thanks for the feedback! If you are using Python, try these tutorials: medium.com/@sushan531/integer-programming-with-python-and-gekko-51ac235de408
Your videos and the website are amazing, very useful and practical professor. Thank you so much
Thanks for the video. I have a question. Around 6:43 you add the constraints 2
You are branching away from 2.67 so it is x2 greater than or equal to 3 and x2 less than or equal to 2 that are solved as separate cases. You continue to branch until you find an integer solution. Once you find an integer solution that is the upper bound for your optimization problem. You continue until the upper bound and the lower bound of the relaxed solutions is within a certain gap tolerance. More info is available at apmonitor.com/me575/index.php/Main/DiscreteOptimization
Can you share the link to the Linear Programming video you suggest watching before this video? I'm having trouble finding it.
Thank you for the video. May I ask if APMonitor can show all possible integer solutions for a problem? My problem is really simple but so far I haven't found one python package that allows a printout of all feasible solutions.
Most packages probably don't do this because the number of feasible solutions is typically too many. Here is some content on discrete optimization: apmonitor.com/me575/index.php/Main/DiscreteOptimization with example code.
What device did you use to write on your screen? Can it also be used on Mac?
I use a Surface Pro with a Wacom pen. OneNote is the program that I use for writing. I use TechSmith Relay for recording the screen. Here is an overview: czcams.com/video/S1ayo1n7AsM/video.html
I'd like to ask you...in a MILP problem for a cement industry, using Matlab, should the size of the matrix of the inequalities be the same with the matrix of equalities???
I don't know of a good MILP solver in MATLAB. The best ones are Gurobi, CPLEX, and Mosul Xpress. The size of the matrix inequalities and equalities can by different.
So expressing the problem like this...Α*x= beq & B*x= bineq , matrixes A & B could be different in size and matrixes beq & bineq size depends on the number of equalities and inequalities in each case, right??
The length of the vector x is common between the two but A and B can have different number of rows but same number of columns (same as x length). The Α*x= beq & B*x= bineq will have dimensions (n x m)*(m x 1) = (n x 1) & (p x m)*(m x 1) = (p x 1).
Is it possible to use MILP with Multi-objective optimization problem?
Yes, MILP has only one objective so you need to give a weight to each objective and add them together. If you can't add them together then you'll need to use something like a Pareto frontier. More details at apmonitor.com/me575 and apmonitor.com/do (see multi-objective link on the right).
great tutorial thanks to sharing it!
Actually I have a question which may be not very related to what you did in this video but stay in the same domain.
so I work on a case of the bin-packing problem, I have a modelization to this problem which has a set of binary decisions variables in some constraints not in the objective function which has just a continues variables, so my question is can we say in this case that I have a mixed integer problem ?
thank you for any feedback.
Yes, your problem is mixed integer. All of your binary variables should have a continuous relaxation meaning that they can be 0, 1, or somewhere in between like 0.7 for evaluating intermediate solutions. Here is a circle packing optimization that may help: apmonitor.com/me575/index.php/Main/CircleChallenge
Thanks a lot for your response.
I have checked the circle packing you refer to, it's almost what I try to do ( i can say it's a triangle packing), I try to place a number of rectangular rooms in a rectangular space has a fixed width and high, the dimensions of every room (which are my variables) have an upper and lower bound and there are, of course, the coordinates of every room which they are variables too. My objective function here is to maximize the surface of every room as much as possible with respect to existing a fixed distance between every pair rooms (corridor).
I use the Cplex IBM solver through C++ with VisualStudio.
The problem is that when I try to place more than 5 or 6 rooms it begins to take very much time (because it's an NP-hard problem I think), so I tried to decompose my problem into a master one and an auxiliary but I failed so any help will be great.
My problem model looks like:
n: number of rooms to take a place.
Variables :
DXi : Dimension on the axis X (for example : 100
You may try Benders Decoposition: en.m.wikipedia.org/wiki/Benders_decomposition Each room could be like a scenario where you apply the cuts from infeasible solutions from one room to all the scenarios. If you'd like to code your problem with Gekko, there is a recent thread on the APMonitor discussion group (Google group) that is relevant to BD.
Thanks again, actually I have tried to constraint my problem as you did with the circle problem. the problem now that the Cplex solver doesn't accept quadratic constraints (non-linear) so I will try with the Benders Decomposition.
Regards
More recent versions of CPLEX and Gurobi accept QPQC (Quadratic contraints). You are also welcome to try the APOPT solver (MINLP) that is included with GEKKO and APMonitor.
Your videos are amazing, I want to master MILP, and the logical constrains, how to set those difficult logical constrains for them to be linear. I know that practice makes masters, but can you help me with some paper easy to read as well of some material to follow to enhance my mathematical modelling skills in MILP? Thanks God bless you!
That’s great to hear. There is a book and optimization content available at APMonitor.com/me575
are you able to give me your contact information if I had some questions. Going into an analyst role without analyst background and this is something I will be required to do for Supply Chain! It would be amazing.
I'd recommend a discussion group such as the APMonitor group. I'm available for consulting support for some projects. Using an online group is a much more cost effective way to get answers. There are also a lot of other online resources. My contact info is john@apmonitor.com.
May I know what programming language are you using? sorry for the stupid question
At 1:39 I show how to program the problem with the APMonitor Optimization Suite. It is available as a toolbox in MATLAB, a module in Python (pip install APMonitor), or in Julia. Visit apmonitor.com for more information and a download link on Github as well.
Could the objective function be quadratic?
Yes, but you would need to use an MIQP solver. Python Gekko can solve Mixed Integer Nonlinear Programming (MINLP) problems.
@@apm Ah here we go again. I used to use this module to solve quadratic optimization in a large scale. Thank you!
Do you ever solve these kinds of problems using a programming language like Python?
+PythonParseltongue, there are options for Python but most are APIs to existing solvers such as discussed here: stackoverflow.com/questions/26305704/python-mixed-integer-linear-programming. Python is too slow to create a competitive solver so they are typically written in C++ or Fortran. I develop the APM Python package that solves MINLP (or MILP) problems with differential and algebraic equations. It should work with this example as well. Here is one example from my Engineering optimization course: apmonitor.com/me575/index.php/Main/DiscreteDesign
+APMonitor, I'm interested in this APM package. I recently used Couenne from COIN-OR to optimize a gearbox for two given gear ratios on my channel. I was wondering, how does APM compare to the MINLP solvers from COIN-OR? Like Couenne, BONMIN, and MINOTAUR? Is it mostly for engineering problems?
The APOPT solver in APMonitor is a large-scale MINLP solver. Other solvers such as Couenne or BONMIN can also be linked to APMonitor, although we haven't done those yet. APOPT is available here for download: apopt.com/download.php for AMPL, Pyomo, or APMonitor. Here is some information on APOPT on some MINLP benchmark problems: apm.byu.edu/prism/uploads/Members/apopt_minlp_presentation_informs2013.pdf I don't think anyone has done a full benchmark comparison yet.
Sir give me answer A small contractor has undertaken to supply a customer with at least 500 units in total of two products A and B during the next month. At least 30% of the total supply must be units of product A. It requires 3 labour hours to produce one unit of A and 8 labour hours to produce one unit of B. The contractor has planned to make use of 2400 labour hours for this work next month and any additional labour hours can be made available if required. The total variable cost is Rs 80 per unit of A and Rs 120 per unit of B. The contractor wishes to minimize his expenditure on this contract. questions, Formulate the linear programming model
There is more information on optimization at apmonitor.com/me575
Good video, but the title is misleading. The example you gave is not a mixed-integer linear programming problem, it is an integer linear programming problem. "Mixed" implies that some (one or more) of the variables are allowed to be continuous in the (final) solution i.e. not just integers. Also I think the algorithm you use is called branch and cut.
Daniel, the problem I show has two other continuous variables that are fixed at the optimum just for the purpose of demonstrating the method. Check out apmonitor.com/me575 for more material on branch and bound methods including source code in Matlab and Python. There is also a book chapter on discrete optimization. Branch and cut is the addition of inequality hyperplanes to trim the search space and is different than the method shown here.
Do you fix those other variables in another video? Well y = 3 as in your example are both inequalities and they both trim the solution space, so what's the difference? According to Wikipedia a line is a type of hyperplane.
I can see why that would be a point of confusion. I suppose it is just the way the community refers to the two methods. Branch and cut is typically reserved for linear cutting planes that are more than just variable bounds. I made up the example problem by modifying the Hock Schittkowski problem #71. apmonitor.com/che263/index.php/Main/PythonOptimization I just fixed two variables at optimal values to simplify the problem.