PT. XYZ is one of the companies which engages in fast moving consumer goods (FMCG) sector and has soft drinks as its main product. In supporting the product distribution to its customers, PT XYZ has several administrative offices and distribution centers (DC) which spread across each region. The DC has main function as the warehouse which has storage activity before the products are distributed. One of the DC is located in Bandung, West Java. DC Bandung itself received product shipments from three factories, such as Cibitung, Cakung and Tambun. Related to the product shipment, DC Bandung has not determined the replenishment policy, and this condition results over stock at some periods, due to the unscheduled delivery time and undetermined product quantity. This condition gives a big impact to the total inventory cost that has to be borne by DC Bandung. This research was conducted to give the proposal of product replenishment policy with mixed-integer programming method, as one of the linear programming types, which aimed to minimize over stock and total holding cost in DC Bandung. Mathematical model is also involved in this research as an approximation to the real replenishment system in the DC. The results of application of the proposed method are in the form of analytical solution, such as order quantity, and reorder point of each product that will give an impact to the total unit inventory and the total holding cost in the DC. The results calculation of replenishment policy provide savings on total inventory costs as much as IDR 23,800,981.20