I'm studying a combinatorial optimization problem which is related to machine scheduling in a hydraulic system.
We have an objective function and constraints, like a combinatorial optimization problem. However, the parameters of the model are unknow, because we need to simulate the hydraulic system. Therefore, we can use a decision variable vector (the scheduling of a set of machines, in periods of hours) for calculating of hydraulic features of the system. Finally, we can measure the objective function and if the solution is feasible.
It is a minimization problem. I'm interested in obtain lower bounds, for a B&B algorithm, or upper bounds, with heuristics.
This question is difficult to answer, unless you provide more information on the structure of the problem. If you cannot find any, and if you do not have enough information on the functions involved to build a surrogate model, it is better not to use a B&B approach. In that case you might want to look at some heuristic method.
I have decision variables xij =1 if the ith machine is turned on in the jth time step, being 0 otherwise.
The first stage of the process is characterized by the generation of operational rules (variables xij), demand definition and cost (parameters). Next, these variables and parameters are used by the hydraulic simulator, which calculates the pressures in the pipe system nodes, the energy consumed and the levels of the tanks, all of them being necessary to the evaluation of the solution.
The following stage is characterized by the calculation of the objective function which is obtained from the total energy cost and from the penalty function, in case the solution is infeasible. The process is repeated until the parameters of the operational control that attend the hydraulic requirements with the lowest cost possible be obtained.
Metaheuristics were inefficient for this problem, because we hardly ever generate feasible solutions.
B&B is promissing, because we are deleting several unfeasible solutions. If we had bounds, it will be better.
Any strategy for generation of feasible solutions in a heuristic is important too.
As the colleague Hermann Schichl pointed out, you could use a simplified (surrogate) model and relax the integrality constraints, so as to find lower bounds. However as the parameters are functions of the decision variables, I suppose the model is highly nonlinear, which may pose further difficulties in case it is not convex.
Are the constraints given by equations and or inequalities, or are those hidden constraints, i.e., only implicitly given after the simulation?
How much effort do you need for the evaluation at one point? How much overall time do you want to spend for finding the solution? How many decision variables do you have?
Dear Hermann,
Let n the number of pumps and t=24 hours (daily operation), we have 24n binary decision variables.
This is our problem:
http://www.iwaponline.com/ws/01003/ws010030315.htm
Dear Bruno,
after having a very quick look at your model, it seems that a decomposition approach over the time steps could help. It seems that the coupling between the time steps is primarily via the levels of the storage tanks and via the max number of pump activations. Is it that most of the time the limits on the storage tanks fail, or is also the pressure a problem? I cannot say anything detailed since the important part of your model, the connectivity between the variables, etc., is not described in your paper - not even roughly.
The decomposition approach roughly works as follows:
If you make decisions in time step 0 this produces an intermediate result at time step 1 which already reduces your possible choices for all the decision variables in time step 1, etc. This should help you to reduce the number of infeasible solutions, and that is very important since it reduces your search space from 2^(24*n) to some product P_1 P_2 ... P_24, where the P_i are the number of allowed choices in the various time steps. You probably do not need to perform detailed simulations for excluding most of the infeasible solutions, a simplified model should be sufficient.
Anyway, if you can come up with a simplified model roughly reproducing the characteristics of your simulation model, this will definitely produce better results than a generalized surrogate approach.
For a B&B approach you need to dive into your simulation code and get some rough estimate for the energy which has to be spent in minimum to get some feasible solution.
To comment in higher detail, I would need significantly more information on the structure of the simulation model.
Dear Hermann,
Thank you very much for your essential comments! I'll reflect about your considerations and I'll talk with my research collegue about the details that you asked. I'll give you a feedback. Thanks again!
Happy Easter!
- Badges
- Science topic
- Similar topics
- Linguistics
- Composition Studies
- Publication