The Petroleum Supply Planning activity is an important link for the integration of the Petroleum Supply Chain at PETROBRAS as it is responsible for refining the strategic supply planning information to be used at the operational level. In this thesis we set the ground for understanding this important problem and we propose a mathematical model to solve it. Although the solvers in the last decade have evolved enormously, for this particular application we cannot get solutions with satisfactory quality in reasonable computational time with only the initial proposed model. This directed the line of research of this thesis into investigating, in detail, the structure of this problem in order to find more suitable reformulations and algorithms to tackle it. Our primary goal is to solve efficiently the petroleum supply planning problem at PETROBRAS. Nevertheless as a by-product of this endeavor, we propose a novel decomposition algorithm and reformulations based on a cascading knapsack structures that turn out to be applicable in a wide range of problems. Concerning the achievement of the main objective, we obtain good results for all instances we tested. We show that the novel decomposition algorithm is the most fitted method to solve the petroleum supply planning problem if we consider more than two tankers to offload each platform. In the case of one or two tankers to offload each platform, the hull relaxation formulation based on the cascading knapsack structure introduced after an inventory reformulation at platforms is the best option if one is to solve this problem. For the real application, these solution alternatives allow to implement a general algorithm that automatically switches to the best solution option depending on the structure of the problem. For the mixed situation, i.e., number of tanker varying from one to four, one can use more than one approaches in parallel and take the fastest or the best result obtained. This model is being tested at PETROBRAS and is showing to be an effective tool to help integrate its petroleum supply chain as well as to do what-if analysis to look for alternative solutions never thought before.