version 1.0.0.0 (10.6 KB) by
John Hedengren

Mixed Integer Nonlinear Programming Solver with APM MATLAB

Solves the mixed integer nonlinear problem:

min p(x,y)

s.t. f(x,y) <= 0

s.t. g(x,y) == 0

s.t. lb <= x <= ub

s.t. nlb <= y <= nub

x(yidx) integer where yidx is a logical index vector

y continuous variables

This program solves nonlinear mixed integer problems with a branch and bound method. NLP relaxations are solved with IPOPT or APOPT.

Files:

minlp.m - Solve the example MINLP problem

minlp.apm - MINLP problem definition

Other:

APM Function Library (v.0.5.6) in folder

Further work:

Add heuristics to create a good initial integer solution

Add cuts to the problem (branch and cut method)

Some testing shows that it works well with up to around 30 integer variables and 10000 NLP variables. Solutions to NLP relaxations are solved as a web-service. With the network communication overhead, the solution time may be slower than other MINLP solvers such as DICOPT, BONMIN, etc. This program is intended for educational purposes and to attract collaborators for future developments. The release notes and development roadmap are listed at the APMonitor.com web-site:

John Hedengren (2020). MINLP: Mixed Integer Nonlinear Programming (https://www.mathworks.com/matlabcentral/fileexchange/35720-minlp-mixed-integer-nonlinear-programming), MATLAB Central File Exchange. Retrieved .

Created with
R2011b

Compatible with any release

**Inspired by:**
bnb, fminconset, Linear Mixed Integer Program Solver

**Inspired:**
Model Predictive Control, Comparison of 5 Estimator Methods, New ODE and DAE Solver, Moving Horizon Estimation

Create scripts with code, output, and formatted text in a single executable document.

haotian wuI have a question,how to modify the maximum iteration?

Wen ZhangEWETOYE Ibrahimrihane sihami have a variable is a matrix that have mixt numbers and the ptoblem is multiobjectif.i must use branch and bound to solve it but ????how can i do it????

Maziar IsapourI tried to solve a nonlinear program the solution that I got from APOPT was not the optimum one. I am wondering if this comes from branch and bound method or APOPT.

EstrongerCould you tell me the syntax rules of this Modeling language?

Krishnakumar GopalakrishnanDoes this work for black-box type of optimisation problems wherein analytical equations of the objective function are not available ?

Waqas KhanPlease someone give me an idea of implementing this.

Joonmoo HuhThe solver says it is "Successful solution". But, I do have a solution that give the better minimum value. What kind of algorithm APOPT use? Does it have a genetic algorithm?

John HedengrenThere are some APOPT solver options available at http://apopt.com/download.php You can change these options in APMonitor by including something like:

File apopt.opt

minlp_gap_tol 1.0e-2

minlp_integer_tol 1.0e-2

End File

What message does the solver produce? Does it say it was successful? You may need to also try different initial guesses if you think your problem is non-convex.

Joonmoo HuhJohn, I can see the solution with only integer variables after changing the name of variables as "int_x[]". though the solution is not optimal.

It seems that it converges to a local minimum. What else I can try? Maybe different solver other than 'nlc.solver'?

Waqas KhanJohn HedengrenJoonmoo, could you send the files to the APMonitor discussion group (subscribe to the Google group to send) if you can't figure it out? Make sure any integer variables start with "int" such as "int_x[1]", etc. Also, make sure the APOPT solver is selected with apm_option(s,a,'nlc.solver',1); It is selected by default but just make sure you haven't selected a solver such as IPOPT.

Joonmoo HuhHi John,

Thank you for letting me know about the code for MINLP only. It is much faster. However, the solution still contains non-integer value (Same as the previous solution below) although I declare the variables as integer variables..

Any idea why this happens?

John HedengrenJoonmoo, I'd recommend that you use the package at https://github.com/APMonitor/apm_matlab (see example_minlp). This package is for someone who would like to develop a new MINLP solver. If you just want to solve MINLP problems then the MATLAB files at that GitHub location will be much better and faster.

Joonmoo HuhHi,

I'm trying to solve a simple 0-1 integer non-linear program with 26 integer variables. (No other variable)

But, the solver gives the solution with several non-integer values.

Is there any part that I might configure wrongly the "minlp.apm" file?

I did declare the variables like below.

! Declare integer variables first

! Default upper and lower bounds are overrided with

! new_ub and new_lb in MATLAB code

Variables

x[1:26] >=0, <=1

End Variables

And solution is given as below.

x[1] 0.00

x[2] 0.00

x[3] 1.000000E+00

x[4] 1.000000E+00

x[5] 0.00

x[6] 0.00

x[7] 0.00

x[8] 0.00

x[9] 0.00

x[10] 0.00

x[11] 0.00

x[12] 0.00

x[13] 1.000000E+00

x[14] 0.00

x[15] 0.00

x[16] 1.000000E+00

x[17] 1.000000E+00

x[18] 0.00

x[19] 0.00

x[20] 0.00

x[21] 3.072271E-01

x[22] 3.072271E-01

x[23] 0.00

x[24] 6.161304E-04

x[25] 0.00

x[26] 1.000000E+00

Pavel HoloborodkoJohn HedengrenAbhinav,

Here is an example of an MINLP formulated in APM: http://apmonitor.com/me575/index.php/Main/DiscreteDesign If you have discrete values that are not integers, you can either

(1) use binary variables (0-1) that indicate whether that option is selected and add a constraint that the sum of all options = 1 (only one is selected).

(2) scale your discrete variables by multiplying by 5 with y = (x1 - 0.2)*5 so that y=0 would be x1 = 0.2, y=1 would be x1=0.25, etc. You'll get an integer solution but the options will still be non-integer and discrete.

-John

Abhinav GaurHello John

In my problem, the variables can take certain discrete values within their respective bounds. Example, variable x1 \in {0.2, 0.5} can take values {0.2, 0.25, 0.3, 0.35, ..., 0.5}. How can I define these variables in the minlp.apm file?

John HedengrenVishwas,

Yes, you could use this package to solve your problem but it will be slow. I'd recommend that you look at APMonitor Optimization Suite, Pyomo, AMPL, GAMS, or other modeling language platforms that support commercial and open-source MILNP solvers. They will be much faster.

-John Hedengren

Vishwas RaoHi,

I am interested in solving a constrained optimization problem of the following form :

min F(U(x))

x

Such that

A(x,I)U = b

I is a vector and each element can be either 0 or 1.

Additionally, only 1 element in I can be non zero.

In other words, I is a canonical basis vector.

Do you think I can use this package to solve the above problem?

Xia laiJohn HedengrenSerena,

You can set lower and upper bounds on lines 73 and 74, respectively. Here are those lines from minlp.m:

lb = [0 0 0 0]';

ub = [1 1 1 1]';

This is development code for those interested in MINLP solver source code. However, there are more efficient ways to solve MINLP problems. Another way to solve this problem is to use the MATLAB MINLP solver described here:

https://youtu.be/XhqteZIydT0

http://apmonitor.com/me575/index.php/Main/DiscreteOptimization

Serena NavaHi,

I am trying to minimize the following function:

F = y'wy

with constraints Ay = b, and lower_bound<=y(1)+y(2)+...+y(v)<=upper_bound. Where y is a 1XN vector consisting of integer values of 0 and 1, and N = v(v-1)/2.

I would appreciate it if you could tell me how I can solve this problem using minlp.m. I have no problem imposing the first constraint (Ay = b) and the upper limit in the second constraint. However there is no option for setting the lower boundary condition for y(1)+y(2)+...+y(V). I was hoping you could help me with this.

Thanks,

Serena

John HedengrenHi Prateek. I'd recommend not using this script but instead to use the MATLAB or Python interface to APMonitor. Here is the APMonitor model file:

Variables

int_x1 >= 0

int_x2 >= 0

Equations

maximize 3 * int_x1 + 4 * int_x2

7*int_x1 + 11*int_x2 <= 88

3*int_x1 - int_x2 <= 12

It returns the answer of x1=3, x2=6. You can either solve it online through a web-browser at http://apmonitor.com/online/view_pass.php or else through the MATLAB or Python interfaces here: http://apmonitor.com

Please let me know if you need any additional help.

-John Hedengren

Prateekhello sir,

i want to solve the basic integer problem as mentioned below:

maximize f = 3*x1 + 4*x2

subject to

7*x1 + 11*x2 <= 88

3*x1 - x2 <= 12

x1 >= 0, x2 >= 0

x1, x2 are integers

so , i have modified the objective function and constraints in minlp.apm file, but i am getting wrong answer.

I think i have to modify the minlp.apm file and program also according to the objective function and constraints mentioned above.

can you tell me, where i have to change ???

Thanks

pk

John HedengrenAitor, you can't currently use it with external functions. Those functions would need first and second derivative information of the constraints and objective through automatic differentiation, adjoint methods, or with finite differencing (slow and hard to control balance between machine precision and accuracy of gradients). If gradients are available, then it should be possible with some minor code modifications. This file submission example uses an external server as a web-service to provide gradients.

AitorThank you for your work. I have one question: can I use this tool with external responses? In my case the constraints are obtained by other software; there is no an analytical expression for the nonlinear constraints. I try to minimize a linear function subject to nonlinear constraints with continuum and integer design variables.

Could you provide me any idea to perform this problem?

hsieh weikangThanks for your submission

I am a freshman of using matlab. I need to learn how to solve the MINLP problem. I want to Know how the example work in your code . I think it will be helpful for me. Thank you~~

John HedengrenPlease see the following link for additional information on MINLP including a MATLAB and Python interface to the Mixed Integer Nonlinear Programming solver, APOPT.

http://apmonitor.com/me575/index.php/Main/DiscreteOptimization

John HedengrenAmirhosein, there is an integer tolerance (possibly 1e-3). As long as the value is within that tolerance of an integer value, it is declared as an integer and accepted as a potential solution. Could you send me a copy of your files at john.hedengren@byu.edu if this isn't the issue?

Amirhosein JafariI have 2 question.

1. I tried to use my own function with 15 binary variables. In the results, the last one has a real value between 0 to 1. Why?

2. It can find the optimum solution of my function by only 1 iteration. How is it possible? that is because I have no non-integer variable?

thanks

Emre SavasOne last question, Where exactly I should put csv_load() command in minlp.m file that you provide in your submission? I think this is why I can't retrieve the data from csv file.

I am using minlp.m file that you submitted in this page.

Thanks for your help

John HedengrenBelow is a simple model file that demonstrates how to load in external parameters into APMonitor. You can replace the File *.csv section with loading a CSV file of your choice through MATLAB with the csv_load() function. For testing, just copy the lines below and insert into the web-interface at: http://apmonitor.com/online/view_pass.php

Constants

m = 4

Parameters

c[1:m] = 1.2

Variables

intv ! integer variables start with "int"

Intermediates

! summation of all elements

s[0] = 0

s[1:m] = s[0:m-1] + c[1:m]

Equations

! v to be equal to the nearest integer for summation

minimize (s[m] - intv)^2

File *.csv

c[1], 2.3

c[2], 5.1

c[4], 0.0

End File

Emre SavasI have tried to do it in either way, but I am always getting this error:

Error using urlreadwrite (line 90)

The server did not find a resource to match this request.

Error in urlread (line 36)

[s,status] = urlreadwrite(mfilename,catchErrors,url,varargin{:});

Error in apm_sol (line 7)

response = urlread(url);

Error in minlp (line 160)

sol = apm_sol(server,app); % retrieve solution

what I did was;

1. using csv_load:

I declared "c" as a parameter in .apm file, and typed csv_load(server,app, 'minlp.csv') command in minlp.m file.

OR….

2. Declaring parameters as FV:

I removed c[1], c[2], and c[3] parameters from amp file, and I put:

apm_info (server, app, 'FV', 'c[1]')

apm_meas (server, app, 'c[1]', 130)

apm_info (server, app, 'FV', 'c[2]')

apm_meas (server, app, 'c[2]', 150)

apm_info (server, app, 'FV', 'c[3]')

apm_meas (server, app, 'c[3]', 180)

this code in minlp.m file.. I am getting the same error in either methods.

Thanks for your help!

Emre

John HedengrenThe easiest way is probably as a CSV file and then load the data file with the command:

csv_load (server, app, csv_filename)

You'll need the APM MATLAB toolbox library that you can download from APMonitor.com. If you have the values in MATLAB you can also declare your parameters as FVs (fixed values) to create a way to load values dynamically such as:

apm_info (server, app, 'FV', 'c[1][5][2][25]')

apm_meas (server, app, 'c[1][5][2][25]', 5.2)

Unfortunately there are only convenient ways to load in 2D matrices in APMonitor.

Emre SavasJohn,

I would like to assign different numbers to each cell of my matrix, which are independent of other variables. i.e:

c[1][1] = 150

c[1][2]= 120

c[1][3] = 180

….

c[1][30]=45

where right hand side is an array of {150, 120, 180,…,45}

Is there an easy way to assign these numbers ?

John HedengrenOkkes, you may find it easier to declare a constants and then use vectors and arrays within APMonitor to define variables and/or equations. Here is an example:

Constants

n = 130

m = 75

End Constants

Variables

val[1:n][1::m]

End Variables

Equations

val[1:n/2][1::m] = val[2:n/2+1][1::m]

val[n/2:n][1::m] = 6

End Equations

Here is some additional information:

http://apmonitor.com/wiki/index.php/Main/Arrays

You can also submit a question to the APMonitor Discussion Forum here:

http://apmonitor.com/wiki/index.php/Main/UsersGroup

Let me know if you have any additional questions.

Emre SavasThanks for your submission. It's quite user-friendly toolbox.

I have a question. I need to create a matrix array (i.e f(i,j) where i and j are indices) using the parameters I define in my program. However, I would like to create it in a for loop statement to make it easier. It is quite painful to assign each cell of the array as an equation, if the dimension of indices (i and j) are too large.

Is there any way to do this?

Thanks,

Emre

MaginaElhamHi John

thanks. so you mean there is nothing available in MATLAB?

AMPL is not in MATLAB.

John HedengrenElham,

This file shows a branch and bound algorithm in MATLAB but it is development code that is meant for understanding the algorithms. If you just have an MINLP problem that you'd like to solve, I'd recommend that you use either a program like AMPL or APMonitor. For a tutorial on solving a Mixed Integer problem, please refer to this video:

http://youtu.be/i8WS6HlE8qM

If you start at 8:30, you'll see how to set up an integer programming problem (by adding "int" to the variables names). The APOPT solver is an MINLP solver and will be able to solve your problem and it will do it much faster than this development MATLAB code.

-John

ElhamHi

If I just changed this objective function :minimize obj + y[1]*y[4]*(y[1]+y[2]+y[3]) + y[3]

then what about the constrains? They should also be changed?

Moreover, could you please tell me that I just need to change minlp.apm file? And no more verifications in other files? I almost cannot understand them line by line.

I just need to run a mixed integer nonlinear optimization with an objective function and constrains.

justinian555okay,thanks for your reply

John HedengrenJustinian, there is additional information on vector and matrix operations in the documentation here:

http://apmonitor.com/wiki/index.php/Main/Arrays

It is an algebraic modeling language and matrix operations are supported although not as easily as MATLAB where matrices are a native structure.

Another strategy is to shift some of the pre- or post-processing to the MATLAB script and use APM for only the parts that need to be optimized. For example, if you Q * Q' can be done after the optimization, the results are returned to the MATLAB script where you can do this processing.

justinian555Hello

could apm file key matrix??

if yes , how can i do matrix multiply

such as declare Q as a matrix (K*K)

b (K*1) vector

then do Q*x<b

and can do Q*(Qtranspose)

Thank

Justinian

John HedengrenZiba, you need to change the following line in the minlp.apm file:

minimize obj + y[1]*y[4]*(y[1]+y[2]+y[3]) + y[3]

to be your specific objective function. You should also look at the APM MATLAB toolbox that gives you more flexibility and allows you to solve with the APOPT solver which is much faster than this version because all of the sub-NLP problems in the branch and bound are not solved with MATLAB but with optimized compiled code.

http://apmonitor.com/wiki/index.php/Main/MATLAB

The purpose of this submission is to demonstrate branch and bound algorithms in MATLAB, not necessarily as optimized code. The APOPT through APM MATLAB toolbox is many times faster than this version. The advantage of this version is that you can use any NLP solver to solve the relaxed sub-problems and you also have the source code instead of using it as a web-service.

-John

ZibaHello

If I want to use minlp as a function in my program how should I introduce my objective function to this function. I will be thankful if let me know the exact format for calling minlp function.

Thank yoy

Ziba

John HedengrenYes, the x represent integer variables. You can change the problem by opening minlp.apm with a text editor. This is a developmental version of an MINLP solver. For a much faster solver, use the "built- in" branch and bound capabilities of APOPT through APM MATLAB.

http://apmonitor.com/wiki/index.php/Main/MATLAB

Here is an example with integer variables that can be solved through a web-interface:

http://apmonitor.com/online/view_pass.php?f=minlp.apm

ahmadHi, sorry how we can input our own objective functions? by the way, x represent integer variables and y represents non-integeres, yes?