Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
objective function in bintprog
26 views
Skip to first unread message
tuantt218
Aug 4, 2008, 3:24:37 PM8/4/08
to
Hello everyone,
I'm working on a binary optimization broblem using *bintprog.
*However, this
function defines the objective function through an input vector f such
as
x=bintprog(f,A,b).
Is there any way that I can define my own objective function as
"objfun"
then I call it such as
x=bintprog(@objfun,A,b)
Any suggestion will be appreciated. Thanks.
I'm working on a binary optimization broblem using *bintprog.
*However, this
function defines the objective function through an input vector f such
as
x=bintprog(f,A,b).
Is there any way that I can define my own objective function as
"objfun"
then I call it such as
x=bintprog(@objfun,A,b)
Any suggestion will be appreciated. Thanks.
WM
Steve
Aug 4, 2008, 5:12:02 PM8/4/08
to
tuantt218 <tuan...@gmail.com> wrote in message
<db11f169-9386-449b...@i24g2000prf.googlegroups.com>...
<db11f169-9386-449b...@i24g2000prf.googlegroups.com>...
Hi,
bintprog is only for binary integer linear programming.
Therfore the only objective it minimizes is f'*x.
++Steve
tuantt218
Aug 4, 2008, 6:33:49 PM8/4/08
to
Steve, thanks for your reply.
That means the objective function is in a form of summation:
sum[f(i)*x(i)] where f(i) is the coefficient and x(i) is a binary. So,
what if i want an objective funtion in another form, for example,
product: prod[f(i)*x(i)]. Can we do that?
WM
On Aug 4, 2:12 pm, "Steve " <steve.griksc...@mathworks.com> wrote:
> tuantt218 <tuantt...@gmail.com> wrote in message
>
> <db11f169-9386-449b-a999-b958f5485...@i24g2000prf.googlegroups.com>...
John D'Errico
Aug 4, 2008, 8:58:02 PM8/4/08
to
tuantt218 <tuan...@gmail.com> wrote in message <5c9bba0f-8471-438d-
9773-9d1...@j7g2000prm.googlegroups.com>...
> Steve, thanks for your reply.
>
> That means the objective function is in a form of summation:
> sum[f(i)*x(i)] where f(i) is the coefficient and x(i) is a binary. So,
> what if i want an objective funtion in another form, for example,
> product: prod[f(i)*x(i)]. Can we do that?
9773-9d1...@j7g2000prm.googlegroups.com>...
> Steve, thanks for your reply.
>
> That means the objective function is in a form of summation:
> sum[f(i)*x(i)] where f(i) is the coefficient and x(i) is a binary. So,
> what if i want an objective funtion in another form, for example,
> product: prod[f(i)*x(i)]. Can we do that?
No. bintprog ONLY solves a linear objective.
Your example is not linear.
No matter how much you want it to work
differently, it still only solves the problem
it was designed to solve.
John
tuantt218
Aug 5, 2008, 1:23:17 PM8/5/08
to
On Aug 4, 5:58 pm, "John D'Errico" <woodch...@rochester.rr.com> wrote:
> tuantt218 <tuantt...@gmail.com> wrote in message <5c9bba0f-8471-438d-
>
> 9773-9d1af72c1...@j7g2000prm.googlegroups.com>...
>
> > Steve, thanks for your reply.
>
> > That means the objective function is in a form of summation:
> > sum[f(i)*x(i)] where f(i) is the coefficient and x(i) is a binary. So,
> > what if i want an objective funtion in another form, for example,
> > product: prod[f(i)*x(i)]. Can we do that?
>
> No. bintprog ONLY solves a linear objective.
> Your example is not linear.
>
> No matter how much you want it to work
> differently, it still only solves the problem
> it was designed to solve.
>
> John
> tuantt218 <tuantt...@gmail.com> wrote in message <5c9bba0f-8471-438d-
>
> 9773-9d1af72c1...@j7g2000prm.googlegroups.com>...
>
> > Steve, thanks for your reply.
>
> > That means the objective function is in a form of summation:
> > sum[f(i)*x(i)] where f(i) is the coefficient and x(i) is a binary. So,
> > what if i want an objective funtion in another form, for example,
> > product: prod[f(i)*x(i)]. Can we do that?
>
> No. bintprog ONLY solves a linear objective.
> Your example is not linear.
>
> No matter how much you want it to work
> differently, it still only solves the problem
> it was designed to solve.
>
> John
Thanks John,
Do you have any suggestion to solve the problem which is not linear as
above?
WM
Rakshith Amarnath
Nov 10, 2011, 9:52:12 AM11/10/11
to
"Steve Grikschat" wrote in message <g77rb2$1e0$1...@fred.mathworks.com>...
Hello Experts,
Is there any possibility for me to enter the objective function as a matrix?
It is still linear but it is no longer a row vector.
For example please consider this:
CostMatrix =
34 37 35 72
38 35 37 72
38 39 33 72
38 39 33 72
A =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
B =
3
3
3
3
Aeq =
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Beq =
1
1
1
1
Now I want to run the ILP such that:
bintprog(CostMatrix,A,B,Aeq,Beq) gives me the result as a 4x4 matrix.
But I get this error because it is expecting A to have 16 columns:
??? Error using ==> bintprog at 222
The number of columns in A must be the same as the length of f.
I have done some work around (change constraints such that their columns = length(f)) and got my problem solved.
But I wanted to know if there is any inbuilt support without requiring me to make the objective function 1dimensional and changing the constraints?
I ask this doubt because the modification that I did to the set of constraint equations has hampered the readability of the my function.
Awaiting your response,
Rakshith Amarnath
Is there any possibility for me to enter the objective function as a matrix?
It is still linear but it is no longer a row vector.
For example please consider this:
CostMatrix =
34 37 35 72
38 35 37 72
38 39 33 72
38 39 33 72
A =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
B =
3
3
3
3
Aeq =
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Beq =
1
1
1
1
Now I want to run the ILP such that:
bintprog(CostMatrix,A,B,Aeq,Beq) gives me the result as a 4x4 matrix.
But I get this error because it is expecting A to have 16 columns:
??? Error using ==> bintprog at 222
The number of columns in A must be the same as the length of f.
I have done some work around (change constraints such that their columns = length(f)) and got my problem solved.
But I wanted to know if there is any inbuilt support without requiring me to make the objective function 1dimensional and changing the constraints?
I ask this doubt because the modification that I did to the set of constraint equations has hampered the readability of the my function.
Awaiting your response,
Rakshith Amarnath
Torsten
Nov 10, 2011, 10:51:24 AM11/10/11
to
On 10 Nov., 15:52, "Rakshith Amarnath" <rakshamarn...@gmail.com>
wrote:
> "Steve Grikschat" wrote in message <g77rb2$1e...@fred.mathworks.com>...
> Rakshith Amarnath- Zitierten Text ausblenden -
>
> - Zitierten Text anzeigen -
So you want to solve 4 independent problems with bintprog
where
f1=[34 ; 37 ; 35 ; 72],
f2=[38 ; 35 ; 37 ; 72],
f3=[38 ; 39 ; 33 ; 72],
f4=[38 ; 39 ; 33 ; 72]
and A, B, Aeq, Beq are the same and as above for each of the
problems ?
Or do you want choose
A1=[1 0 0 0 ]
A2=[0 1 0 0 ]
A3=[0 0 1 0 ]
A4=[0 0 0 0 ]
(same for B, Aeq and Beq) ?
In any case, call bintprog in a loop with loop-index i and set
f(:)=CostMatrix(i,:)'
and accordingly for A,B,Aeq and Beq.
Best wishes
Torsten.
wrote:
> "Steve Grikschat" wrote in message <g77rb2$1e...@fred.mathworks.com>...
> > tuantt218 <tuantt...@gmail.com> wrote in message
> > <db11f169-9386-449b-a999-b958f5485...@i24g2000prf.googlegroups.com>...
>
> - Zitierten Text anzeigen -
So you want to solve 4 independent problems with bintprog
where
f1=[34 ; 37 ; 35 ; 72],
f2=[38 ; 35 ; 37 ; 72],
f3=[38 ; 39 ; 33 ; 72],
f4=[38 ; 39 ; 33 ; 72]
and A, B, Aeq, Beq are the same and as above for each of the
problems ?
Or do you want choose
A1=[1 0 0 0 ]
A2=[0 1 0 0 ]
A3=[0 0 1 0 ]
A4=[0 0 0 0 ]
(same for B, Aeq and Beq) ?
In any case, call bintprog in a loop with loop-index i and set
f(:)=CostMatrix(i,:)'
and accordingly for A,B,Aeq and Beq.
Best wishes
Torsten.
Rakshith Amarnath
Nov 11, 2011, 3:52:31 AM11/11/11
to
Torsten <Torsten...@umsicht.fraunhofer.de> wrote in message <38c561e1-369c-4bce...@m7g2000vbc.googlegroups.com>...
Dear Torsten,
Thank you very much for the reply.
In fact I want to solve the entire problem as one single optimization problem and not as 4 independent ones. And when I tried the suggestion given by you, f(:)=CostMatrix(i,:)' , it does not seem to work.
%**************Error
??? In an assignment A(:) = B, the number of elements in A and B
must be the same.
Error in ==> tmp2 at 129
f(:) = CostMatrix(i,:)';
%**************Error
My doubt is: if my objective function is of length 16 i.e. in the form of 4x4 matrix, but not as 1x16 vector, can my constraint also be a 4x4 matrix or should it be a row vector of 1x16? Also I am interested in the output being a 4x4 matrix.
It would mean that it is not possible to input objective function and constraints as a 2D matrix and make use of bintprog to solve it as one Optimization problem.
I hope you are able to understand my question. Do let me know if you feel that there are any simple steps. Because now I have modified every constraint into 1x16 vector (4 such constraints) and got it working. But I do not want to confuse the readers of my function by doing so. I want the constraints to be retained as a 4x4 matrix.
Best Regards,
Rakshith Amarnath
Thank you very much for the reply.
In fact I want to solve the entire problem as one single optimization problem and not as 4 independent ones. And when I tried the suggestion given by you, f(:)=CostMatrix(i,:)' , it does not seem to work.
%**************Error
??? In an assignment A(:) = B, the number of elements in A and B
must be the same.
Error in ==> tmp2 at 129
f(:) = CostMatrix(i,:)';
%**************Error
My doubt is: if my objective function is of length 16 i.e. in the form of 4x4 matrix, but not as 1x16 vector, can my constraint also be a 4x4 matrix or should it be a row vector of 1x16? Also I am interested in the output being a 4x4 matrix.
It would mean that it is not possible to input objective function and constraints as a 2D matrix and make use of bintprog to solve it as one Optimization problem.
I hope you are able to understand my question. Do let me know if you feel that there are any simple steps. Because now I have modified every constraint into 1x16 vector (4 such constraints) and got it working. But I do not want to confuse the readers of my function by doing so. I want the constraints to be retained as a 4x4 matrix.
Best Regards,
Rakshith Amarnath
Torsten
Nov 11, 2011, 4:49:09 AM11/11/11
to
On 11 Nov., 09:52, "Rakshith Amarnath" <rakshamarn...@gmail.com>
wrote:
> Torsten <Torsten.Hen...@umsicht.fraunhofer.de> wrote in message <38c561e1-369c-4bce-931c-1ca7cb489...@m7g2000vbc.googlegroups.com>...
I still don't understand what your entire optimization problem looks
like.
If
min: [34 ; 37 ; 35 ; 72 ; 38 ; 35 ; 37 ; 72 ; 38 ;
39 ; 33 ; 72 ; 38 ; 39 ; 33 ; 72]' * [x(1) ;x(2) ;
x(3) ;...;x(16)]
is your objective function, what are the constraints in terms of
x(1),x(2),...,x(16) ?
Best wishes
Torsten.
wrote:
> Torsten <Torsten.Hen...@umsicht.fraunhofer.de> wrote in message <38c561e1-369c-4bce-931c-1ca7cb489...@m7g2000vbc.googlegroups.com>...
like.
If
min: [34 ; 37 ; 35 ; 72 ; 38 ; 35 ; 37 ; 72 ; 38 ;
39 ; 33 ; 72 ; 38 ; 39 ; 33 ; 72]' * [x(1) ;x(2) ;
x(3) ;...;x(16)]
is your objective function, what are the constraints in terms of
x(1),x(2),...,x(16) ?
Best wishes
Torsten.
Rakshith Amarnath
Nov 11, 2011, 6:45:10 AM11/11/11
to
Torsten <Torsten...@umsicht.fraunhofer.de> wrote in message <f0ae0bdb-4bd0-4e72...@y42g2000yqh.googlegroups.com>...
Dear Torsten,
Here is the problem which is working:
Objective function:
LCostMatrix = LinearizeArray(CostMatrix);
So now,
LCostMatrix =
Columns 1 through 14
34 37 35 72 38 35 37 72 38 39 33 72 38 39
Columns 15 through 16
33 72
Constraints:
Inequality Constraints A and B
A = repmat(eye(4),1,4);
% Construction of matrix B for inequality
B = CAPACITY*ones(4,1);
So, A and B are:
A =
Columns 1 through 14
1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0
Columns 15 through 16
0 0
0 0
1 0
0 1
B =
2
2
2
2
Equality Constraints (Aeq and Beq) are:
Aeq =
Columns 1 through 14
1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1
Columns 15 through 16
0 0
0 0
0 0
[map MinCost] = bintprog(LCostMatrix,A,B,Aeq,Beq);
map =
1
0
0
0
0
1
0
0
0
0
1
0
0
0
1
0
Now I convert back the map to 4x4 arrray.
MemMap = VectorizeArray(map,4,4);
1 0 0 0
0 1 0 0
0 0 1 0
0 0 1 0
My question:
Is there a way execute bintprog as below and get result as 4x4 matrix? without modifying it as shown above?
x = bintprog(CostMatrix,A,B,Aeq,Beq)
Where x has to be 4x4 or in other words the dimensions as CostMatrix?
And
Where:
2
2
2
Aeq =
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Beq =
1
1
1
1
I hope the problem is now clear.
Regards,
Rakshith Amarnath
Here is the problem which is working:
Objective function:
CostMatrix =
34 37 35 72
38 35 37 72
38 39 33 72
38 39 33 72
But I convert 4x4 to 1x16 because of problem mentioned above. For this I use a custom function LinearizeArray:
34 37 35 72
38 35 37 72
38 39 33 72
38 39 33 72
LCostMatrix = LinearizeArray(CostMatrix);
So now,
LCostMatrix =
Columns 1 through 14
34 37 35 72 38 35 37 72 38 39 33 72 38 39
33 72
Constraints:
Inequality Constraints A and B
A = repmat(eye(4),1,4);
% Construction of matrix B for inequality
B = CAPACITY*ones(4,1);
So, A and B are:
A =
Columns 1 through 14
1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0
Columns 15 through 16
0 0
0 0
1 0
B =
2
2
2
2
Equality Constraints (Aeq and Beq) are:
Aeq =
Columns 1 through 14
1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1
Columns 15 through 16
0 0
0 0
0 0
1 1
Beq =
1
1
1
1
Finally without looping, I run the bintprog as below:
Beq =
1
1
1
1
[map MinCost] = bintprog(LCostMatrix,A,B,Aeq,Beq);
map =
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
Now I convert back the map to 4x4 arrray.
MemMap = VectorizeArray(map,4,4);
1 0 0 0
0 1 0 0
0 0 1 0
My question:
Is there a way execute bintprog as below and get result as 4x4 matrix? without modifying it as shown above?
x = bintprog(CostMatrix,A,B,Aeq,Beq)
Where x has to be 4x4 or in other words the dimensions as CostMatrix?
And
Where:
CostMatrix =
34 37 35 72
38 35 37 72
38 39 33 72
38 39 33 72
A =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
B =
2
34 37 35 72
38 35 37 72
38 39 33 72
38 39 33 72
A =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
B =
2
2
2
Aeq =
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Beq =
1
1
1
1
Regards,
Rakshith Amarnath
Torsten
Nov 11, 2011, 7:13:33 AM11/11/11
to
On 11 Nov., 12:45, "Rakshith Amarnath" <rakshamarn...@gmail.com>
wrote:
> Torsten <Torsten.Hen...@umsicht.fraunhofer.de> wrote in message <f0ae0bdb-4bd0-4e72-ac90-a4ec4fc95...@y42g2000yqh.googlegroups.com>...
No, you will have to rewrite the problem as you did above.
There exists no "special" bintprog-formulation for the type of
problem
you have to solve.
Best wishes
Torsten.
wrote:
> Torsten <Torsten.Hen...@umsicht.fraunhofer.de> wrote in message <f0ae0bdb-4bd0-4e72-ac90-a4ec4fc95...@y42g2000yqh.googlegroups.com>...
There exists no "special" bintprog-formulation for the type of
problem
you have to solve.
Best wishes
Torsten.
Rakshith Amarnath
Nov 11, 2011, 7:59:11 AM11/11/11
to
Torsten <Torsten...@umsicht.fraunhofer.de> wrote in message <389bcff5-485f-4af5...@m19g2000yqh.googlegroups.com>...
Dear Torsten,
Thanks for the reply.
I am a little curious to know the number of decision variables that can be practically solved? Can you let me know the limit on the size of objective function f? Currently I am not bothered much about the time it takes to solve. But I would like to know approximate size and if possible time - might be that time would also depend on constraints too as they will help the branch bound decisions to take place effectively.
I will be trying them out myself but in case if you have already done so, I would like to hear from you.
Thanks in advance.
Mit freundlichen Grüßen ,
Rakshith Amarnath
Thanks for the reply.
I am a little curious to know the number of decision variables that can be practically solved? Can you let me know the limit on the size of objective function f? Currently I am not bothered much about the time it takes to solve. But I would like to know approximate size and if possible time - might be that time would also depend on constraints too as they will help the branch bound decisions to take place effectively.
I will be trying them out myself but in case if you have already done so, I would like to hear from you.
Thanks in advance.
Mit freundlichen Grüßen ,
Rakshith Amarnath
Paul Kerr-Delworth
Nov 15, 2011, 4:52:14 AM11/15/11
to
"Rakshith Amarnath" wrote in message <j9j66v$esi$1...@newscl01ah.mathworks.com>...
Hi Rakshith,
This is a tricky question to answer and your suggestion of trying out the problems and seeing how long they take is a good one.
Saying that, you cannot solve problems with 65536 (2^16) variables or more using bintprog.
Best regards,
Paul
This is a tricky question to answer and your suggestion of trying out the problems and seeing how long they take is a good one.
Saying that, you cannot solve problems with 65536 (2^16) variables or more using bintprog.
Best regards,
Paul
Johan Löfberg
Nov 15, 2011, 7:22:10 AM11/15/11
to
tuantt218 <tuan...@gmail.com> wrote in message <5c9bba0f-8471-438d...@j7g2000prm.googlegroups.com>...
z <= x
z <= y
z >= x+y-1
for trilinear terms etc, you just perform the reformulations recursively.
Having said that, you do not want to solve the resulting problems using bintprog. bintprog is typically highly inferior compared to alternative MILP solver such as glpk or lp_solve (free) or cplex, gurobi, xpress or mosek (commercial with free academic licenses). All of these solvers have MATLAB interfaces.
If you use the modelling layer YALMIP, you can perform the reformulation automatically
A = randn(100,10);
b = rand(100,1)*15;
x = binvar(10,1);
f1 = rand(10,1);
f2 = randn(10,1);
objective = (f1'*x)*(f2'*x)
[obj_linear,aux] = binmodel(objective)
solvesdp([A*x < b, aux],obj_linear)
This model takes ~0.01 seconds to solve using glpk and 10 seconds using bintprog.
> Steve, thanks for your reply.
>
> That means the objective function is in a form of summation:
> sum[f(i)*x(i)] where f(i) is the coefficient and x(i) is a binary. So,
> what if i want an objective funtion in another form, for example,
> product: prod[f(i)*x(i)]. Can we do that?
>
> WM
>
>
> That means the objective function is in a form of summation:
> sum[f(i)*x(i)] where f(i) is the coefficient and x(i) is a binary. So,
> what if i want an objective funtion in another form, for example,
> product: prod[f(i)*x(i)]. Can we do that?
>
> WM
>
> On Aug 4, 2:12=A0pm, "Steve " <steve.griksc...@mathworks.com> wrote:
> > tuantt218 <tuantt...@gmail.com> wrote in message
> >
> > <db11f169-9386-449b-a999-b958f5485...@i24g2000prf.googlegroups.com>...
> >
> > > Hello everyone,
> > > I'm working on a binary optimization broblem using *bintprog.
> > > *However, this
> > > function defines the objective function through an input
> > vector f such
> > > as
> > > x=3Dbintprog(f,A,b).
> > tuantt218 <tuantt...@gmail.com> wrote in message
> >
> > <db11f169-9386-449b-a999-b958f5485...@i24g2000prf.googlegroups.com>...
> >
> > > Hello everyone,
> > > I'm working on a binary optimization broblem using *bintprog.
> > > *However, this
> > > function defines the objective function through an input
> > vector f such
> > > as
> > > Is there any way that I can define my own objective
> > function as
> > > "objfun"
> > > then I call it such as
> > > x=3Dbintprog(@objfun,A,b)
> > function as
> > > "objfun"
> > > then I call it such as
> > > Any suggestion will be appreciated. Thanks.
> >
> > > WM
> >
> > Hi,
> >
> > bintprog is only for binary integer linear programming.
> > Therfore the only objective it minimizes is f'*x.
> >
> > ++Steve
>
If you really have a product as stated, you can reformulate the problem to a binary model. Basically, you use the fact that x^2 is equal to x, and if you have bilinear terms x*y where x and y are binary, you replace this term with a new binary z with the constraints
> >
> > > WM
> >
> > Hi,
> >
> > bintprog is only for binary integer linear programming.
> > Therfore the only objective it minimizes is f'*x.
> >
> > ++Steve
>
z <= x
z <= y
z >= x+y-1
for trilinear terms etc, you just perform the reformulations recursively.
Having said that, you do not want to solve the resulting problems using bintprog. bintprog is typically highly inferior compared to alternative MILP solver such as glpk or lp_solve (free) or cplex, gurobi, xpress or mosek (commercial with free academic licenses). All of these solvers have MATLAB interfaces.
If you use the modelling layer YALMIP, you can perform the reformulation automatically
A = randn(100,10);
b = rand(100,1)*15;
x = binvar(10,1);
f1 = rand(10,1);
f2 = randn(10,1);
objective = (f1'*x)*(f2'*x)
[obj_linear,aux] = binmodel(objective)
solvesdp([A*x < b, aux],obj_linear)
This model takes ~0.01 seconds to solve using glpk and 10 seconds using bintprog.
0 new messages