pith. sign in

arxiv: 1907.02036 · v1 · pith:6NMJYKYBnew · submitted 2019-07-03 · 🧮 math.OC · math.CO· math.MG

Hyperbolic Optimization over the Integer Efficient Set of MOILFP

Fatma Zohra Ouail , Mohamed El-Amine Chergui This is my paper

Pith reviewed 2026-05-25 09:48 UTC · model grok-4.3

classification 🧮 math.OC math.COmath.MG
keywords multi-objective optimizationinteger programminglinear fractional programmingbranch and boundefficient setglobal optimization
0
0 comments X

The pith

A branch and bound method finds the optimum of a linear fractional function over the efficient set of a multi-objective linear fractional integer program without generating all efficient solutions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a branch and bound algorithm to optimize one linear fractional objective over the efficient solutions of a multi-objective linear fractional integer program. The efficient set is discrete and non-convex, making direct optimization difficult, so the method searches for a solution that is both optimal for the single objective and efficient for the multiple ones. This avoids the need to list every efficient point, which becomes impractical as problem size grows. Tests on random instances with up to 120 variables, 100 constraints and 6 criteria show the approach works.

Core claim

The authors describe a branch and bound based method with a double mission to search for an optimal solution for a given linear fractional function which is moreover efficient for a multi-objective linear fractional integer programming problem, without generating all efficient solutions.

What carries the argument

A branch and bound algorithm that prunes the search tree using bounds on the fractional objective and efficiency criteria.

If this is right

  • The method solves the global optimization problem over the discrete efficient set directly.
  • It succeeds on instances with up to 120 variables, 100 constraints and 6 criteria.
  • No full generation of the efficient set is required for the search.
  • The approach handles the non-convex discrete nature of the efficient set through targeted pruning.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The pruning strategy might generalize to optimization over Pareto sets in other classes of integer programs.
  • It could reduce effort in applications that combine multiple fractional criteria with an additional objective.
  • Performance on structured instances rather than random ones could reveal further limits or strengths.

Load-bearing premise

The branch and bound algorithm can effectively prune the search tree using bounds on the fractional objective and efficiency criteria without missing the global optimum or requiring full generation of the efficient set.

What would settle it

An instance where the algorithm returns a solution that is not the true optimum or requires enumerating all efficient solutions to confirm optimality.

read the original abstract

The aim of this study is to find the optimum of a linear fractional function over the efficient set of a multi-objective linear fractional integer program without generating all efficient solutions. By its nature, it is a global optimization problem since the efficient set is discrete, hence not convex. For this purpose, a branch and bound based method is described with a double mission to search for an optimal solution for a given linear fractional function which is moreover, efficient for a multi-objective linear fractional integer programming problem. Tests performed on instances randomly generated up to 120 variables, 100 constraints and 6 criteria are successful.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper presents a branch-and-bound algorithm to optimize a single linear fractional objective over the efficient set of a multi-objective linear fractional integer program (MOILFP) without enumerating all efficient solutions. The method simultaneously enforces efficiency with respect to the multiple fractional criteria while optimizing the additional fractional function, and reports successful computational tests on randomly generated instances with up to 120 variables, 100 constraints, and 6 objectives.

Significance. If the bounding and pruning rules are valid, the approach would offer a practical way to solve a non-convex global optimization problem that arises in applications such as ratio-based efficiency analysis over discrete efficient frontiers. The reported scale of instances (120 variables) suggests the method may be computationally viable where full enumeration of the efficient set is intractable.

major comments (2)
  1. [§3] §3 (Branch-and-bound framework): the description of the lower and upper bounds on the single fractional objective must be shown to remain valid when the efficiency constraints (with respect to the vector of fractional criteria) are relaxed; without an explicit statement of the relaxation used for the multi-objective efficiency test, it is unclear whether the pruning step can discard an optimal efficient solution.
  2. [§4] §4 (Computational results): the tables report only aggregate success rates and CPU times; no information is given on the number of nodes explored, the tightness of the bounds, or the fraction of instances in which the algorithm terminated with a proven optimum versus a feasible efficient point.
