GA 2.5 Report: Optimization¶

CEGM1000 MUDE: Week 2.5. Due: December 13, 2024.

Questions¶

Solving NDP problem with MILP¶

Run the model. Has the optimal solution been found? (yes/no)

You need to check the Gap. If there is a Gap, you cannot prove the optimal solution. If the Gap is zero, then yes, you’ve found the optimal solution.

If there is a gap, what can you tell about the value of the best solution that you are still theoretically able to obtain?

If the Gap is zero, that’s it. If a Gap exists, you must return the best bound from the results or calculate it yourself: Objective * (1 - Gap).

Consider now that the network operator does not want to surpass the capacity in the links. How do you write that constraint mathematically? Reminding you that in the current model it is possible to go beyond the capacity.

You need to impose the capacity constraint on each link.

Run the model with the new constraint. What changed in the network as a result of imposing the constraint?

c_new = model.addConstrs(link_flow[i, j] <= cap_normal[i,j] + ((cap_extend[i,j]-cap_normal[i,j] ) * link_selected[i,j])  for (i, j) in links)

You perform cap_extend[i,j] - cap_normal[i,j] because the extended capacity includes the normal capacity. There may be alternative ways to write this.

The changes in the network are that the links no longer surpass their capacity. The flows on the road network will change. You can illustrate this with maps.

Solving NDP problem with GA¶

5.What very important solution performance indicator did you lose by using the GA metaheuristic in comparison with MILP?

It’s the Gap. With the genetic algorithm, you never know if you are far or close to the optimal solution unless you have a benchmark from the mathematical programming. However, you can use the convergence of the curve as an indicator of approaching a better solution.

Change the parameters of the algorithm and see if it changes the performance.

Try changing the population size and the crossover operator (currently HalfUniformCrossover(), change it to PointCrossover()) to see how this affects performance.

There’s no definitive answer to what you’ll get 😊. Increasing the population size will increase diversity, which might help convergence, but it will also require more evaluations of the objective function per generation.

Is the GA a better algorithm to solve this problem than the math program?

For a duration of 300 seconds, it depends on the configuration of the algorithm. Compare the objective function results for both approaches since the maximum time is the same. From tests, linear programming appears to perform better.

General Comments on the Assignment [optional]¶

Use this space to let us know if you encountered any issues completing this assignment (but please keep it short!). For example, if you encountered an error that could not be fixed in your Python code, or perhaps there was a problem submitting something via GitLab. You can also let us know if the instructions were unclear. You can delete this section if you don't use it.

End of file.