Maximal flow problem in a network with a variable structure
Minimizing the number of tardy jobs for the single machine scheduling problem: MIP-based lower and upper bounds
This paper considers the problem of scheduling n jobs on a single machine. A fixed processing time and an execution interval are associated with each job. Preemption is not allowed. The objective is to find a feasible job sequence that minimizes the number of tardy jobs. On the basis of an original mathematical integer programming formulation, this paper shows how good-quality lower and upper bounds can be computed. Numerical experiments are provided for assessing the proposed approach.
Minmax regret combinatorial optimization problems: an Algorithmic Perspective
Uncertainty in optimization is not a new ingredient. Diverse models considering uncertainty have been developed over the last 40 years. In our paper we essentially discuss a particular uncertainty model associated with combinatorial optimization problems, developed in the 90's and broadly studied in the past years. This approach named minmax regret (in particular our emphasis is on the robust deviation criteria) is different from the classical approach for handling uncertainty, stochastic approach,...
Minmax regret combinatorial optimization problems: an Algorithmic Perspective
Uncertainty in optimization is not a new ingredient. Diverse models considering uncertainty have been developed over the last 40 years. In our paper we essentially discuss a particular uncertainty model associated with combinatorial optimization problems, developed in the 90's and broadly studied in the past years. This approach named minmax regret (in particular our emphasis is on the robust deviation criteria) is different from the classical approach for handling uncertainty, stochastic approach,...
Mixed integer programming, general concept inclusions and fuzzy description logics.
MOPP-I: an optimization package for multipurpose batch operations.
A number of algorithms have been developed -including enumeration of feasible production sequences, alternative task selection and the generation of alternative production lines- to determine the optimal sequence in which products and by-products should be produced and the times at which the various production operations for each product should be carried out to meet a given product demand pattern, taking into account the available equipment, storage costs, stopover penalties and other plant limitations.Product...
Nonlinear mixed zero-one Programming: Practical and Theoretical Aspects
On modelling planning under uncertainty in manufacturing.
We present a modelling framework for two-stage and multi-stage mixed 0-1 problems under uncertainty for strategic Supply Chain Management, tactical production planning and operations assignment and scheduling. A scenario tree based scheme is used to represent the uncertainty. We present the Deterministic Equivalent Model of the stochastic mixed 0-1 programs with complete recourse that we study. The constraints are modelled by compact and splitting variable representations via scenarios.
On sparsity of approximate solutions to max-plus linear systems
When a system of one-sided max-plus linear equations is inconsistent, the approximate solutions within an admissible error bound may be desired instead, particularly with some sparsity property. It is demonstrated in this paper that obtaining the sparsest approximate solution within a given error bound may be transformed in polynomial time into the set covering problem, which is known to be NP-hard. Besides, the problem of obtaining the sparsest approximate solution within a given error bound...
Programmation linéaire mixte : conditions de validité dans les méthodes arborescentes
Programmes mathématiques mixtes. Application au principe du maximum en temps discret dans le cas déterministe et dans le cas stochastique
Properties of solutions of optimization problems for set functions.
Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations
Many combinatorial optimization problems can be formulated as the minimization of a 0–1 quadratic function subject to linear constraints. In this paper, we are interested in the exact solution of this problem through a two-phase general scheme. The first phase consists in reformulating the initial problem either into a compact mixed integer linear program or into a 0–1 quadratic convex program. The second phase simply consists in submitting the reformulated problem to a standard solver. The efficiency...
Reconfigurable Dynamic Cellular Manufacturing System: A New Bi-Objective Mathematical Model
Dynamic Cell Formation Problem (DCFP) seeks to cope with variation in part mix and demands using machine relocation, replication, and removing; whilst from practical point of view it is too hard to move machines between cells or invest on machine replication. To cope with this deficiency, this paper addresses Reconfigurable Dynamic Cell Formation Problem (RDCFP) in which machine modification is conducted instead of their relocation or replication in order to enhance machine capabilities to process...
Reformulations in Mathematical Programming: Definitions and Systematics
A reformulation of a mathematical program is a formulation which shares some properties with, but is in some sense better than, the original program. Reformulations are important with respect to the choice and efficiency of the solution algorithms; furthermore, it is desirable that reformulations can be carried out automatically. Reformulation techniques are widespread in mathematical programming but interestingly they have never been studied under a unified framework. This paper attempts to move...
Résolution de programmes linéaires entiers ou mixtes à l'aide de la forme normale de Hermite
Rounding Strategies for Mixed Integer Programs Arising from Chemical Production Planning
Simultaneous routing and flow rate optimization in energy-aware computer networks
The issue of energy-aware traffic engineering has become prominent in telecommunications industry in the last years. This paper presents a two-criteria network optimization problem, in which routing and bandwidth allocation are determined jointly, so as to minimize the amount of energy consumed by a telecommunication infrastructure and to satisfy given demands represented by a traffic matrix. A scalarization of the criteria is proposed and the choice of model parameters is discussed in detail. The...
Solution approaches to large shift scheduling problems
This paper considers large shift scheduling problems with different shift start times and lengths, fractionable breaks and work stretch duration restrictions. Two solution approaches are proposed to solve the problems over a multiple-day planning horizon. The first approach is based on a local branching strategy and the second one is based on a temporal decomposition of the problem. Local branching is very efficient in finding good feasible solutions when compared to a classical branch-and-bound...
Solution of a fractional combinatorial optimization problem by mixed integer programming
Fractionnal mathematical programs appear in numerous operations research, computer science and economic domains. We consider in this paper the problem of maximizing the sum of 0–1 hyperbolic ratios (SRH). In contrast to the single ratio problem, there has been little work in the literature concerning this problem. We propose two mixed-integer linear programming formulations of SRH and develop two different strategies to solve them. The first one consists in using directly a general-purpose mixed-integer...