4 ms·
Relating to the article on construction, I think this may be an instance where the theory breaks down in practice. Construction jobs aren’t just optimal linear
by bumby 4y ago
Relating to the article on construction, I think this may be an instance where the theory breaks down in practice. Construction jobs aren’t just optimal linear programming because the order often impacts both the costs and duration of subsequent work, making much of it nonlinear.
- eru 4y agoLinear integer programming can model these kinds of dependencies.
- bumby 4y agoCan you elaborate? My understanding is they can in an iterative fashion, but the dependencies I’m talking about are not constraints but nonlinear dependencies between decision variables. As an example, the decision variables may be integers denoting schedule blocks, but the cost is a nonlinear function of time and the other variables. Meaning each time block can be solved with linear programming iteratively, but to solve across all time blocks requires nonlinear optimization
- eru 4y agoThe general answer is that linear integer programming is NP-complete. The more specific answer is that you can abuse integer variables to do Boolean logic and then eg model piece-wise linear functions relatively easily. In practice, this abuse might or might not be very performant, it depends on exactly what you are doing and what your solving is doing. It might be fine, or you might be better off with quadratic or complex programming solvers. If you have a more specific example, I can try to model it.
- bumby 4y agoSay we have some equipment condition estimated by time variant non-linear function like the Weibull reliability function. [1] Say the cost of repair is based on a nonlinear relationship between between the equipment replacement cost and current condition. Something like cost = replace_cost * [(100-current_condition)/(100 - failing_condition)]^2 After repair, the condition increases to some assumed value (say, 95). The overall facility condition is the cost-weighted average of the constituent equipment conditions at any point in time. facility_cond = sum(equip_cond * equip_cost)/sum(equip_cost) I want to plan repairs over some time period (say, 10 years) to optimize facility condition within some budget. Can I do this with linear programming? I can set it up as a linear problem for a single snapshot in time, but haven't thought of a way to efficiently do it as a linear program concurrently across multiple time steps. [1] https://weibull.com/hotwire/issue7/relbasics7.htm https://weibull.com/hotwire/issue7/relbasics7.htm
- eru 4y agoYou _can_ do this as a mixed integer linear program. Whether it's a good idea, is another question.
- bumby 4y agoHow would one go about setting that up? It’s been done on a per year basis, but every approach that looks at multiple years seems to require non-linear optimization
- eru 4y agoYou can implement piecewise-linear functions with mixed integer linear programming. (And, of course: piecewise-linear != linear.) See eg https://web.mit.edu/15.053/www/AMP-Chapter-09.pdf https://web.mit.edu/15.053/www/AMP-Chapter-09.pdf for some examples of simulating non-linear constraints in integer programming.
- Lio 4y agoThat’s sounds like a slightly different problem than scheduling operations to carry some complex construction activity, which I think is what is being discussed. I believe John Sterman used System Dynamics to model maintenance schedules in oil refineries. I’m an amateur at this but that sounds like a better fit to model what you’ve proposed.
- bumby 4y agoNonlinear programming has been used in similar construction problems, like maritime platforms. They usually optimize for something like availability. My issue is that there’re seems too be too much variance in the assumptions (like repair time or inspection duration) to make them practical.