noc19-mg24 Lecture 39 - Overview of Optimization Methods - Part 1

IIT Kanpur July 201
20 followers
2 Video Views·Dec 3, 2023
Good afternoon students, welcome to one another lecture in the advanced degree in manufacturing
systems.
We are coming to the close of the course, most of we have covered most of the topics
and with this lecture we would probably now cover one of the major concepts that we are
trying to do is the optimization and some of the algorithms associated with it.
So without wasting too much of time, I will just jump into today's topic.
So if you look at today's presentation, we have overview of optimization methods is what
we are going to do.
We have seen how the optimization problems are and now we are trying to look into what
are some of the methods, how do we solve this and today's learning agenda, we look into
something called total enumeration and branch and bound search, then improving search heuristics
which is called as local search and the extensions of local search.
These are the 4 concepts that we will cover today.
So first let us talk about this new concept that we are going to cover today in the class.
So what have we learned so far, what did we learn on optimization so far, what did we
do.
The thing that we learned so far is how to formulate an optimization problem, how to
formulate an optimization problem.
This we have seen, we are good at identifying how are we formulating this, this we know
how do we do that and what are the other aspects of it, we have a good idea.
Then we also saw how to use software to solve optimization problem.
Here in this case, we have been limited to what we call as continuous variables.
So our variables are continuous in nature, continuous variables that means they are vary
from x varies from minus infinity to plus infinity, okay this is what our concept was
and we know how to formulate those problems and we learn how to solve them using software
packages, right.
The trick is that many situations will happen where many situations will occur where variable
values, the values of the variables, variable values are not continuous, okay these variables
are not continuous or in other way only discrete values are possible, okay.
So what we are saying is that many situations, many of the optimization problems will not
have the variables as continuous variables, instead only discrete values are possible.
Discrete means integer values, countable values, those kind of things, okay.
So for the linear programming problem or what we call as LP, okay where the variables are
continuous and stuff like that, okay few prominent algorithms are sufficient to handle vast majority
of the models, of the optimization models or optimization problem.
So for LP problems where the variables are continuous, there are few algorithms available,
there are prominent algorithms and they are sufficient, they are very good in handling
majority of these models, okay.
But the major important thing for us is but discrete optimization problems, discrete optimization
problems.
What are discrete optimization problems?
Variables are not continuous, variables not continuous, okay your variables are not taking
a continuous value, okay.
These discrete optimization problems often require clever methods, methods that are specialized
are specialized for individual scenario.
So for each individual scenario, okay specific scenario of the discrete optimization problem,
we require clever methods that are specialized.
Highly specialized clever methods are required for discrete optimization problem.
The reason being is variables are not continuous, so hence LP like algorithms not possible,
we cannot use those algorithms to handle such kind of problems.
So what are some of the commonly used methods?
Our question today is this is what we are going to learn today.
What are some of the commonly used methods, methods on which context for discrete optimization
problems?
And this is very common because in real life in manufacturing, you do discrete manufacturing
most of the time, you make cars, you make parts, you make engines all those kind of
things.
They are all discrete optimization problems because they are countably discrete, there
is no continuous values there, okay.
So the first and foremost algorithm that we are going to talk about is total enumeration.
And you would not believe this is a pretty effective thing for small case problems, okay.
So like one of the things is it is often counterintuitive, you can it is often counterintuitive that
discrete optimization problems, what are discrete optimization problems?
Problems where the decision variables are not continuous.
Problems are more difficult than their continuous analogues.
So what we are saying is that the discrete optimization problem for a particular case
is more difficult to solve than the same continuous there, analog or the continuous the analog
problem which is a of the where the variables are in continuous, why?
Because it appears that only a finite number of choices are possible for decision variables,
a finite number of choices are possible for decision variables, hence should be easy.
So you think that in a continuous problem, the variable can take infinite number of choices,
any value it is possible, whereas in a discrete problem there are only limited values, a finite
number of values are possible for the decision variables.
Hence it should be ideally easy, but it is actually counterintuitive because it is not
easy.
Because when the variables are continuous, the most easiest thing is that you know you
can use things like mathematical things like differentiation integration or slop those
kind of things, gradient like techniques, whereas in these kind of problems that kind
of a thing is not possible.
So let us say one hypothesis, hypothesis 1, let us think about a important hypothesis
in this regard.
If a model that is a discrete optimization, discrete optimization model has only a few
discrete decision variables, discrete decision variables, if a model has only few discrete
decision variables, the most effective way or effective method of analysis is enumerate
all possibilities to obtain optimal solution.
So what we are saying here is, if the problem, the model is a discrete optimization model
and there are only few decision variables, number of decision variables are very small,
then the effective way of getting the optimal solution, how can you find the optimal solution
effectively is to enumerate all possibilities, run through all possibility options and then
find out.
This method, this approach is known as total enumeration.
So when somebody says total enumeration, then you should understand few things, one means
the decision variables are only few discrete options and then out of this you are able
to get an optimal solution.
So this total enumeration where we define it as checking of all possibilities, you are
checking of all possibilities implied by discrete variable values or taken by discrete variable
values are conducted, you do all discrete variable values, you take them and you check
all those possible values and then choosing the best combination, best combination that
gives the best objective value, that gives the best objective function value.
So what you are trying to do here is, you check all possibilities implied by the discrete
variable, whatever the decision variables, remember these are very few in number.
These few discrete decision variables you find out what are the all possibilities values
it can take, then what you do is you choose the best combination of this, that gives the
best objective function value.
Whatever is the best combination, you take that and you call it as the best objective
function value, that is the idea.
So let us see a simple example, let us look at a example of a total enumeration.
So this is kind of like a tricky problem but I think it will make.
So let us write a linear programming problem, maximize that is objective function 7x plus
4y plus 19z okay and subject to the constraints is x plus z is less than or equal to 1, then
y plus z is less than or equal to 1, then x, y and z they are element of 0, 1.
So what you are saying is that your 3 variables, these are the coefficients of the variables
that is the, this is the objective function and these are your constraints right.
So then obviously the thing is that the most important thing that you should understand
is x and x, y, z okay, the decision variables, the variables on which you can take decisions
x, y and z okay, can have either 0 or 1 as its values.
So you can have only either 0 or 1 in this particular case for the decision variables
x, y and z.
So since there are 3 variables, how many possibilities are there, 3 variables each having 2 values
possible, which gives you 2 to the power of 3, 8 options, 8 possible choices.
So 8 possible choices this is manageable by you.
So what are the possible choices okay, let us say the possible choices, the possible
choices in our case are let us call it as of x, y, z is the possible choice, it is a
0, 0, 0 that is one possible choice.
So that means all the values are 0, then the other possible choice is 0, 0, 1 okay.
So x, z taking value of 1, third choice is 0, 1, 0 where y is taking this one, then you
can have is 1, 0, 0 that is another possible combination.
So each one of them taking this particular value, then we can have another value as the
0, 1 and 1 where both y and z are taking the values of 1, so it is 2, 4 and 5.
So then the other value that is possible is 1, 0, 1, x and z taking 1 and y taking 0.
Then the other value that is possible is 1, 1 and 0 right and so now you have 2, 4, 6,
7 and the last possible value is all taking 1 right.
Now let us see in these cases okay what are the values of the objective function right.
So now let us say constraints, so let us see if you put the value of 0 and 0 okay, so let
us see the first constraint okay, the two constraints right.
So this satisfies the x, y and z these variables element of 0, 1, this is satisfied in all
cases okay.
So then the other constraint okay which let us call this as constraint 1 and let us call
this as constraint 2 right.
So the x plus z less than or equal to 1 okay, is it satisfied in all cases, so this is x,
y and z, so this is x plus z less than or equal to 0, so 1, 2 okay.
So 1 is satisfied, so we have put 1, 2, there is also first constraint, second constraint,
first constraint, second constraint, first constraint, second constraint, first, second,
first, second.
So there are two cases in this regard.
So the case of constraint 1 okay, check which all satisfy, so we check the first constraint
which one of them x plus z less than or equal to 1, is that satisfying.
So 0 plus 0 less than or equal to 1 that is correct, this case is x plus z, so it is 0
plus 1 less than or equal to this is also satisfied, this is 0 plus 0 less than or equal
to 1, satisfied, 1 plus 0 less than or equal to 1 satisfied, this is 0 plus 1 less than
or equal to 1 satisfied again, this is 1 plus 1 that is 2 less than or equal to 1 not satisfied,
1 plus 0 less than or equal to 1 satisfied, 1 plus 1 less than or equal to 1 not satisfied.
So these two cases immediately you can say that okay fine, I do not need to deal with
this because this is infeasible on 1 the first constraint is infeasible here is also infeasible
on 1. So, with the first constraint we know that these 2 are non-needed. So, then we do
not need to check the second constraint at all because you got this problem you do you
can eliminate. So, now immediately from 8 you are now reduced to 6 of them.
Now let us look at the second constraint which says x sorry y plus z less than or equal to
1 this is the check which all satisfy. So, now we are checking which all will satisfy
y plus z less than or equal to 1. So, y plus z less than or equal to 1 0 less than or equal
to 1 this satisfies y plus z less. So, 0 plus 1 is 1 1 less than or equal to 1 satisfies
1 plus 0 less than or equal to 1 satisfies 0 plus 0 less than or equal to 1 satisfies
and then 1 plus 1 this is less than 2 less than or equal to 1 does not satisfy.
Then in this case 1 plus 0 less than or equal to 1 satisfies. So, we get this particular
case also infeasible on 2. So, of these cases we know that we do not need to worry about
this case we do not need to worry about this particular case and we do not need to worry
about this particular case. So, out of 8 1 2 3 4 5 these are the 5 possible cases we
just need to now check. So, our possible cases in this include ok.
So, now if you continue with this working of this example the possible cases are now
the evaluation cases the cases that we need to evaluate in this case include 0 0 0 ok.
Then we have is 0 0 1 then we have is 0 1 0 then the next one we have is 1 0 0 and we
have is 1 1 0. So, these are the 5 cases if you look into this we got these values
from this particular table. So, we are only evaluating these cases ok.
So, now how do we evaluate that? So, now we do is these we just need to find the objective
function value ok because these are feasible these conditions of them are feasible we already
check the feasible. Now we just need to find what the objective function value is. So,
how do we calculate? The calculations include like this. So, for 0 0 0 it is equal to you
know 7 times 0 plus 4 times 0 plus 19 times 0 which will give you 0. So, the objective
function value is 0 in this case ok. The other case is let us take 0 0 1 then it
will be 7 times 0 plus 4 times 0 plus 19 times 1 that will be 19. So, 0 0 1 will give
you the value of 19 right. Then you have 0 1 0 0 1 0 will be 7 times 0 plus 4 times 1
plus 19 times 0 will give you 4 ok. So, 0 1 0 the objective function value is 4. Now
1 0 0 will give you 7 times 1 plus 4 times 0 plus 19 times 0 will give you 7. So, this value
is 7 right. Now the last one is 1 1 0. So, that will be 7 times 1 plus 4 times 1 plus 19 times
0 is 7 plus 4 11. So, that objective function value is 11. So, these are the 4 possible objective
function values. Now the objective was to maximize ok. Since the objective was to maximize
choose the largest value of objective function. So, what you are doing is from here this is
the largest value of objective function. So, we say this is the best possible solution
for this ok. So, the solution is that. So, what we are saying that the value of x is
equal to 0, value of y is equal to 0, value of z is equal to 1 ok. Objective function
is 19 ok and this is the best possible setup for this is the optimal solution for the problem.
So, depending on the constraints we already seen that we eliminated infeasible solutions
ok. These are all infeasible. So, we eliminated them using both constraints and then only
the remaining ones were worked out to find out what the best possible solution is ok.
So, this where we. So, we evaluated limited and yet feasible alternatives of decision
variables. So, we evaluated and yet feasible and yet all feasible alternatives of decision
variables were done and hence this is why it is called as total enumeration. Hopefully
this makes sense to you. From there we get into the next algorithm or next approach what
we call as branch and bound search ok. This is also a very popular approach among a lot
of people and let us see what it is ok. What is the major drawback of total enumeration?
What happens when you do the total enumeration? Why is the major drawback? Why is it like
people do not heavily use it? This is not feasible for a large set of decision variables.
So, if you have a large set of decision variables this is not very feasible. Why? The exponential
growth of solution space of solutions ok. So, for example, if 3 decision variables ok
let us say 0 1, then it is 2 to the power of 3 8. Let us say if 4 decision variables
again 0 1, then it is 2 to the power of 4. What is that? 2 to the power of 4 will be
16. So, now if it becomes 5, then it will be 16 times 2, 32. So, it will grow. So,
this solution space will grow something like this ok. This exponential growth if this is
the number of decision where the number of decision variables ok. This is the solutions
if you draw a graph like this, then the growth will be like an exponential growth.
So, then when it is large number of decision variables, now you have to look at if it there
are 5, then you will look at 32 options pretty soon it becomes manually impossible for you
to evaluate the things ok. So, then alternative what else can we do ok? What is alternative
to this headache ok? So, this is the let us say hypothesis 2 ok.
And belief system that if we have a way to deal with problems having large set of decision
variables set of decision variables ok. If we have problem which has large set of decision
variables, can the optimal solution be found without enumerating without explicit enumeration
of all possible excuse me unfeasible cases. So, what we are trying to say or our belief
is that if there is a way, if there is a method available where problems having large set
of decision variables are there, they are all discrete decision variables ok.
Where we still want to find the optimal solution, we want to get the optimal solution that is
provably optimal while we do not want to enumerate all possible and feasible cases. So, then
branch and bound is one such strategy. So, we can we call it as a it is a subset enumeration
set strategy ok. So, we are saying is that we do not want to enumerate every possible
options ok. So, what we say is that systematically form
classes of solution systematically form class solutions and investigate whether the classes
can contain optimal solutions. So, what you are saying is from the total problem you create
systematically from the classes of solution and see whether these classes can contain
optimal solution. If you find that the classes cannot contain optimal solutions then do not
look into that class, if you find that the class can have the optimal solution then look
into this ok. So, that kind of an approach. So, usually the tree search approach is used
to expand options. So, or classes ok. So, what we do is we use a tree search approach
in this regard to see whether we can actually systematically form the classes of solution
and then investigate whether the class can contain the feasible solution or not ok.
So, again as I said earlier let us look at a simple example of this one this would make
you understand the problem better ok. So, this is a single machine scheduling ok. So,
the idea is that you have a machine a single machine ok, let us say let us call it as drill
and you know entities arrive. So, they arrive into the system ok, this is the queue or something
and then they get drilled here ok, then there is a processing time P i j ok or whatever
the processing time and then they leave ok and this is the machine ok.
So, what happens is there are like say and jobs arrive there are different jobs that
are available. So, let us call the number of jobs for this case as 1, 2, 3 and 4 there
are 4 jobs available the processing time ok, P i for 1 let us make the processing
time as 37, for 2 the processing time is 27, 3 the processing time is 1 and the 4 the processing
time is 28 and then there is one more that is called as due date where you are supposed
to deliver the. So, this is the processing time this is associated with this, then here
is a customer sitting here and here is the delivery ok and this is where the due date.
Due date means when you have to give it to the customer. So, in this case let us put
a value of 49, let us put 36, let us put 1 and 37.
Now the question here is ok. So, we can schedule it in many ways, but find the schedule that
minimizes lateness of all jobs. So, what you are trying to do is we want to find the production
schedule that minimizes or find the sequence ok or schedule let us call it as a sequence
for the time being. Schedule and sequence there is only much small difference. So, sequence
means there are 4 jobs. So, there is Raman numerals are sequence positions ok, these
are sequence positions and we have to decide which job will go into which sequence position
in this regard right. So, you can solve it as a discrete optimization
problem as well or you can use branch and bound to solve the case. So, one way to think
about this problem is that ideally speaking you can think about it as a tree search. So,
if you say you call this as 0, let us call this as root node ok for the time being and
let us call this as the position 1 ok position 1. So, then you can have 4 possible options
out of this, you can put 4 possible jobs. So, these are the 4 possible jobs. So, if
you put 1 here, 2 here, 3 here and 4 here. So, that is equivalent to saying sequence
position 1 is taken by 1, 2, 3 and 4 ok. Then we take from here, once you fix this
when you say I am going to come to this particular portion, then you can say that there is another
position called position 2, the sequence position 2 that position 2 in this job you can have
3 underneath them. So, once 1 is fixed, then you can have for
the position it is 2, 3 and 4, any one of them can take the sequence position 2. For
2 again there is possibility of 3 ok. So, this is 1, 3 and 4, you cannot use 2 because
2 is already gone in the first sequence position right. So, then if you think about this below
that you have something called as position 3, the sequence position 3, there are only
2 possible options for this for this case, what because you already used 1, you already
used 2, then the possibilities are 3 and 4. So, then the last case is position 4, this
can have only 1, it can be 4, this can be 3. So, when you think about this, this sequence
becomes 1, 2, 3, 4 and the other sequence is 1, 2, 4, 3. So, what you have done is this
is where you have created something called as a what I mentioned earlier, this particular
term is systematically form classes of solution ok, systematic class of solution forming that
is what we are doing here in this particular case.
So, how would this actually help us in solving the problem? So, let us see an example ok,
this same example let us work out little bit longer. So, that would probably help us
in understanding the mechanics of the problem. So, our root node is 0 and we have our 4 sequence
positions ok, I hope we get space here 1, 2, 3 and 4 ok. So, the first sequence position
is taken care of in this case, we have made the first sequence position set up to 1, 2,
3 and 4. Now, you can decide the minute you put 1 here ok, the time taken to produce ok,
the PIE for. So, the lateness late let us let us call lateness equal to due date d i
the job minus sum of PIEs all the processing times.
So, for this case the lateness is equal to what is the value of lateness, the due date
the processing times are 37, 27 I am just writing it here for the time being making
my life easy 1 and 28 ok. So, for 37 if you think about it the due date of this problem
is I am writing the due date on this side which is 49 ok, this is 36, then this is 1
and 37 ok. So, in this case the lateness is 0, the in this case also the lateness is also
0 ok, I am just putting L equal to 0 here, this is also lateness equal to 0, lateness
equal to 0 ok fine. Now, there are multiple ways you can think
about ok. So, sometimes what people do is ok fine I will take one of these subclass
and expand it and so, that I get a solution out of it and see wherever I exceed this I
do not continue this problem. So, let us look at that example. So, I am just going to take
this branch 1 and expand out of it right. So, the next one I am going to do is ok the
sequence position 1. So, you finished that. So, now, let us think about the next job that
we are going to put in here, we have 3 jobs here possible that is 2, 3 and 4 ok for us.
So, now the processing time of job 1 is 37, if you put 2 here ok. So, then that becomes
the time taken the 2s processing time is which is 2s processing time is 27. So, the
time taken is the pi sigma pi in this regard is here will be I will kind of use the bottom
portion the sigma pi is equal to 37 plus 27 right. So, that will give you 7 plus 7 is
4 14 3 plus 2 5 plus 1 6. So, this will be 64, 64 and 2 is supposed to be delivered on
36th day ok and you are already late now ok. Now, about 3 if you think about it 3 the time
is 1. So, the sigma pi for 3 will be 37 plus 1 that is 38 right. So, this will be 38 and
3 is supposed to be delivered on day 1. So, you are already late ok again and if you think
about 4 it will be sigma pi will be is equal to 37 plus what you call as 4 will be 28 ok.
So, that will be 65 ok, 65 and 4 was supposed to be delivered on 37th day. So, you are late
here. So, by the second sequence position itself your solution is not very good you
are already late big time right. Now, same way if you can think about it is. So, some
people will say ok fine then there is no point in going here let me see whether there is
any other scenario where it is better. So, you can try the next one this second one and
let us see for an example I take the second sequence position I have 3 jobs possible here.
So, I put it as 1 3 and 4 and if you think about it the time taken for this is 27. So,
the sigma pi for the first branch is it is 27 plus 1 is 37. So, that will be 64 the time
to deliver is 36 it is late ok. So, then 3 will be it is 27 and 3 is time is 1. So, 28
and it has to be 3 has to be delivered in due date on 1 it is still late 27 plus 4.
So, that will be 4 is 28. So, this case will be sigma pi will be 27 plus 28. So, that is
15 2 plus 2 for 55. So, in this case it is 55 and it is supposed to be delivered on 37
it is still late. So, you will like fine here also by the second sequence position
everybody is late. So, now, let us look at the third one we can say is that there are
3 places that we can do at this point. So, 1 2 and 3. So, I can put 1 2 4. So, these
are the 3 options I have and this one if you think about is 3 the number of the processing
time is 1. So, there is no lateness here and. So, then the next job is 1 we have taken
and that is 37 right. So, 37 plus 1 is 38 and it is supposed to be delivered on 49.
So, no lateness L is equal to 0 if I do 2 then 2 will be 1 plus 27 that is 28 it is
supposed to be delivered on 36 the lateness is equal to 0 and 4 is 28. So, that is 29.
So, then the due date is to be 37. So, the lateness is equal to 0. So, now, here is a
scenario where the second sequence position none of the jobs are late. So, which means
now this is compared to these 3 cases I can say that this is a promising subclass. So,
compared to these guys these 2 1 this subclass the first subclass and the second subclass
this subclass is better because here all the jobs are late by the second sequence position
and here none of the jobs are late by the second sequence position.
So, then I can do is from here I can expand the third sequence position then. So, in this
case it will be 2 sequence positions will be used in this case that will be I am just
going to expand it for the time being just to expand. So, this will be 3 and 1 are used.
So, it will be 2 and 4 are the 2 possible options in this case right. So, then if it
is 2. So, this is 38 was the total processing time so far. So, the sigma pi for us is 38
and for 2 the time is 27. So, 38 plus 27. So, it is 8 plus it is 16. So, it is 5 3 plus
2 is 5 plus 1 6. So, this is 65 and 2 is supposed to be delivered by 36. So, you are late here
and then with 4 you can find out 4 is 28. So, sigma pi is equal to 38 plus 28. So, 16
and 3 plus. So, 3 plus 2 is 5, 5 plus 1 is 6. So, 66 and 4 is to be delivered at the
time of 37. So, this is late. So, both the jobs are late in the sequence position.
So, now if you look at the next ones and you can say that this 3 2. So, in the next
option is you have is 1 and 4 ok. So, these 2 guys will have that and then you expand
it and then this 4 case you will have 1 and 2 ok like this. And then from here then you
calculate which is the lowest lateness and then from there you can decide which lateness
or so far you might be promising and continuing that and then wherever you find a lateness
more. So, this process what we are doing below ok this is called branching, expanding
the solution to the branches of the trees is what we call as the branching.
And then let us say for example, I just let me take one example in this case I have already
let us say 28 is here and then with 1 the it is 37. So, let us take one example is that
here this is let us say 4 and I got that is 65. So, sigma pi in our case is 65 plus
the processing time of 4 is 28. So, 28 that so it is 93. So, let us say get the total
processing time as 93 and let us say the sum of the lateness in this particular case is
let us say you get a value of let us say for example, take it as 30 ok. So, the L value
is 30. So, let us say you get the for this particular
branch let us say for the L value here is 31, then what happens is you know that going
below this branch is not going to help ok, because it is not going to get you any better
solution. So, do not enumerate called bounding you are terminating or stopping or cutting
the search ok. So, there is other thing also is called bound. So, I would not call it as
bound bounding I will call it as pruning ok. What I am using is I am using this using this
as the bound. So, I am saying that with this bound this L equal to 30 whatever I calculated
I can basically stop all those branches of trees I do I can stop all those enumerations
where say look there is no need I need I do not need to expand this because my solution
is not going to be better. So, using the bound. So, what why do you use
bound? Bounds are used to reduce the number of leaves these are the leaves ok, leaves
evaluated in a tree. So, this approach what I am just talking to you as of now is what
we call as a ok called as a branch and bound algorithm ok. You branch on different branches
like you branching on a tree ok and then you use a bound to ensure that you do not evaluate
all possible options in this particular example. So, I hope you understand how I am how this
method works the different implementations of these methods by different people the different
variations of this also, but the fundamental idea is somewhat like this ok fine.
So, now we get into the last possible options which is called as a heuristics and optimization.
So, the heuristics and optimization is also another important aspect that we need to consider
in this case ok. So, one of the main thing that you need to understand is most of the
large scale most of the large scale optimization problem most of the large scale optimization
problems settle for some kind of approximation approximate optimization approximate optimization.
You are trying to look for some approximation which we typically called as heuristic ok
some approximate optimization method to obtain feasible and good solution ok. Some people
also call, but not necessarily optimal solution. So, what you are trying while managing the
computational effect computational effort. So, what you are trying to say is that why
when you are looking at a large scale optimization problem. So, then you set for some you try
to tend to use more of an approximate optimization or a heuristic method for getting feasible
and good solutions your aim is to obtain feasible and good solutions.
So, when you do that what you are trying to do is you are sacrificing you are ok with
the scenario where you are not going to get an optimal solution, but the computational
effort can be managed. So, that is the idea in this one. So, the one thing that you need
to learn about this point is called constructive heuristics. So, constructive heuristics is
that aims to build an approximate optimum approximate optimum incrementally. So, step
by step you make an approximate optimum ok an approximate optimum is created one step
at a time ok. So, how do you do values for discrete decision
variables discrete decision variables are chosen one by one. So, you choose these variable
values one by one chosen one by one the discrete decision variable values are chosen one by
one and stopping when a full feasible solution is obtained as long as you have a full feasible
solution and as soon as you get it you stop it ok. Many times many algorithms many times
stopping happens stopping happens upon obtaining first feasible solution. So, many times as
soon as you get your first feasible solution then you stop ok. Sometimes it can happen
in single pass and then some people call it as single pass one pass heuristics and those
kind of stuff ok. So, there are many names and other terminologies
of used in this particular scenario, but the idea is that you basically choose the values
of discrete decision variables you choose them one by one and stopping stop it when
as soon as you get a full feasible solution right all right. So, this method of this approach
is called as a optimization heuristics in this or how do you use heuristics for optimization.
So, we will actually see a simple algorithm and probably see an example soon.
