共查询到20条相似文献,搜索用时 171 毫秒
1.
James P. Ignizio 《European Journal of Operational Research》1983,12(4):357-361
Generalized networks can often provide substantial advantages in both the modeling and solution of integer programming problems. In this paper we present a straightforward approach which combines generalized networks with goal programming so as to achieve a modeling and solution methodology for multiobjective generalized networks. Such an approach also encompasses the solution to weighted integer foal programming as well as lexicographic integer goal programming problems. In ongoing research, the resulting hybrid algorithms have indicated superior performance, for a number of problems, over that obtained by more conventional approaches. A particularly attractive feature of the methodology is its relative simplicity and robustness. 相似文献
2.
Mason Gene Bailey Billy E. Gillett 《The Journal of the Operational Research Society》1980,31(3):257-262
An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.The approach consists primarily of solving the most relaxed problem (θ = 1) using cutting planes and then contracting the region of feasible integer solutions in such a manner that the current optimal integer solution is eliminated.The algorithm was applied to 1800 integer linear programming problems with reasonable success. Integer programming problems which have proved to be unsolvable using cutting planes have been solved by expanding the region of feasible integer solutions (θ = 1) and then contracting to the original region. 相似文献
3.
In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical ε-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical ε-constraint method on the bi-objective integer programming problem for the sake of completeness and comment on its efficiency. Then present our method on tri-objective integer programming problem and then extend it to the general MOIP problem with k objectives. A numerical example considering tri-objective assignment problem is also provided. 相似文献
4.
In this paper we consider nonlinear integer optimization problems. Nonlinear integer programming has mainly been studied for special classes, such as convex and concave objective functions and polyhedral constraints. In this paper we follow an other approach which is not based on convexity or concavity. Studying geometric properties of the level sets and the feasible region, we identify cases in which an integer minimizer of a nonlinear program can be found by rounding (up or down) the coordinates of a solution to its continuous relaxation. We call this property rounding property. If it is satisfied, it enables us (for fixed dimension) to solve an integer programming problem in the same time complexity as its continuous relaxation. We also investigate the strong rounding property which allows rounding a solution to the continuous relaxation to the next integer solution and in turn yields that the integer version can be solved in the same time complexity as its continuous relaxation for arbitrary dimensions. 相似文献
5.
pth Power Lagrangian Method for Integer Programming 总被引:1,自引:0,他引:1
When does there exist an optimal generating Lagrangian multiplier vector (that generates an optimal solution of an integer programming problem in a Lagrangian relaxation formulation), and in cases of nonexistence, can we produce the existence in some other equivalent representation space? Under what conditions does there exist an optimal primal-dual pair in integer programming? This paper considers both questions. A theoretical characterization of the perturbation function in integer programming yields a new insight on the existence of an optimal generating Lagrangian multiplier vector, the existence of an optimal primal-dual pair, and the duality gap. The proposed pth power Lagrangian method convexifies the perturbation function and guarantees the existence of an optimal generating Lagrangian multiplier vector. A condition for the existence of an optimal primal-dual pair is given for the Lagrangian relaxation method to be successful in identifying an optimal solution of the primal problem via the maximization of the Lagrangian dual. The existence of an optimal primal-dual pair is assured for cases with a single Lagrangian constraint, while adopting the pth power Lagrangian method. This paper then shows that an integer programming problem with multiple constraints can be always converted into an equivalent form with a single surrogate constraint. Therefore, success of a dual search is guaranteed for a general class of finite integer programming problems with a prominent feature of a one-dimensional dual search. 相似文献
6.
《European Journal of Operational Research》2001,128(2):447-458
In this paper we present an efficient approach for solving single allocation p-hub problems with two or three hubs. Two different variants of the problem are considered: the uncapacitated single allocation p-hub median problem and the p-hub allocation problem. We solve these problems using new mixed integer linear programming formulations that require fewer variables than those formerly used in the literature. The problems that we solve here are the largest single allocation problems ever solved. The numerical results presented here will demonstrate the superior performance of our mixed integer linear programs over traditional approaches for large problems. Finally we present the first mixed integer linear program for solving single allocation hub location problems that requires only O(n2) variables and O(n2) constraints that is valid for any number of hubs. 相似文献
7.
R. R. Meyer 《Mathematical Programming》1974,7(1):223-235
The purpose of this paper is to present sufficient conditions for the existence of optimal solutions to integer and mixed-integer programming problems in the absence of upper bounds on the integer variables. It is shown that (in addition to feasibility and boundedness of the objective function) (1) in the pure integer case a sufficient condition is that all of the constraints (other than non-negativity and integrality of the variables) beequalities, and (2) that in the mixed-integer caserationality of the constraint coefficients is sufficient. Some computational implications of these results are also given. 相似文献
8.
Pablo E. Coll 《Discrete Applied Mathematics》2006,154(5):770-801
We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented. 相似文献
9.
With emphasis on the simple plant location problem, (SPLP), we consider an important family of discrete, deterministic, single-criterion, NP-hard, and widely applicable optimization problems. The introductory discussion on problem formulation aspects is followed by the establishment of relationships between SPLP and set packing, set covering and set partitioning problems which all are among those structures in integer programming having the most wide-spread applications. An extensive discourse on solution properties and computational techniques, spanning from early heuristics to the presumably most novel exact methods is then provided. Other subjects of concern include a subfamily of SPLP's solvable in polynomial time, analyses of approximate algorithms, transformability of p-CENTER and p-MEDIAN to SPLP, and structural properties of the SPLP polytope. Along the way we attempt to synthesize these findings and relate them to other areas of integer programming. 相似文献
10.
《European Journal of Operational Research》2002,140(2):291-321
We define a class of monotone integer programs with constraints that involve up to three variables each. A generic constraint in such integer program is of the form ax−by⩽z+c, where a and b are nonnegative and the variable z appears only in that constraint. We devise an algorithm solving such problems in time polynomial in the length of the input and the range of variables U. The solution is obtained from a minimum cut on a graph with O(nU) nodes and O(mU) arcs where n is the number of variables of the types x and y and m is the number of constraints. Our algorithm is also valid for nonlinear objective functions.Nonmonotone integer programs are optimization problems with constraints of the type ax+by⩽z+c without restriction on the signs of a and b. Such problems are in general NP-hard. We devise here an algorithm, relying on a transformation to the monotone case, that delivers half integral superoptimal solutions in polynomial time. Such solutions provide bounds on the optimum value that can only be superior to bounds provided by linear programming relaxation. When the half integral solution can be rounded to an integer feasible solution, this is a 2-approximate solution. In that the technique is a unified 2-approximation technique for a large class of problems. The results apply also for general integer programming problems with worse approximation factors that depend on a quantifier measuring how far the problem is from the class of problems we describe.The algorithm described here has a wide array of problem applications. An additional important consequence of our results is that nonmonotone problems in the framework are MAX SNP-hard and at least as hard to approximate as vertex cover.Problems that are amenable to the analysis provided here are easily recognized. The analysis itself is entirely technical and involves manipulating the constraints and transforming them to a totally unimodular system while losing no more than a factor of 2 in the integrality. 相似文献
11.
凹整数规划的分枝定界解法 总被引:3,自引:0,他引:3
凹整数规划是一类重要的非线性整数规划问题,也是在经济和管理中有着广泛应用的最优化问题.本文主要研究用分枝定界方法求解凹整数规划问题,这一方法的基本思想是对目标函数进行线性下逼近,然后用乘子搜索法求解连续松弛问题.数值结果表明,用这种分枝定界方法求解凹整数规划是有效的. 相似文献
12.
Bala Krishnamoorthy 《Operations Research Letters》2017,45(1):77-83
In the context of branch-and-bound (B&B) for integer programming (IP) problems, a direction along which the polyhedron of the IP has minimum width is termed a thin direction. We demonstrate that a thin direction need not always be a good direction to branch on for solving the problem efficiently. Further, the integer width, which is the number of B&B nodes created when branching on the direction, may also not be an accurate indicator of good branching directions. 相似文献
13.
A portfolio problem with integer variables can facilitate the use of complex models, including models containing discrete asset values, transaction costs, and logical constraints. This study proposes a distributed algorithm for solving a portfolio program to obtain a global optimum. For a portfolio problem with n integer variables, the objective function first is converted into an ellipse function containing n separated quadratic terms. Next, the problem is decomposed into m equal-size separable programming problems solvable by a distributed computation system composed of m personal computers linked via the Internet. The numerical examples illustrate that the proposed method can obtain the global optimum effectively for large scale portfolio problems involving integral variables. 相似文献
14.
Andrzej Ruszczyński 《Mathematical Programming》2002,93(2):195-215
We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions.
They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties
of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities
for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are
used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with
a numerical example.
Received: October 8, 2000 / Accepted: August 13, 2002 Published online: September 27, 2002
Key words. stochastic programming – integer programming – valid inequalities 相似文献
15.
Dorit S. Hochbaum 《Operations Research Letters》2004,32(1):49-58
Linear programming problems with up to two nonzeroes per column in the constraint matrix are shown equivalent to generalized network flow problem. The transformation is applied for solving the maximum cut problem, the b-matching problem in strongly polynomial time and for approximation algorithms for certain integer versions of the problem. 相似文献
16.
Computing exact solution to nonlinear integer programming: Convergent Lagrangian and objective level cut method 总被引:3,自引:0,他引:3
In this paper, we propose a convergent Lagrangian and objective level cut method for computing exact solution to two classes
of nonlinear integer programming problems: separable nonlinear integer programming and polynomial zero-one programming. The
method exposes an optimal solution to the convex hull of a revised perturbation function by successively reshaping or re-confining
the perturbation function. The objective level cut is used to eliminate the duality gap and thus to guarantee the convergence
of the Lagrangian method on a revised domain. Computational results are reported for a variety of nonlinear integer programming
problems and demonstrate that the proposed method is promising in solving medium-size nonlinear integer programming problems. 相似文献
17.
In this paper we develop an algorithm to optimise a nonlinear utility function of multiple objectives over the integer efficient set. Our approach is based on identifying and updating bounds on the individual objectives as well as the optimal utility value. This is done using already known solutions, linear programming relaxations, utility function inversion, and integer programming. We develop a general optimisation algorithm for use with k objectives, and we illustrate our approach using a tri-objective integer programming problem. 相似文献
18.
19.
We present a Lagrangean decomposition to study integer nonlinear programming problems. Solving the dual Lagrangean relaxation we have to obtain at each iteration the solution of a nonlinear programming with continuous variables and an integer linear programming. Decreasing iteratively the primal—dual gap we propose two algorithms to treat the integer nonlinear programming.This work was partially supported by CNPq and FINEP. 相似文献
20.
The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems. 相似文献