RECORD
Relaxations and Duality for Multiobjective Integer Programming
Optimization and Control · Submitted 15 Sep 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We include a numerical experiment to illustrate that bound sets obtained via Lagrangian duality may yield tighter bounds than those from a convex hull relaxation.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Multiobjective integer programs (MOIPs) simultaneously optimize multiple objective functions over a set of linear constraints and integer variables. In this paper, we present continuous, convex hull and Lagrangian relaxations for MOIPs and examine the relationship among them. The convex hull relaxation is tight at supported solutions, i.e., those that can be derived via a weighted-sum scalarization of the MOIP. At unsupported solutions, the convex hull relaxation is not tight and a Lagrangian relaxation may provide a tighter bound. Using the Lagrangian relaxation, we define a Lagrangian dual of an MOIP that satisfies weak duality and is strong at supported solutions under certain conditions on the primal feasible region. We include a numerical experiment to illustrate that bound sets obtained via Lagrangian duality may yield tighter bounds than those from a convex hull relaxation. Subsequently, we generalize the integer programming value function to MOIPs and use its properties to motivate a set-valued superadditive dual that is strong at supported solutions. We also define a simpler vector-valued superadditive dual that exhibits weak duality but is strongly dual if and only if the primal has a unique nondominated point.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Multiobjective integer programs (MOIPs) simultaneously optimize multiple objective functions over a set of linear constraints and integer variables. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | In this paper, we present continuous, convex hull and Lagrangian relaxations for MOIPs and examine the relationship among them. | contribution 1.00 | 0.94 | 0.08 | asserted 0.98 |
| s2 | The convex hull relaxation is tight at supported solutions, i.e., those that can be derived via a weighted-sum scalarization of the MOIP. | result 0.99 | 0.64 | 0.12 | asserted 1.00 |
| s3 | At unsupported solutions, the convex hull relaxation is not tight and a Lagrangian relaxation may provide a tighter bound. | result 0.97 | 0.66 | 0.13 | hedged possibility 0.51 |
| s4 | Using the Lagrangian relaxation, we define a Lagrangian dual of an MOIP that satisfies weak duality and is strong at supported solutions under certain conditions on the primal feasible region. | contribution 0.66 | 0.92 | 0.19 | asserted 0.99 |
| s5 | We include a numerical experiment to illustrate that bound sets obtained via Lagrangian duality may yield tighter bounds than those from a convex hull relaxation. | result 0.58 | 0.96 | 0.13 | hedged possibility 0.97 |
| s6 | Subsequently, we generalize the integer programming value function to MOIPs and use its properties to motivate a set-valued superadditive dual that is strong at supported solutions. | contribution 0.91 | 0.94 | 0.12 | asserted 0.97 |
| s7 | We also define a simpler vector-valued superadditive dual that exhibits weak duality but is strongly dual if and only if the primal has a unique nondominated point. | contribution 0.88 | 0.93 | 0.11 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Multiobjective integer programs (MOIPs) simultaneously optimize multiple objective functions over a set of linear constraints and integer variables. In this paper, we present continuous, convex hull and Lagrangian relaxations for MOIPs and examine the relationship among them. The convex hull relaxation is tight at supported solutions, i.e., those that can be derived via a weighted-sum scalarization of the MOIP. At unsupported solutions, the convex hull relaxation is not tight and a Lagrangian relaxation may provide a tighter bound. Using the Lagrangian relaxation, we define a Lagrangian dual of an MOIP that satisfies weak duality and is strong at supported solutions under certain conditions on the primal feasible region. We include a numerical experiment to illustrate that bound sets obtained via Lagrangian duality may yield tighter bounds than those from a convex hull relaxation. Subsequently, we generalize the integer programming value function to MOIPs and use its properties to motivate a set-valued superadditive dual that is strong at supported solutions. We also define a simpler vector-valued superadditive dual that exhibits weak duality but is strongly dual if and only if the primal has a unique nondominated point.
Human review
How the literature uses it
1 arXiv paper cite this in 1 sentence
Papers citing it
Cites it as background 1 paper
-
More recently, [ref] considered the optimization of multiobjective integer programs through various relaxation and duality approaches, including continuous, convex hull, and Lagrangian relaxations, as well as Lagrangian duals and set- and vector-valued superadditive duals, offering alternative solution methods.
On the Relationship Between the Value Function and the Efficient Frontier of a Mixed Integer Linear Optimization Problem · Multiobjective Optimization · 0.93
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.