共查询到20条相似文献,搜索用时 0 毫秒
1.
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. 相似文献
2.
We study the transit frequency optimization problem, which aims to determine the time interval between subsequent buses for a set of public transportation lines given by their itineraries, i.e., sequences of stops and street sections. The solution should satisfy a given origin–destination demand and a constraint on the available fleet of buses. We propose a new mixed integer linear programming (MILP) formulation for an already existing model, originally formulated as a nonlinear bilevel one. The proposed formulation is able to solve to optimality real small-sized instances of the problem using MILP techniques. For solving larger instances we propose a metaheuristic which accuracy is estimated by comparing against exact results (when possible). Both exact and approximated approaches are tested by using existing cases, including a real one related to a small-city which public transportation system comprises 13 lines. The magnitude of the improvement of that system obtained by applying the proposed methodologies, is comparable with the improvements reported in the literature, related to other real systems. Also, we investigate the applicability of the metaheuristic to a larger-sized real case, comprising more than 130 lines. 相似文献
3.
Discrete optimization in public rail transport 总被引:5,自引:0,他引:5
Many problems arising in traffic planning can be modelled and solved using discrete optimization. We will focus on recent
developments which were applied to large scale real world instances.
Most railroad companies apply a hierarchically structured planning process. Starting with the definition of the underlying
network used for transport one has to decide which infrastructural improvements are necessary. Usually, the rail system is
periodically scheduled. A fundamental base of the schedule are the lines connecting several stations with a fixed frequency.
Possible objectives for the construction of the line plan may be the minimization of the total cost or the maximization of
the passengers’s comfort satisfying certain regulations. After the lines of the system are fixed, the train schedule can be
determined. A criterion for the quality of a schedule is the total transit time of the passengers including the waiting time
which should be minimized satisfying some operational constraints. For each trip of the schedule a train consisting of a locomotive
and some carriages is needed for service. The assignment of rolling stock to schedule trips has to satisfy operational requirements.
A comprehensible objective is to minimize the total cost. After all strategic and tactical planning the schedule has to be
realized. Several external influences, for example delayed trains, force the dispatcher to recompute parts of the schedule
on-line.
A Web page with examples quoted in this survey can be found at http://www.math.tu-bs.de/mo/ismp.html. 相似文献
4.
Géraldine Heilporn Martine Labbé Patrice Marcotte Gilles Savard 《Discrete Optimization》2011,8(3):393-410
Motivated by an application in highway pricing, we consider the problem that consists in setting profit-maximizing tolls on a clique subset of a multicommodity transportation network. We formulate the problem as a linear mixed integer program and propose strong valid inequalities, some of which define facets of the two-commodity polyhedron. The numerical efficiency of these inequalities is assessed by embedding them within a branch-and-cut framework. 相似文献
5.
The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB. 相似文献
6.
P. Hungerländer 《Optimization》2017,66(10):1699-1712
We suggest a new variant of a row layout problem: Find an ordering of n departments with given lengths such that the total weighted sum of their distances to a given checkpoint is minimized. The Checkpoint Ordering Problem (COP) is both of theoretical and practical interest. It has several applications and is conceptually related to some well-studied combinatorial optimization problems, namely the Single-Row Facility Layout Problem, the Linear Ordering Problem and a variant of parallel machine scheduling. In this paper we study the complexity of the (COP) and its special cases. The general version of the (COP) with an arbitrary but fixed number of checkpoints is NP-hard in the weak sense. We propose both a dynamic programming algorithm and an integer linear programming approach for the (COP) . Our computational experiments indicate that the (COP) is hard to solve in practice. While the run time of the dynamic programming algorithm strongly depends on the length of the departments, the integer linear programming approach is able to solve instances with up to 25 departments to optimality. 相似文献
7.
8.
Managing shelf space is critical for retailers to attract customers and optimize profits. This article develops a shelf-space allocation optimization model that explicitly incorporates essential in-store costs and considers space- and cross-elasticities. A piecewise linearization technique is used to approximate the complicated nonlinear space-allocation model. The approximation reformulates the non-convex optimization problem into a linear mixed integer programming (MIP) problem. The MIP solution not only generates near-optimal solutions for large scale optimization problems, but also provides an error bound to evaluate the solution quality. Consequently, the proposed approach can solve single category-shelf space management problems with as many products as are typically encountered in practice and with more complicated cost and profit structures than currently possible by existing methods. Numerical experiments show the competitive accuracy of the proposed method compared with the mixed integer nonlinear programming shelf-space model. Several extensions of the main model are discussed to illustrate the flexibility of the proposed methodology. 相似文献
9.
A non-convex optimization problem involving minimization of the sum of max and min concave functions over a transportation
polytope is studied in this paper. Based upon solving at most (g+1)(< p) cost minimizing transportation problems with m sources and n destinations, a polynomial time algorithm is proposed which minimizes the concave objective function where, p is the number of pairwise disjoint entries in the m× n time matrix {t
ij
} sorted decreasingly and T
g
is the minimum value of the max concave function. An exact global minimizer is obtained in a finite number of iterations.
A numerical illustration and computational experience on the proposed algorithm is also included.
We are thankful to Prof. S. N. Kabadi, University of New Brunswick-Fredericton, Canada, who initiated us to the type of problem
discussed in this paper. We are also thankful to Mr. Ankit Khandelwal, Ms. Neha Gupta and Ms. Anuradha Beniwal, who greatly
helped us in the implementation of the proposed algorithm. 相似文献
10.
11.
Sana Belmokhtar 《4OR: A Quarterly Journal of Operations Research》2008,6(3):315-318
The paper summarizes the main results of the author’s Ph.D. thesis presented in December 2006 at the école des Mines de Saint
étienne. The work was supervised by Alexandre Dolgui and Xavier Delorme. The thesis is written in French and is available
upon request from the author. Its purpose is to provide decision support in the design and reconfiguration of modular machining
lines with multi-spindle units. This design problem is defined as the selection of spindle units to perform a set of operations
needed to produce the parts and subsequently their assignment to workstations. The corresponding optimization problem is solved
using different models based on integer and constraint programming.
相似文献
12.
Gianfranco Guastaroba Renata Mansini M. Grazia Speranza 《European Journal of Operational Research》2009
In single-period portfolio selection problems the expected value of both the risk measure and the portfolio return have to be estimated. Historical data realizations, used as equally probable scenarios, are frequently used to this aim. Several other parametric and non-parametric methods can be applied. When dealing with scenario generation techniques practitioners are mainly concerned on how reliable and effective such methods are when embedded into portfolio selection models. In this paper we survey different techniques to generate scenarios for the rates of return. We also compare the techniques by providing in-sample and out-of-sample analysis of the portfolios obtained by using these techniques to generate the rates of return. Evidence on the computational burden required by the different techniques is also provided. As reference model we use the Worst Conditional Expectation model with transaction costs. Extensive computational results based on different historical data sets from London Stock Exchange Market (FTSE) are presented and some interesting financial conclusions are drawn. 相似文献
13.
In this paper we study a new variant of the minimum energy broadcast (MEB) problem, namely the probabilistic MEB (PMEB). The objective of the classic MEB problem is to assign transmission powers to the nodes of a wireless network is such a way that the total energy dissipated on the network is minimized, while a connected broadcasting structure is guaranteed by the assigned transmission powers. In the new variant of the problem treated in this paper, node failure is taken into account, aiming at providing solutions with a chosen reliability level for the broadcasting structure. Three mixed integer linear programming formulations for the new problem are presented, together with efficient formulation-dependent methods for their solution. Computational results are proposed and discussed. One method emerges as the most promising one under realistic settings. It is able to handle problems with up to fifty nodes. 相似文献
14.
In this paper, we develop effective methods for solving the power-networking problem encountered by the Tulsa Metro Chamber. The primary objective is the maximization of unique contacts made in meetings with multiple rotations of participants. Mixed-integer and constraint-programming models are developed to optimize small- to medium-scale problems, and a heuristic method is developed for large-scale problems representative of the Chamber’s application. Tight bounds on the dual objective are presented. The constraint-programming model developed as phase one for the heuristic yields many new best-known solutions to the related social-golfer problem. The solutions generated for the power-networking problem enables the Chamber of Commerce to plan meeting assignments much more effectively. 相似文献
15.
Arnaud Malapert Christelle Guéret Louis-Martin Rousseau 《European Journal of Operational Research》2012
This paper presents a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch processing machine can process several jobs simultaneously and the objective is to minimize the maximal lateness. The constraint programming formulation proposed relies on the decomposition of the problem into finding an assignment of the jobs to the batches, and then minimizing the lateness of the batches on a single machine. This formulation is enhanced by a new optimization constraint which is based on a relaxed problem and applies cost-based domain filtering techniques. Experimental results demonstrate the efficiency of cost-based domain filtering techniques. Comparisons to other exact approaches clearly show the benefits of the proposed approach: it can optimally solve problems that are one order of magnitude greater than those solved by a mathematical formulation or by a branch-and-price. 相似文献
16.
Miguel Constantino Xenia Klimentova Ana Viana Abdur Rais 《European Journal of Operational Research》2013
In recent years several countries have set up policies that allow exchange of kidneys between two or more incompatible patient–donor pairs. These policies lead to what is commonly known as kidney exchange programs. 相似文献
17.
This work focuses on an improved exact algorithm for addressing an NP-hard network pricing problem. The method involves an efficient and partial generation of candidate solutions, a recursive scheme for generating improved upper bounds, and a column generation procedure for solving the network-structured subproblems. Its efficiency is assessed against both randomly generated instances involving three distinct topologies as well as instances based on real life situations in telecommunication and freight transportation. 相似文献
18.
Discrete Filled Function Method for Discrete Global Optimization 总被引:6,自引:0,他引:6
A discrete filled function method is developed in this paper to solve discrete global optimization problems over strictly pathwise connected domains. Theoretical properties of the proposed discrete filled function are investigated and a solution algorithm is proposed. Numerical experiments reported in this paper on several test problems with up to 200 variables have demonstrated the applicability and efficiency of the proposed method. 相似文献
19.
A gas network basically consists of a set of compressors and valves that are connected by pipes. The problem of gas network
optimization deals with the question of how to optimize the flow of the gas and to use the compressors cost-efficiently such
that all demands of the gas network are satisfied. This problem leads to a complex mixed integer nonlinear optimization problem.
We describe techniques for a piece-wise linear approximation of the nonlinearities in this model resulting in a large mixed
integer linear program. We study sub-polyhedra linking these piece-wise linear approximations and show that the number of
vertices is computationally tractable yielding exact separation algorithms. Suitable branching strategies complementing the
separation algorithms are also presented. Our computational results demonstrate the success of this approach.
Received: April, 2004 相似文献
20.
Réal A. Carbonneau Gilles CaporossiPierre Hansen 《European Journal of Operational Research》2011,212(1):213-222
Exact global optimization of the clusterwise regression problem is challenging and there are currently no published feasible methods for performing this clustering optimally, even though it has been over thirty years since its original proposal. This work explores global optimization of the clusterwise regression problem using mathematical programming and related issues. A mixed logical-quadratic programming formulation with implication of constraints is presented and contrasted against a quadratic formulation based on the traditional big-M, which cannot guarantee optimality because the regression line coefficients, and thus errors, may be arbitrarily large. Clusterwise regression optimization times and solution optimality for two clusters are empirically tested on twenty real datasets and three series of synthetic datasets ranging from twenty to one hundred observations and from two to ten independent variables. Additionally, a few small real datasets are clustered into three lines. 相似文献