Page 1 Next

Displaying 1 – 20 of 42

Showing per page

A fast Lagrangian heuristic for large-scale capacitated lot-size problems with restricted cost structures

Kjetil K. Haugen, Guillaume Lanquepin-Chesnais, Asmund Olstad (2012)


In this paper, we demonstrate the computational consequences of making a simple assumption on production cost structures in capacitated lot-size problems. Our results indicate that our cost assumption of increased productivity over time has dramatic effects on the problem sizes which are solvable. Our experiments indicate that problems with more than 1000 products in more than 1000 time periods may be solved within reasonable time. The Lagrangian decomposition algorithm we use does of course not...

A Mixed Integer Quadratic Programming Model for the Low Autocorrelation Binary Sequence Problem

Kratica, Jozef (2012)

Serdica Journal of Computing

In this paper the low autocorrelation binary sequence problem (LABSP) is modeled as a mixed integer quadratic programming (MIQP) problem and proof of the model’s validity is given. Since the MIQP model is semidefinite, general optimization solvers can be used, and converge in a finite number of iterations. The experimental results show that IQP solvers, based on this MIQP formulation, are capable of optimally solving general/skew-symmetric LABSP instances of up to 30/51 elements in a moderate time....

A note on resolving the inconsistency of one-sided max-plus linear equations

Pingke Li (2019)


When a system of one-sided max-plus linear equations is inconsistent, its right-hand side vector may be slightly modified to reach a consistent one. It is handled in this note by minimizing the sum of absolute deviations in the right-hand side vector. It turns out that this problem may be reformulated as a mixed integer linear programming problem. Although solving such a problem requires much computational effort, it may propose a solution that just modifies few elements of the right-hand side vector,...

An ex-post bound on the greedy heuristic for the uncapacitated facility location problem

Jean-Michel Thizy (2006)

RAIRO - Operations Research

A bound for the greedy heuristic applied to the K-facility location problem can be calculated, using values gathered during the calculation of the heuristic. The bound strengthens a well-known bound for the heuristic. Computational experiments show that this bound can be beneficial when the number of facilities is small or close to the total number of potential sites. In addition, it is consistent with previous results about the influence of the data characteristics upon the optimal value.

Asignación de recursos Max-Min: propiedades y algoritmos.

Amparo Mármol Conde, Blas Pelegrín Pelegrín (1991)

Trabajos de Investigación Operativa

Este trabajo trata el problema de asignación de recursos cuando el objetivo es maximizar la mínima recompensa y las funciones recompensa son continuas y estrictamente crecientes. Se estudian diferentes propiedades que conducen a algoritmos que permiten de forma eficiente la resolución de gran variedad de problemas de esta naturaleza, tanto con variables continuas como discretas.

Automatic error localisation for categorical, continuous and integer data.

Ton de Waal (2005)


Data collected by statistical offices generally contain errors, which have to be corrected before reliable data can be published. This correction process is referred to as statistical data editing. At statistical offices, certain rules, so-called edits, are often used during the editing process to determine whether a record is consistent or not. Inconsistent records are considered to contain errors, while consistent records are considered error-free. In this article we focus on automatic error localisation...

Construction of a Φ-function for two convex polytopes

Y. Stoyan, J. Terno, M. Gil, T. Romanova, G. Scheithauer (2002)

Applicationes Mathematicae

The analytical description of Φ-functions for two convex polytopes is investigated. These Φ-functions can be used for mathematical modelling of packing problems in the three-dimensional space. Only translations of the polytopes are considered. The approach consists of two stages. First the 0-level surface of a Φ-function is constructed, and secondly, the surface is extended to get the Φ-function. The method for constructing the 0-level surface is described in detail.

Enumerating the Set of Non-dominated Vectors in Multiple Objective Integer Linear Programming

John Sylva, Alejandro Crema (2008)

RAIRO - Operations Research

An algorithm for enumerating all nondominated vectors of multiple objective integer linear programs is presented. The method tests different regions where candidates can be found using an auxiliary binary problem for tracking the regions already explored. An experimental comparision with our previous efforts shows the method has relatively good time performance.

Fast computation of the leastcore and prenucleolus of cooperative games

Joseph Frédéric Bonnans, Matthieu André (2008)

RAIRO - Operations Research

The computation of leastcore and prenucleolus is an efficient way of allocating a common resource among n players. It has, however, the drawback being a linear programming problem with 2n - 2 constraints. In this paper we show how, in the case of convex production games, generate constraints by solving small size linear programming problems, with both continuous and integer variables. The approach is extended to games with symmetries (identical players), and to games with partially continuous...

Incorporating the strength of MIP modeling in schedule construction

Cor A.J. Hurkens (2009)

RAIRO - Operations Research

Linear programming techniques can be used in constructing schedules but their application is not trivial. This in particular holds true if a trade-off has to be made between computation time and solution quality. However, it turns out that – when handled with care – mixed integer linear programs may provide effective tools. This is demonstrated in the successful approach to the benchmark constructed for the 2007 ROADEF computation challenge on scheduling problems furnished by France Telecom.

Interval valued bimatrix games

Milan Hladík (2010)


Payoffs in (bimatrix) games are usually not known precisely, but it is often possible to determine lower and upper bounds on payoffs. Such interval valued bimatrix games are considered in this paper. There are many questions arising in this context. First, we discuss the problem of existence of an equilibrium being common for all instances of interval values. We show that this property is equivalent to solvability of a certain linear mixed integer system of equations and inequalities. Second, we...

Local stability and differentiability of the Mean–Conditional Value at Risk model defined on the mixed–integer loss functions

Martin Branda (2010)


In this paper, we study local stability of the mean-risk model with Conditional Value at Risk measure where the mixed-integer value function appears as a loss variable. This model has been recently introduced and studied in~Schulz and Tiedemann [16]. First, we generalize the qualitative results for the case with random technology matrix. We employ the contamination techniques to quantify a possible effect of changes in the underlying probability distribution on the optimal value. We use the generalized...

Currently displaying 1 – 20 of 42

Page 1 Next