Joint Binary-Continuous Fractional Programming: Solution Methods and Applications
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911364289658880 |
|---|---|
| author | Pham, Hoang Giang Duong, Ngan Ha Mai, Tien Ta, Thuy Anh Ha, Minh Hoang |
| author_facet | Pham, Hoang Giang Duong, Ngan Ha Mai, Tien Ta, Thuy Anh Ha, Minh Hoang |
| contents | In this paper, we investigate a class of non-convex sum-of-ratios programs relevant to decision-making in key areas such as product assortment and pricing, and facility location and cost planning. These optimization problems, characterized by both continuous and binary decision variables, are highly non-convex and challenging to solve. To the best of our knowledge, no existing methods can efficiently solve these problems to near-optimality with arbitrary precision. To address this challenge, we propose an innovative approach based on logarithmic transformations and piecewise linear approximation (PWLA) to approximate the nonlinear fractional program as a mixed-integer convex program with arbitrary precision, which can be efficiently solved using cutting plane (CP) or Branch-and-Cut (B&C) procedures. Our method offers several advantages: it allows for a shared set of binary variables to approximate nonlinear terms and employs an optimal set of breakpoints to approximate other non-convex terms in the reformulation, resulting in an approximate model that is minimal in size. Furthermore, we provide a theoretical analysis of the approximation errors associated with the solutions derived from the approximated problem. We demonstrate the applicability of our approach to constrained competitive joint facility location and cost optimization, as well as constrained product assortment and pricing problems. Extensive experiments on instances of varying sizes, comparing our method with several alternatives, including general-purpose solvers and more direct PWLA-based approximations, show that our approach consistently achieves superior performance across all baselines, particularly in large-scale instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_02152 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Joint Binary-Continuous Fractional Programming: Solution Methods and Applications Pham, Hoang Giang Duong, Ngan Ha Mai, Tien Ta, Thuy Anh Ha, Minh Hoang Optimization and Control In this paper, we investigate a class of non-convex sum-of-ratios programs relevant to decision-making in key areas such as product assortment and pricing, and facility location and cost planning. These optimization problems, characterized by both continuous and binary decision variables, are highly non-convex and challenging to solve. To the best of our knowledge, no existing methods can efficiently solve these problems to near-optimality with arbitrary precision. To address this challenge, we propose an innovative approach based on logarithmic transformations and piecewise linear approximation (PWLA) to approximate the nonlinear fractional program as a mixed-integer convex program with arbitrary precision, which can be efficiently solved using cutting plane (CP) or Branch-and-Cut (B&C) procedures. Our method offers several advantages: it allows for a shared set of binary variables to approximate nonlinear terms and employs an optimal set of breakpoints to approximate other non-convex terms in the reformulation, resulting in an approximate model that is minimal in size. Furthermore, we provide a theoretical analysis of the approximation errors associated with the solutions derived from the approximated problem. We demonstrate the applicability of our approach to constrained competitive joint facility location and cost optimization, as well as constrained product assortment and pricing problems. Extensive experiments on instances of varying sizes, comparing our method with several alternatives, including general-purpose solvers and more direct PWLA-based approximations, show that our approach consistently achieves superior performance across all baselines, particularly in large-scale instances. |
| title | Joint Binary-Continuous Fractional Programming: Solution Methods and Applications |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2211.02152 |