minor comments (2)
  1. [§2] Notation for the multi-objective fractional criteria should be introduced once and used consistently; the current alternation between vector notation and component-wise notation in the abstract and §2 is confusing.
  2. [§4] The random instance generator is described only at a high level; parameters controlling the density and coefficient ranges of the constraint matrix should be stated explicitly so that the test bed can be reproduced.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments on our manuscript. We address each major comment below and will incorporate the suggested clarifications and additional computational details in the revised version.

read point-by-point responses

  1. Referee: [§3] §3 (Branch-and-bound framework): the description of the lower and upper bounds on the single fractional objective must be shown to remain valid when the efficiency constraints (with respect to the vector of fractional criteria) are relaxed; without an explicit statement of the relaxation used for the multi-objective efficiency test, it is unclear whether the pruning step can discard an optimal efficient solution.

    Authors: We agree that an explicit statement and validity proof are required. The relaxation used is the standard continuous relaxation of the single fractional objective over the integer feasible set obtained by branching, while the multi-objective efficiency is enforced via the branching rules that eliminate dominated regions. In the revised manuscript we will add a dedicated paragraph in §3 stating the precise relaxed subproblem and proving that the derived lower and upper bounds remain valid (and hence safe for pruning) because any feasible solution to the relaxed problem that violates efficiency is already excluded by the branching process. This guarantees that no optimal efficient solution can be discarded. revision: yes

  2. Referee: [§4] §4 (Computational results): the tables report only aggregate success rates and CPU times; no information is given on the number of nodes explored, the tightness of the bounds, or the fraction of instances in which the algorithm terminated with a proven optimum versus a feasible efficient point.

    Authors: We acknowledge that the current tables provide only aggregate metrics. In the revised version we will augment §4 with additional statistics drawn from the same experimental runs: average number of nodes explored, average relative gap between lower and upper bounds at termination, and the fraction of instances in which the algorithm returned a proven optimum versus a feasible efficient point only. These data will be presented in a new table or as supplementary text. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algorithmic construction is self-contained

full rationale

The paper describes a branch-and-bound algorithm to optimize a single linear fractional objective over the efficient set of a multi-objective integer linear fractional program without enumerating the full set. The approach relies on standard bounding and pruning techniques for both the fractional objective and efficiency conditions. No self-definitional reductions, fitted parameters renamed as predictions, or load-bearing self-citations appear in the abstract or described method; the derivation chain consists of independent algorithmic steps whose validity is not forced by redefinition of the inputs. This is the expected non-finding for an optimization algorithm paper whose central contribution is a constructive procedure rather than a fitted or self-referential claim.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available, so no specific free parameters, axioms, or invented entities can be identified from the text. The method likely builds on standard assumptions in integer programming and multi-objective optimization.

pith-pipeline@v0.9.0 · 5629 in / 1055 out tokens · 35377 ms · 2026-05-25T09:48:58.562191+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

