共查询到20条相似文献,搜索用时 31 毫秒
1.
We introduce a new Integer Linear Programming (ILP) approach for solving Integer Programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear IP. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems. 相似文献
2.
《Operations Research Letters》2014,42(3):226-230
We propose an Integer Linear Programming (ILP) approach for solving integer programs with bilinear objectives and linear constraints. Our approach is based on finding upper and lower bounds for the integer ensembles in the bilinear objective function, and using the bounds to obtain a tight ILP reformulation of the original problem, which can then be solved efficiently. Numerical experiments suggest that the proposed approach outperforms a latest iterative ILP approach, with notable reductions in the average solution time. 相似文献
3.
A method is proposed to estimate confidence intervals for the solution of integer linear programming (ILP) problems where the technological coefficients matrix and the resource vector are made up of random variables whose distribution laws are unknown and only a sample of their values is available. This method, based on the theory of order statistics, only requires knowledge of the solution of the relaxed integer linear programming (RILP) problems which correspond to the sampled random parameters. The confidence intervals obtained in this way have proved to be more accurate than those estimated by the current methods which use the integer solutions of the sampled ILP problems.This research was partially supported by the Italian National Research Council contract no. 82.001 14.93 (P.F. Trasporti). 相似文献
4.
Aleksandar Savić Jozef Kratica Marija Milanović Djordje Dugošija 《European Journal of Operational Research》2010
This paper considers the maximum betweenness problem. A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on randomly generated instances from the literature. The results of CPLEX solver, based on the proposed MILP formulation, are compared with results obtained by total enumeration technique. The results show that CPLEX optimally solves instances of up to 30 elements and 60 triples in a short period of time. 相似文献
5.
We consider the generalized version of the classical Minimum Spanning Tree problem where the nodes of a graph are partitioned
into clusters and exactly one node from each cluster must be connected. We present a Variable Neighborhood Search (VNS) approach
which uses three different neighborhood types. Two of them work in complementary ways in order to maximize search effectivity.
Both are large in the sense that they contain exponentially many candidate solutions, but efficient polynomial-time algorithms
are used to identify best neighbors. For the third neighborhood type we apply Mixed Integer Programming to optimize local
parts within candidate solution trees. Tests on Euclidean and random instances with up to 1280 nodes indicate especially on
instances with many nodes per cluster significant advantages over previously published metaheuristic approaches.
This work is supported by the RTN ADONET under grant 504438. 相似文献
6.
《Applied Mathematical Modelling》2014,38(7-8):2118-2129
This paper considers the multi level uncapacitated facility location problem (MLUFLP). A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on instances known from literature. The results achieved by CPLEX and Gurobi solvers, based on the proposed MILP formulation, are compared to the results obtained by the same solvers on the already known formulations. The results show that CPLEX and Gurobi can optimally solve all small and medium sized instances and even some large-scale instances using the new formulation. 相似文献
7.
In this paper we present two major approaches to solve the car sequencing problem, in which the goal is to find an optimal arrangement of commissioned vehicles along a production line with respect to constraints of the form “no more than lccars are allowed to require a component c in any subsequence of mcconsecutive cars”. The first method is an exact one based on integer linear programming (ILP). The second approach is hybrid: it uses ILP techniques within a general variable neighborhood search (VNS) framework for examining large neighborhoods. We tested the two methods on benchmark instances provided by CSPLIB and the automobile manufacturer RENAULT for the ROADEF Challenge 2005. These tests reveal that our approaches are competitive to previous reported algorithms. For the CSPLIB instances we were able to shorten the required computation time for reaching and proving optimality. Furthermore, we were able to obtain tight bounds on some of the ROADEF instances. For two of these instances the proposed ILP-method could provide new optimality proofs for already known solutions. For the VNS, the individual contributions of the used neighborhoods are also experimentally analyzed. Results highlight the significant impact of each structure. In particular the large ones examined using ILP techniques enhance the overall performance significantly, so that the hybrid approach clearly outperforms variants including only commonly defined neighborhoods. 相似文献
8.
The strategy of subdividing optimization problems into layers by splitting variables into multiple copies has proved useful as a method for inducing exploitable structure in a variety of applications, particularly those involving embedded pure and generalized networks. A framework is proposed in this paper which leads to new relaxation and restriction methods for linear and integer programming based on our extension of this strategy. This framework underscores the use of constructions that lead to stronger relaxations and more flexible strategies than previous applications. Our results establish the equivalence of all layered Lagrangeans formed by parameterizing the equal value requirement of copied variables for different choices of the principal layers. It is further shown that these Lagrangeans dominate traditional Lagrangeans based on incorporating non-principal layers into the objective function. In addition a means for exploiting the layered Lagrangeans is provided by generating subgradients based on a simple averaging calculation. Finally, we show how this new layering strategy can be augmented by an integrated relaxation/restriction procedure, and indicate variations that can be employed to particular advantage in a parallel processing environment. Preliminary computational results on fifteen real world zero-one personnel assignment problems, comparing two layering approaches with five procedures previously found best for those problems, are encouraging. One of the layering strategies tested dominated all non-layering procedures in terms of both quality and solution time.This research was supported in part by the Office of Naval Research Contract N00014-78-C-0222 with the Center for Business Decision Analysis and by the US Department of Agriculture Contract 51-3142-4020 with Management Science Software Systems. 相似文献
9.
Lizhi Wang 《Operations Research Letters》2009,37(2):114-116
We present cutting plane algorithms for the inverse mixed integer linear programming problem (InvMILP), which is to minimally perturb the objective function of a mixed integer linear program in order to make a given feasible solution optimal. 相似文献
10.
11.
It is not a difficult task to find a weak Pareto or Pareto solution in a multiobjective linear programming (MOLP) problem. The difficulty lies in finding all these solutions and representing their structure. This paper develops an algorithm for solving this problem. We investigate the solutions and their relationships in the objective space. The algorithm determines finite number of weights, each of which corresponds to a weighted sum problems. By solving these problems, we further obtain all weak Pareto and Pareto solutions of the MOLP and their structure in the constraint space. The algorithm avoids the degeneration problem, which is a major hurdle of previous works, and presents an easy and clear solution structure. 相似文献
12.
Denis Cornaz 《Mathematical Programming》2006,105(2-3):329-344
Let G be a simple undirected graph with node set V(G) and edge set E(G). We call a subset independent if F is contained in the edge set of a complete multipartite (not necessarily induced) subgraph of G, F is dependent otherwise. In this paper we characterize the independents and the minimal dependents of G. We note that every minimal dependent of G has size two if and only if G is fan and prism-free. We give a 0-1 linear programming formulation of the following problem: find the maximum weight of
a complete multipartite subgraph of G, where G has nonnegative edge weights. This formulation may have an exponential number of constraints with respect to |V(G)| but we show that the continuous relaxation of this 0-1 program can be solved in polynomial time. 相似文献
13.
André R. S. Amaral 《Optimization Letters》2009,3(4):513-520
We are concerned with the exact solution of a graph optimization problem known as minimum linear arrangement (MinLA). Define the length of each edge of a graph with respect to a linear ordering of the graph vertices. Then, the MinLA problem asks for a vertex
ordering that minimizes the sum of edge lengths. MinLA has several practical applications and is NP-Hard. We present a mixed
0-1 linear programming formulation of the problem, which led to fast optimal solutions for dense graphs of sizes up to n = 23. 相似文献
14.
This paper investigates the simple uncapacitated plant location problem on a line. We show that under general conditions the
special structure of the problem allows the optimal solution to be obtained directly from a linear programming relaxation.
This result may be extended to the related p-median problem on a line. Thus, the practitioner is now able to use readily available
LP codes in place of specialized algorithms to solve these one-dimensional models. The findings also shed some light on the
“integer friendliness” of the general problem. 相似文献
15.
A succinct integer linear programming model for the Steiner problem in networks is presented. 相似文献
16.
H. P. Benson 《Journal of Optimization Theory and Applications》1989,60(3):353-373
Many decision-making situations involve multiple planners with different, and sometimes conflicting, objective functions. One type of model that has been suggested to represent such situations is the linear multilevel programming problem. However, it appears that theoretical and algorithmic results for linear multilevel programming have been limited, to date, to the bounded case or the case of when only two levels exist. In this paper, we investigate the structure and properties of a linear multilevel programming problem that may be unbounded. We study the geometry of the problem and its feasible region. We also give necessary and sufficient conditions for the problem to be unbounded, and we show how the problem is related to a certain parametric concave minimization problem. The algorithmic implications of the results are also discussed.This research was supported by National Science Foundation Grant No. ECS-85-15231. 相似文献
17.
Credal nets are probabilistic graphical models which extend Bayesian nets to cope with sets of distributions. An algorithm for approximate credal network updating is presented. The problem in its general formulation is a multilinear optimization task, which can be linearized by an appropriate rule for fixing all the local models apart from those of a single variable. This simple idea can be iterated and quickly leads to accurate inferences. A transformation is also derived to reduce decision making in credal networks based on the maximality criterion to updating. The decision task is proved to have the same complexity of standard inference, being NPPP-complete for general credal nets and NP-complete for polytrees. Similar results are derived for the E-admissibility criterion. Numerical experiments confirm a good performance of the method. 相似文献
18.
This study investigates scheduling problems that occur when the weighted number of late jobs that are subject to deterministic machine availability constraints have to be minimized. These problems can be modeled as a more general job selection problem. Cases with resumable, non-resumable, and semi-resumable jobs as well as cases without availability constraints are investigated. The proposed efficient mixed integer linear programming approach includes possible improvements to the model, notably specialized lifted knapsack cover cuts. The method proves to be competitive compared with existing dedicated methods: numerical experiments on randomly generated instances show that all 350-job instances of the test bed are closed for the well-known problem 1|ri|∑wiUi. For all investigated problem types, 98.4% of 500-job instances can be solved to optimality within 1 hour. 相似文献
19.
Marvin D Troutt 《Operations Research Letters》1985,4(4):181-184
A linear programming model is constructed which enables a firm to estimate its competitor's cost structure when the competitor adheres to a non-randomized strategy. The existence of the model makes randomized bidding prudent apart from game theory considerations. The need for increased curriculum attention to optimal bidding is highlighted. 相似文献
20.
This paper presents a new algorithm for identifying all supported non-dominated vectors (or outcomes) in the objective space, as well as the corresponding efficient solutions in the decision space, for multi-objective integer network flow problems. Identifying the set of supported non-dominated vectors is of the utmost importance for obtaining a first approximation of the whole set of non-dominated vectors. This approximation is crucial, for example, in two-phase methods that first compute the supported non-dominated vectors and then the unsupported non-dominated ones. Our approach is based on a negative-cycle algorithm used in single objective minimum cost flow problems, applied to a sequence of parametric problems. The proposed approach uses the connectedness property of the set of supported non-dominated vectors/efficient solutions to find all integer solutions in maximal non-dominated/efficient facets. 相似文献