1,721,006 research outputs found
An Algorithm for Approximate Multiparametric Linear Programming
No full textMultiparametric programming considers optimization problems where the data are functions of a parameter vector and describes the optimal value and an optimizer as explicit functions of the parameters. In this paper, we consider a linear program where the right-hand side is an affine function of a parameter vector; we propose an algorithm for approximating its solution. Given a full-dimensional simplex in the parameter space and an optimizer for each simplex vertex, the algorithm formulates the linear interpolation of the given solutions as an explicit function of the parameters, giving a primal feasible approximation of an optimizer inside the simplex. If the resulting absolute error in the objective exceeds a prescribed tolerance, then the algorithm subdivides the simplex into smaller simplices where it applies recursively. We propose both a basic version and a refined version of the algorithm. The basic version is polynomial in the output size, provided a polynomial LP solver is used; the refined version may give a smaller output. A global error bound for the optimizer is derived and some computational tests are discussed
A two-phase method for bi-objective combinatorial optimization and its application to the TSP with profits
Full text linkWe study a variant of the two-phase method for general bi-objective combinatorial optimization problems. First, we analyze a basic enumerative procedure, often used in literature to solve specific bi-objective combinatorial optimization problems, making it suitable to solve general problems. We show that the procedure generates the exact set E of efficient points by solving exactly 2|E| - 1 single objective problems. Second, we embed the procedure in a classic two-phase framework, where supported points are computed in the first phase and unsupported points are computed in the second phase.
We test the refined approach on a hard problem, namely the Traveling Salesman Problem with Profits, a bi-objective generalization of the well known Traveling Salesman Problem. On the tested instances, the procedure outperforms the epsilon-constraint method, one of the most used approaches to solve exactly general bi-objective combinatorial optimization problems
Approximation schemes for bi-objective combinatorial optimization and their application to the TSP with profits
No full textWe describe two approximation schemes for bi-objective combinatorial optimization problems with nonnegative, integer valued objectives. The procedures compute a subset of the efficient points such that any other efficient point is within an arbitrary factor from a computed one with respect to both objectives. Both schemes are simple modifications of classical algorithms for the construction of the whole efficient set.
In both procedures, a properly defined single objective subproblem has to be solved at every iteration. We show that, in both cases, the number of subproblems to be solved and the number of returned efficient points are polynomial in the input size and the reciprocal of the allowed error. We also show that a fast post-processing guarantees that the number of returned efficient points is at most three times the minimum possible number needed to approximate the efficient set within the specified tolerance.
We test the procedures on the Traveling Salesman Problem with Profits, where profits and costs are treated as conflicting objectives. Results are taken on randomly generated instances and on TSPLIB instances. We show that both algorithms return a guaranteed approximation with significant time sparing with respect to exact procedures. We also give empirical evidence
that in the specific application the number of points returned by the approximation schemes is close to the minimum
Sensitivity analysis in linear programming
No full textSensitivity analysis in linear programming studies the stability of optimal solutions and the optimal objective value with respect to perturbations in the input data. This analysis is often relevant in practical applications. We discuss the main approaches to sensitivity analysis, including ordinary sensitivity, the 100% rule, and the tolerance approach, giving special attention to degeneracy issues. We focus on the effects of perturbations in the right-hand side and objective vectors
- …