53 extracted references · 53 canonical work pages

  1. [1]

    Benson, H.(1984), Optimization over the efficient set, Jou rnal of Mathematical Analysis and Applications 98, pp. 562-580. 16 FZ. OUAIL et al

    work page 1984

  2. [2]

    (1986), An algorithm for optimizing over the we akly efficient set, Eu- ropean Journal of Operational Research 25, pp

    Benson, H. (1986), An algorithm for optimizing over the we akly efficient set, Eu- ropean Journal of Operational Research 25, pp. 192-199

    work page 1986

  3. [3]

    (1992) , A Bisection-Extreme Point Search Algo rithm for Optimizing over the Efficient Set in the Linear Dependence Case, Discussi on paper, 1992

    Benson, H. (1992) , A Bisection-Extreme Point Search Algo rithm for Optimizing over the Efficient Set in the Linear Dependence Case, Discussi on paper, 1992

    work page 1992

  4. [4]

    Song (1994), Optimizing a linear functio n over an efficient set, Journal of Optimization Theory and Application Vol 83, pp

    J, Ecker and J.H. Song (1994), Optimizing a linear functio n over an efficient set, Journal of Optimization Theory and Application Vol 83, pp. 5 41-563

    work page 1994

  5. [5]

    (1991), Optimization over the efficient set using an active constraint approach

    Dauer, J. (1991), Optimization over the efficient set using an active constraint approach. Zeitschrift for Operations Research, 35(3):185 -195

    work page 1991

  6. [6]

    Operations Research, 48(1):65 72

    Sayin, S.(2000), Optimizing over the efficient set using a t op-down search of faces. Operations Research, 48(1):65 72

    work page 2000

  7. [7]

    Yamamoto, Y. (2002). Optimization over the efficient set: o verview. Journal of Global Optimization, 22(1-4):285317

    work page 2002

  8. [8]

    (1972), Algorithm for the Vector Maximization Problem, Mathematical Programming 2, 1972, pp

    Philip, J. (1972), Algorithm for the Vector Maximization Problem, Mathematical Programming 2, 1972, pp. 207-229

    work page 1972

  9. [9]

    (2008), An exact method for a dis crete multiobjective linear fractional optimization

    Chergui, M-E-A, Moula, M. (2008), An exact method for a dis crete multiobjective linear fractional optimization. J Appl Math Deci sci. 2008 ; vol.2008 : Article ID 760191, 12 pages. http ://dx.doi.org/10.1155/2008/76019 1

    work page doi:10.1155/2008/76019 2008

  10. [10]

    (1984), Algorithm to determine an i nitial efficient basic solution for a linear fractional multiple objective transp ortation problem

    Datta, N., Bhatia, D. (1984), Algorithm to determine an i nitial efficient basic solution for a linear fractional multiple objective transp ortation problem. Cahiers Centre Etudes Rech.Oper, Kaiser-slauternol, 26/ 1-2, 127- 136

    work page 1984

  11. [11]

    (2009), An algorithm for optimizing a linear f unction over an integer efficient set

    Jorge, JM. (2009), An algorithm for optimizing a linear f unction over an integer efficient set. Eur J Oper Res.;195 :98103

    work page 2009

  12. [12]

    (2015), A linear fractional opti mization over an integer efficient set

    Mahdi, S., Chaabane, D. (2015), A linear fractional opti mization over an integer efficient set. RAIRO-Oper. Res.; 49 : 265-278. DOI : 10.1051/r o/2014036

    work page doi:10.1051/r 2015

  13. [13]

    Wassila Drici, Fatma Zohra Ouail (2017), Mustapha Moula , Optimizing a linear fractional function over the integer efficient set, Annals of Operations Research

    work page 2017

  14. [14]

    (2003), Minimu m maximal flow problem An optimization over the efficient set

    Shigeno, M., Takahashi, I., Yamamoto, Y. (2003), Minimu m maximal flow problem An optimization over the efficient set. Journal of Global Opti mization, 22, 425-443

    work page 2003

  15. [15]

    (2011), Optimization over an inte ger efficient set of a multiple objective linear fractional problem

    Zerdani, O., Moula, M. (2011), Optimization over an inte ger efficient set of a multiple objective linear fractional problem. App Mat Sci. ; 5/50 :24512466

    work page 2011

  16. [16]

    Boland, Natashia, Charkhgard, Hadi, Savelsbergh, Mart in (2016), A new method for optimizing a linear function over the efficient set of a mul tiobjective integer program European Journal of Operational Research

    work page 2016

  17. [17]

    and Chaabane, D.(2006), Optimizing a linear fu nction over an integer efficient set, European Journal of Operational Research 174, pp 1140-1161

    Abbas, M. and Chaabane, D.(2006), Optimizing a linear fu nction over an integer efficient set, European Journal of Operational Research 174, pp 1140-1161

    work page 2006

  18. [18]

    Nguyen (1992), An algorithm for optimizing a linear function over the integer efficient set, Konrad-Zuse-Zentrum fur Informationstechni k Berlin

    N.C. Nguyen (1992), An algorithm for optimizing a linear function over the integer efficient set, Konrad-Zuse-Zentrum fur Informationstechni k Berlin

    work page 1992

  19. [19]

    Gilmore and R.E

    P.C. Gilmore and R.E. Gomory (1963), A linear programmin g approach to the cutting stock problem-Part II. Operations Resemrh, 11:863 -888

    work page 1963

  20. [20]

    Ishii, T

    H. Ishii, T. lbaraki, and H. Mine. Fractional knapsack pr oblems. Mathematical Programming, 13:255-271, 1977

    work page 1977

  21. [21]

    Myung and D

    Y. Myung and D. Tcha. (1991), Return of investment analys is for facility location. Technical Report OR 251-91, Massachusetts Institute of Tec hnology

    work page 1991

  22. [22]

    Kouada (1975), Finding efficient points for linear multiple objective programs, Mathematical Programming 8, pp 375-377

    J, Ecker and I. Kouada (1975), Finding efficient points for linear multiple objective programs, Mathematical Programming 8, pp 375-377

    work page 1975

  23. [23]

    Gupta and R

    R. Gupta and R. Malhotra (1992), Multi-criteria integer linear programming prob- lem, Cahiers de CERO 34, pp. 51-68

    work page 1992

  24. [24]

    Gupta and R

    R. Gupta and R. Malhotra (1995), Multi-criteria integer linear fractional program- ming problem, Optimization 35, pp. 373-389

    work page 1995

  25. [25]

    Isermann (1974), Proper efficiency and the linear vecto r maximization problem, Operations Research 22, pp 189-191

    H. Isermann (1974), Proper efficiency and the linear vecto r maximization problem, Operations Research 22, pp 189-191. Hyperbolic Optimization over the Integer Efficient Set of MOI LFP 17

    work page 1974

  26. [26]

    Klein and E

    D. Klein and E. Hannan (1982), An algorithm for multiple o bjective integer linear programming problem, European Journal of Operational Rese arch 9, pp. 378-385

    work page 1982

  27. [27]

    Kirlik, Gokhan and Sayin, Serpil, (2014), A new algorith m for generating all non- dominated solutions of multiobjective discrete optimizat ion problems, European Journal of Operational Research, 232, issue 3, p. 479-488

    work page 2014

  28. [28]

    Ozlen and M

    M. Ozlen and M. Azizoglu (2009), Multi-objective intege r programming: A gen- eral approach for generating all non-dominated solutions; presented at European Journal of Operational Research, pp.25-35

    work page 2009

  29. [29]

    Sylva and A

    J. Sylva and A. Crema (2003), A method for finding the set of non-dominated vectors for multiple objective integer linear programs, Eu ropean Journal of Oper- ational Research, in press

    work page 2003

  30. [30]

    R. E. Steuer (1986), Multiple Criteria Optimization: Th eory, Computation, and Application, John Wiley & Sons

    work page 1986

  31. [31]

    Benson, HP (1997), ”Generating the efficient outcome set i n multiple-objective linear programs: the bicriteria case.” Acta Mathematica Vi etnamica, vol. 22, pp. 29-51

    work page 1997

  32. [32]

    70, no.3, pp

    Armand, P & Malivert, C 1991, ”Determination of the efficie nt set in multiobjective linear programming.” Journal of Optimization Theory and Ap plications, vol. 70, no.3, pp. 467-489. 3

    work page 1991

  33. [33]

    Armand, P 1993, ”Finding all maximal efficient faces in mul tiobjective linear pro- gramming.” Mathematical Programming, vol. 61, no. 1-3, pp. 357-375

    work page 1993

  34. [34]

    Ida, M (2005), ”Efficient solution generation for multipl e objective linear program- ming based on extreme ray generation method.” European Jour nal of Operational Research, vol. 160, no. 1, pp. 242-251

    work page 2005

  35. [35]

    Gonzales, G.R

    J.J. Gonzales, G.R. Reeves, L.S. Franz (1985), An Intera ctive Procedure for Solving Multiple Objective Integer Linear Programming Pro blems, in Haimes Y. and Chankong (eds), Decision Making with Multiple Objectiv es, Springer-Verlag, Berlin 250-260

    work page 1985

  36. [36]

    Maria Joao Alves and Joao Climaco (2000), An Interactive Reference Point Ap- proach for Multiobjective Mixed-Integer Programming usin g Branch-and-Bound, European Journal of Operational Research 124 3 478-494

    work page 2000

  37. [37]

    Shapiro (1976), Multiple Criteria Public Investme nt Decision Making by Mixed Integer Programming, in Thiriez H

    J.F. Shapiro (1976), Multiple Criteria Public Investme nt Decision Making by Mixed Integer Programming, in Thiriez H. & Zionts S. (eds), M ultiple Criteria Decision Making, Springer-Verlag, Berlin 170-181

    work page 1976

  38. [38]

    Ulungu, J

    E.L. Ulungu, J. Teghem (1992), Heuristic for Multi-obje ctive Combinatorial Op- timization Problems with Simulated Annealing, paper prese nted at EURO XII congress, Helsinki June (1992)

    work page 1992

  39. [39]

    Ulungu, J

    E.L. Ulungu, J. Teghem (199), Multi-objective Combinat orial Optimization Prob- lems : A survey, Journal of Multi-Criteria Decision Analysi s, Vol. 3 83-104

    work page

  40. [40]

    and Steuer R.E

    Kornbluth J.S.H. and Steuer R.E. (1981), Multiple Objec tive Linear Fractional Programming, Management Science 27 : 1024-1039

    work page 1981

  41. [41]

    Markowitz, H. M. (1959), Portfolio Selection: Efficient D iversification of Invest- ments, John Wiley and Sons, New York, pp. 77-91

    work page 1959

  42. [42]

    Steuer, R. E., Y. Qi and M. Hirschberger (2007). Suitable -Portfolio Investors, Non- dominated Frontier Sensitivity, and the Effect on Standard P ortfolio Selection, Annals of Operations Research, Vol. 152, pp. 297-317

    work page 2007

  43. [43]

    Steuer, R. E., M. Wimmer and M. Hirschberger (2013). Over viewing the Transition of Markowitz Bi-Criterion Portfolio Selection to Tri-Crit erion Portfolio Selection, Journal of Busi- ness Economics, Vol. 83, No. 1, pp. 61-85. 18 FZ. OUAIL et al

    work page 2013

  44. [44]

    & Chergui, M.EA

    Oual, F.Z. & Chergui, M.EA. (2017), A branch-and-cut tec hniqque to solve the multiobjective integer quadratic programming problem, An n Oper Res (2017). https ://doi.org/10.1007/s10479-017-2698- 6, 2017

    work page doi:10.1007/s10479-017-2698- 2017

  45. [45]

    Gilmore and R.E

    P.C. Gilmore and R.E. Gomory (1963). A linear programmin g approach to the cutting stock problem-Part II. Operations Resemrh, 11:863 -888

    work page 1963

  46. [46]

    Ishii, T

    H. Ishii, T. lbaraki, and H. Mine (1977). Fractional knap sack problems. Mathe- matical Programming, 13:255-271

    work page 1977

  47. [47]

    Myung and D

    Y. Myung and D. Tcha (1991). Return of investment analysi s for facility location. Technical Report OR 251-91, Massachusetts Institute of Tec hnology

    work page 1991

  48. [48]

    (1977), Minimal ratio spanning tree s, Networks 7, 355-342

    Chandrasekaran, R. (1977), Minimal ratio spanning tree s, Networks 7, 355-342. 3

    work page 1977

  49. [49]

    BAJALINOV, ERIK B. (2003). Linear-Fractional Programm ing: Theory, Methods, Applications and Software. Kluwer Academic Publishers, Do rdrecht, The Nether- lands. 423 pp

    work page 2003

  50. [50]

    I.(1998), Discrete and Fractional Programmi ng Techniques for Location Models, Combinatorial Optimization, p.180, Springer US

    Barros, A. I.(1998), Discrete and Fractional Programmi ng Techniques for Location Models, Combinatorial Optimization, p.180, Springer US

    work page 1998

  51. [51]

    Cambini and L

    A. Cambini and L. Martein (1992), ”Equivalence in linear fractional programming,” Optimization, vol. 23, no. 1, pp. 4151

    work page 1992

  52. [52]

    P.(1978) Existence of efficient solutions for ve ctor maximization prob- lems, Journal of Optimization Theory and Appl,26,569-580

    Benson H. P.(1978) Existence of efficient solutions for ve ctor maximization prob- lems, Journal of Optimization Theory and Appl,26,569-580

    work page 1978

  53. [53]

    C. R. Seshan and V. G. Tikekar (1980), ”Algorithms for int eger fractional pro- gramming,” Journal of the Indian Institute of Science, vol. 62, no. 2, pp. 9-16

    work page 1980