All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 61

Showing per page

Inductive computations on graphs defined by clique-width expressions

Frédérique Carrère (2009)

RAIRO - Theoretical Informatics and Applications

Labelling problems for graphs consist in building distributed data structures, making it possible to check a given graph property or to compute a given function, the arguments of which are vertices. For an inductively computable function D, if G is a graph with n vertices and of clique-width at most k, where k is fixed, we can associate with each vertex x of G a piece of information (bit sequence) lab(x) of length O(log2(n)) such that we can compute D in constant time, using only the labels...

Inequality-sum : a global constraint capturing the objective function

Jean-Charles Régin, Michel Rueher (2005)

RAIRO - Operations Research - Recherche Opérationnelle

This paper introduces a new method to prune the domains of the variables in constrained optimization problems where the objective function is defined by a sum y = Σ x i , and where the integer variables x i are subject to difference constraints of the form x j - x i ≤ c . An important application area where such problems occur is deterministic scheduling with the mean flow time as optimality criteria. This new constraint is also more general than a sum constraint defined on a set of ordered variables. Classical approaches...

Inequality-sum: a global constraint capturing the objective function

Jean-Charles Régin, Michel Rueher (2010)

RAIRO - Operations Research

This paper introduces a new method to prune the domains of the variables in constrained optimization problems where the objective function is defined by a sum y = ∑xi, and where the integer variables xi are subject to difference constraints of the form xj - xi ≤ c. An important application area where such problems occur is deterministic scheduling with the mean flow time as optimality criteria. This new constraint is also more general than a sum constraint defined on a set of ordered variables....

Inexact Newton-type method for solving large-scale absolute value equation A x - | x | = b

Jingyong Tang (2024)

Applications of Mathematics

Newton-type methods have been successfully applied to solve the absolute value equation A x - | x | = b (denoted by AVE). This class of methods usually solves a system of linear equations exactly in each iteration. However, for large-scale AVEs, solving the corresponding system exactly may be expensive. In this paper, we propose an inexact Newton-type method for solving the AVE. In each iteration, the proposed method solves the corresponding system only approximately. Moreover, it adopts a new line search technique,...

Influence of modeling structure in probabilistic sequential decision problems

Florent Teichteil-Königsbuch, Patrick Fabiani (2006)

RAIRO - Operations Research

Markov Decision Processes (MDPs) are a classical framework for stochastic sequential decision problems, based on an enumerated state space representation. More compact and structured representations have been proposed: factorization techniques use state variables representations, while decomposition techniques are based on a partition of the state space into sub-regions and take advantage of the resulting structure of the state transition graph. We use a family of probabilistic exploration-like...

Integer Linear Programming applied to determining monic hyperbolic irreducible polynomials with integer coefficients and span less than 4

Souad El Otmani, Armand Maul, Georges Rhin, Jean-Marc Sac-Épée (2013)

Journal de Théorie des Nombres de Bordeaux

In this work, we propose a new method to find monic irreducible polynomials with integer coefficients, only real roots, and span less than 4. The main idea is to reduce the search of such polynomials to the solution of Integer Linear Programming problems. In this frame, the coefficients of the polynomials we are looking for are the integer unknowns. We give inequality constraints specified by the properties that the polynomials should have, such as the typical distribution of their roots. These...

Integer programming approaches for minimum stabbing problems

Breno Piva, Cid C. de Souza, Yuri Frota, Luidi Simonetti (2014)

RAIRO - Operations Research - Recherche Opérationnelle

The problem of finding structures with minimum stabbing number has received considerable attention from researchers. Particularly, [10] study the minimum stabbing number of perfect matchings (mspm), spanning trees (msst) and triangulations (mstr) associated to set of points in the plane. The complexity of the mstr remains open whilst the other two are known to be 𝓝𝓟-hard. This paper presents integer programming (ip) formulations for these three problems, that allowed us to...

Integer Programming Formulation of the Bilevel Knapsack Problem

R. Mansi, S. Hanafi, L. Brotcorne (2010)

Mathematical Modelling of Natural Phenomena

The Bilevel Knapsack Problem (BKP) is a hierarchical optimization problem in which the feasible set is determined by the set of optimal solutions of parametric Knapsack Problem. In this paper, we propose two stages exact method for solving the BKP. In the first stage, a dynamic programming algorithm is used to compute the set of reactions of the follower. The second stage consists in solving an integer program reformulation of BKP. We show that the...

Interactive compromise hypersphere method and its applications

Sebastian Sitarz (2012)

RAIRO - Operations Research - Recherche Opérationnelle

The paper focuses on multi-criteria problems. It presents the interactive compromise hypersphere method with sensitivity analysis as a decision tool in multi-objective programming problems. The method is based on finding a hypersphere (in the criteria space) which is closest to the set of chosen nondominated solutions. The proposed modifications of the compromise hypersphere method are based on using various metrics and analyzing their influence on the original method. Applications of the proposed...

Interactive compromise hypersphere method and its applications

Sebastian Sitarz (2012)

RAIRO - Operations Research

The paper focuses on multi-criteria problems. It presents the interactive compromise hypersphere method with sensitivity analysis as a decision tool in multi-objective programming problems. The method is based on finding a hypersphere (in the criteria space) which is closest to the set of chosen nondominated solutions. The proposed modifications of the compromise hypersphere method are based on using various metrics and analyzing their influence on the original method. Applications of the proposed...

Currently displaying 21 – 40 of 61