Branch-and-bound for bi-objective integer programming
From MaRDI portal
Abstract: In bi-objective integer optimization the optimal result corresponds to a set of non-dominated solutions. We propose a generic bi-objective branch-and-bound algorithm that uses a problem-independent branching rule exploiting available integer solutions and takes advantage of integer objective coefficients. The developed algorithm is applied to bi-objective facility location problems, to the bi-objective set covering problem, as well as to the bi-objective team orienteering problem with time windows. In the latter case, lower bound sets are computed by means of column generation. Comparison to state-of-the-art exact algorithms shows the effectiveness of the proposed branch-and-bound algorithm.
Recommendations
- Branch-and-bound and objective branching with three or more objectives
- An exact algorithm for biobjective integer programming problems
- Bi-objective branch-and-cut algorithms based on LP relaxation and bound sets
- Branching with hyperplanes in the criterion space: the frontier partitioner algorithm for biobjective integer programming
- Multi-objective branch and bound
Cites work
- A bi-objective home care scheduling problem: analyzing the trade-off between costs and client inconvenience
- A branch and bound algorithm for mixed zero-one multiple objective linear programming
- A comparison of stochastic programming and bi-objective optimisation approaches to robust airline crew scheduling
- A computational study of exact approaches for the bi-objective prize-collecting Steiner tree problem
- A criterion space search algorithm for biobjective integer programming: the balanced box method
- A criterion space search algorithm for biobjective mixed integer programming: the triangle splitting method
- A generic branch-and-cut algorithm for multiobjective optimization problems: application to the multilabel traveling salesman problem
- A multiobjective branch-and-bound framework: application to the biobjective spanning tree problem
- A Primer in Column Generation
- An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
- Benchmarking optimization software with performance profiles.
- Bicriteria Transportation Problem
- Bound sets for biobjective combinatorial optimization problems
- Column generation for bi-objective vehicle routing problems with a MIN-MAX objective
- Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming
- Diversity Maximization Approach for Multiobjective Optimization
- Fathoming rules for biobjective mixed integer linear programs: review and extensions
- Multicriteria Optimization
- Multiple objective branch and bound for mixed 0-1 linear programming: corrections and improvements for the biobjective case
- On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization
- Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints
- The bi-objective stochastic covering tour problem
- Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem
Cited in
(31)- Branch-and-bound as a higher-order function
- A branch-and-bound algorithm for a class of mixed integer linear maximum multiplicative programs: a bi-objective optimization approach
- A hybrid approach for biobjective optimization
- Fathoming rules for biobjective mixed integer linear programs: review and extensions
- Branching with hyperplanes in the criterion space: the frontier partitioner algorithm for biobjective integer programming
- Equidistant representations: connecting coverage and uniformity in discrete biobjective optimization
- A two-stage approach for bi-objective integer linear programming
- An exact algorithm for biobjective integer programming problems
- A decision space algorithm for multiobjective convex quadratic integer optimization
- An \(\varepsilon \)-constraint column generation-and-enumeration algorithm for bi-objective vehicle routing problems
- Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs
- Branch-and-bound and objective branching with three or more objectives
- A multiobjective branch-and-bound framework: application to the biobjective spanning tree problem
- ILP heuristics and a new exact method for bi-objective 0/1 ILPs: application to fttx-network design
- scientific article; zbMATH DE number 1784662 (Why is no real title available?)
- BRANCHING TECHNIQUE FOR A BI-OBJECTIVE TWO-STAGE ASSIGNMENT PROBLEM
- Branch-and-Bound for Biobjective Mixed-Integer Linear Programming
- Network Models for Multiobjective Discrete Optimization
- Bi-objective branch-and-cut algorithms based on LP relaxation and bound sets
- Optimising makespan and energy consumption in task scheduling for parallel systems
- Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods
- The hiking tourist problem
- Augmenting bi-objective branch and bound by scalarization-based information
- An outer approximation algorithm for generating the Edgeworth-Pareto hull of multi-objective mixed-integer linear programming problems
- Engineering and evaluating multi-objective pseudo-Boolean optimizers
- An efficient branch-and-bound algorithm to optimize a function over a nondominated set
- Using dual relaxations in multiobjective mixed-integer convex quadratic programming
- A multi-objective perspective on the cable-trench problem
- An exact approach for bi-objective non-identical batch processing machines scheduling
- On improvements of multi-objective branch and bound
- Quadratic convex reformulations for multiobjective binary quadratic programming
This page was built for publication: Branch-and-bound for bi-objective integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5139633)
