Search results for "Mathematical optimization"
showing 10 items of 1300 documents
Fast and Accurate Bounds on Linear Programs
2009
We present an algorithm that certifies the feasibility of a linear program while using rational arithmetic as little as possible. Our approach relies on computing a feasible solution of the linear program that is as far as possible from satisfying an inequality at equality. To realize such an approach, we have to detect the set of inequalities that can only be satisfied at equality. Compared to previous approaches for this problem our algorithm has a much higher rate of success.
Certifying feasibility and objective value of linear programs
2012
Abstract We present an algorithm that certifies the feasibility of a linear program and computes a safe bound on its objective value while using rational arithmetic as little as possible. Our approach relies on computing a feasible solution that is as far as possible from satisfying an inequality at equality. To this end, we have to detect the set of inequalities that can only be satisfied at equality. Compared to previous approaches, our algorithm has a much higher success rate.
Black-Box Solvers
2017
Linear programming is perhaps the best-known tool for optimization. Linear programming is a general-purpose framework that allows a real system to be abstracted as a model with a linear objective function subject to a set of linear constraints.
Approximate solutions for two-level optimization problems
1988
This paper is devoted to general results for approximating two-level optimization problems in which the set of solutions to the lower level problem is not a singleton.
On the design of the optimal covering of an obstacle
2006
We consider the problem of controlling the shape of the coincidence set in an obstacle problem. This so called packaging problem was introduced in
A Scatter Search Algorithm for the Split Delivery Vehicle Routing Problem
2008
In this chapter we present a metaheuristic procedure constructed for the special case of the Vehicle Routing Problem in which the demands of clients can be split, i.e., any client can be serviced by more than one vehicle. The proposed algorithm, based on the scatter search methodology, produces a feasible solution using the minimum number of vehicles. The quality of the obtained results is comparable to the best results known up to date on a set of instances previously published in the literature.
A New Metaheuristic for the Vehicle Routing Problem with Split Demands
2007
In this paper we present a metaheuristic procedure constructed for the special case of the Vehicle Routing Problem in which the demands of the clients can be split, i.e., any client can be serviced by more than one vehicle. The proposed algorithm, based on the scatter search methodology, produces a feasible solution using the minimum number of vehicles. The results obtained compare with the best results known up to date on a set of instances previously published in the literature.
Efficient Local Search Limitation Strategies for Vehicle Routing Problems
2008
In this paper we examine five different strategies for limiting the local search neighborhoods in the context of vehicle routing problems. The vehicle routing problem deals with the assignment of a set of transportation orders to a fleet of vehicles, and the sequencing of stops for each vehicle to minimize transportation costs. The examined strategies are applied to three standard neighborhoods and implemented in a recently suggested powerful memetic algorithm. Experimental results on 26 well-known benchmark problems indicate significant speedups of almost 80% without worsening the solution quality. On the contrary, in 12 cases new best solutions were obtained.
The simulation and analysis of the revenue critierion based adaptive WFQ
2003
This paper presents the simulation and analysis of the adaptive resource allocation model, which was proposed and theoretically considered in our previous works. It relies upon the Weighted Fair Queueing (WFQ) service policy and uses the revenue criterion to adjust weights. The purpose of the proposed model is to maximize a provider's revenue and, at the same time, ensure the required Quality-of-Service (QoS) for end-users. Our previous works provided the theoretical evaluation of the proposed model and considered the single-node case only. This paper presents more realistic network scenario, which includes a set of clients and several intermediate switching nodes with the proposed model. T…
About Combining Metric Learning and Prototype Generation
2014
Distance metric learning has been a major research topic in recent times. Usually, the problem is formulated as finding a Mahalanobis-like metric matrix that satisfies a set of constraints as much as possible. Different ways to introduce these constraints and to effectively formulate and solve the optimization problem have been proposed. In this work, we start with one of these formulations that leads to a convex optimization problem and generalize it in order to increase the efficiency by appropriately selecting the set of constraints. Moreover, the original criterion is expressed in terms of a reduced set of representatives that is learnt together with the metric. This leads to further im…