Parameterisation algorithms for the integer linear programs in binary variables
In this paper problems of parametric integer linear programming (ILP) are discussed. Consider the problem: (ILP) minimize \(z(x)=\sum_{j\in J}c_ jx_ j\) subject to A\(X\leq b\), \(x_ j=0\), 1. Due to Roodman's well-known postoptimality analysis scheme a modified version of Balas' additive algorithm is used and each of the fathomed partial solutions (FPS) is attributed to the constraint which caused the fathoming. The set \(\Lambda\) of FPS is partitioned into \(m+1\) disjoint sets. In this paper a parametric function \(z^*(\xi(\lambda))\) for any single parameter \(\xi \in \{c_ j,a_{ij},b_ i:i\in I\), \(j\in J\}\), \(\xi(\lambda)=\xi +\lambda\) is constructed. The function \(z^*(\xi(\lambda))\) matches nonoverlapping intervals of \(\lambda\) with optimal solutions and their associated objective function values. Contrasted to Roodman's collection and classification scheme the proposed algorithm employs additional bounding tests which result in a substantial reduction in the number of FPS necessary for the construction of \(z^*(\xi(\lambda))\). Computational experience was conducted on a UNIVAC 1106, computer programs were written in FORTRAN V and tested on more than 1000 randomly generated problems.
- An algorithm to perform a complete parametric analysis relative to the constraint matrix for a 0-1-integer linear program
- A branch-and-bound algorithm for 0-1 parametric mixed integer programming
- Parametric mixed-integer 0-1 linear programming: The general case for a single parameter
- An algorithm to perform a complete right-hand-side parametrical analysis for a 0-1-integer linear programming problem
- An algorithm for the multiparametric 0--1-integer linear programming problem relative to the objective function
- A hybrid approach to discrete mathematical programming
- A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
- An Additive Algorithm for Solving Linear Programs with Zero-One Variables
- Computational Complexity of Some Problems in Parametric Discrete Programming. I
- Discrete right hand side parametrization for linear integer programs
- Exceptional Paper—Parametric and Postoptimality Analysis in Integer Linear Programming
- Finding All Solutions for a Class of Parametric Quadratic Integer Programming Problems
- scientific article; zbMATH DE number 3554027 (Why is no real title available?)
- scientific article; zbMATH DE number 3564693 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- scientific article; zbMATH DE number 3323652 (Why is no real title available?)
- Implicit enumeration based algorithms for postoptimizing zero-one programs
- Integer Programming Post-Optimal Analysis with Cutting Planes
- Parameterisation algorithms for the integer linear programs in binary variables
- Parametric integer linear programming: A synthesis of branch and bound with cutting planes
- Parametric Integer Programming Analysis: A Contraction Approach
- Parametric Multicriteria Integer Programming
- Postoptimality analysis in integer programming by implicit enumeration: The mixed integer case
- Postoptimality analysis in zero‐one programming by implicit enumeration
- Reporting computational experiments in mathematical programming
- Some Easy Postoptimality Analysis for Zero-One Programming
- The Structure of Integer Programs under the Hermitian Normal Form
- The value function of an integer program
- A shadow price in integer programming for management decision
- An algorithm to perform a complete right-hand-side parametrical analysis for a 0-1-integer linear programming problem
- A contraction for the multiparametric integer linear programming problem
- Parametric uncapacitated facility location
- Parametric methods in integer linear programming
- Three methods for postoptimal analysis in integer linear programming
- scientific article; zbMATH DE number 3970524 (Why is no real title available?)
- scientific article; zbMATH DE number 3970525 (Why is no real title available?)
- Analyse de sensibilité pour les problèmes linéaires en variables 0-1
- Parametric-objective integer programming using knapsack facets and Gomory cutting planes
- Parameterisation algorithms for the integer linear programs in binary variables
- An adapted step size algorithm for a 0-1 biknapsack Lagrangean dual
- Parametric mixed-integer 0-1 linear programming: The general case for a single parameter
This page was built for publication: Parameterisation algorithms for the integer linear programs in binary variables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q795729)
