Event and clock based representations of time in mathematical optimization

Abstract

Time representation is one of the most important issues in mathematical optimization in terms of computational time and e ciency. The discrete time formulation requires large number of binary variables which a ects the solution time of the problems. Instead of relying on the traditional uniform discretization of the time horizon, the event-based formulations are proposed to deal with the instances that have a long horizon. In the event-based approach, events are the situations that cause a change in the system and mathematical model is constructed based on the events. In this study, rst, we brie y review the main characteristics of the two approaches and outline their advantages and disadvantages. Then, we focus on the event-based formulations of the two problems: location and scheduling problem (LASP) in wireless sensor networks (WSN) and berth allocation problem (BAP). We try to generalize the event-based formulations for di erent types of problems. In order to enhance the event-based formulations, we strengthen the constraints. Finally, we propose a branch and price algorithm by decomposing the models based on events. Although it provides bounds, which are better than the linear programming relaxation of original formulation, the branch and price algorithm is not very e cient. We also propose simple heuristics to nd good feasible solutions. In our experiments, we compare two modeling approaches by solving the formulations using a state-of-the-art solver on the generated test bed. Then, we assess the performance of the branch and price algorithm. According to our experiments, generally the event-based formulations require less computational time. However, nding an optimum event number can require considerable computational e ort. The decision maker should choose the best representation of time based on the advantages and disadvantages of the two approaches.