A compromised multi-objective solution using fuzzy mixed integer goal programming for market-based short-term unit commitment problem

When implementing, the solution of single-objective unit commitment models may be dissatisfactory or inapplicable. This might mainly be due to not considering the secondary conflicting objectives from the policy-making in internal/external environment of generation companies in the developed models. To attain a practical compromised multi-objective solution for the short-term unit commitment in the deregulated hybrid markets, a novel fuzzy mixed integer linear goal programme is developed in which several complementary objectives with lower relative importances are also incorporated. Non-linear characteristic curves of the generating units are approximated through the piece-wise linear functions. The fuzzy approach is proposed to handle the imprecise nature of the goals’ target levels and priorities as well as some critical data. The critical aspects of power systems are considered in the model. The efficiency of the proposed approach is demonstrated using the experimental results inspired by a real case. The applicable nice feature of our model is that it can easily and efficiently be matched with a various line of unit commitment problems.     

A real coded genetic algorithm for solving integer and mixed integer optimization problems

In this paper, a real coded genetic algorithm named MI-LXPM is proposed for solving integer and mixed integer constrained optimization problems. The proposed algorithm is a suitably modified and extended version of the real coded genetic algorithm, LXPM, of Deep and Thakur [K. Deep, M. Thakur, A new crossover operator for real coded genetic algorithms, Applied Mathematics and Computation 188 (2007) 895-912; K. Deep, M. Thakur, A new mutation operator for real coded genetic algorithms, Applied Mathematics and Computation 193 (2007) 211-230]. The algorithm incorporates a special truncation procedure to handle integer restrictions on decision variables along with a parameter free penalty approach for handling constraints. Performance of the algorithm is tested on a set of twenty test problems selected from different sources in literature, and compared with the performance of an earlier application of genetic algorithm and also with random search based algorithm, RST2ANU, incorporating annealing concept. The proposed MI-LXPM outperforms both the algorithms in most of the cases which are considered.     

Remarks on the integer Talmud solution for integer bankruptcy problems

In Fragnelli et al. (TOP 22:892–933, 2014; TOP 24:88–130, 2016), we considered a bankruptcy problem with the additional constraint that the estate has to be assigned in integer unities, allowing for non-integer claims; we dealt with the extension to our setting of the constrained equal losses solution and of the constrained equal awards solution. Here, we analyze the possibilities of extending the Talmud solution to the integer situation, starting from the existing approaches for the non-integer case; some of these approaches are compatible with the non-integer claims, but in order to comply with as much as possible of the approaches it is necessary to switch to integer claims.     

A branch and bound algorithm with constraint partitioning for integer goal programming problems

Using constraint partitioning and variable elimination, the authors have recently developed an efficient algorithm for solving linear goal programming problems. However, many goal programs require some or all of the decision variables to be integer valued. This paper shows how the new partitioning algorithm can be extended with a modified branch and bound strategy to solve both pure and mixed type integer goal programming problems. A potential problem in combining the partitioning algorithm and the branch and bound search scheme is presented and resolved.     

An integer goal programming model for hazardous waste treatment and disposal

The improper handling and disposal of hazardous wastes cause threats to human health and the environment. One reason for the improper handling and disposal of these wastes is that not much consideration is usually given to the logistical aspects of hazardous waste systems. In this paper an integer goal programming model is developed that takes into consideration the multiple goals and needs of many groups involved in managing and planning hazardous waste systems. The model can easily be implemented and can be used to address many of the issues related to facility location, recycling, treatment, and disposal of hazardous wastes.     

A review of interactive methods for multiobjective integer and mixed-integer programming

This paper makes a review of interactive methods devoted to multiobjective integer and mixed-integer programming (MOIP/MOMIP) problems. The basic concepts concerning the characterization of the non-dominated solution set are first introduced, followed by a remark about non-interactive methods vs. interactive methods. Then, we focus on interactive MOIP/MOMIP methods, including their characterization according to the type of preference information required from the decision maker, the computing process used to determine non-dominated solutions and the interactive protocol used to communicate with the decision maker. We try to draw out some contrasts and similarities of the different types of methods.     

A decomposition-based solution method for stochastic mixed integer nonlinear programs

This is a summary of the main results presented in the author’s PhD thesis, supervised by D. Conforti and P. Beraldi and defended on March 2005. The thesis, written in English, is available from the author upon request. It describes one of the very few existing implementations of a method for solving stochastic mixed integer nonlinear programming problems based on deterministic global optimization. In order to face the computational challenge involved in the solution of such multi-scenario nonconvex problems, a branch and bound approach is proposed that exploits the peculiar structure of stochastic programming problem.     

Review and comparison of three methods for the solution of the car sequencing problem

The car sequencing problem is the ordering of the production of a list of vehicles which are of the same type, but which may have options or variations that require higher work content and longer operation times for at least one assembly workstation. A feasible production sequence is one that does not schedule vehicles with options in such a way that one or more workstations are overloaded. In variations of the problem, other constraints may apply. We describe and compare three approaches to the modeling and solution of this problem. The first uses integer programming to model and solve the problem. The second approaches the question as a constraint satisfaction problem (CSP). The third method proposes an adaptation of the Ant Colony Optimization for the car sequencing problem. Test-problems are drawn from CSPLib, a publicly available set of problems available through the Internet. We quote results drawn both from our own work and from other research. The literature review is not intended to be exhaustive but we have sought to include representative examples and the more recent work. Our conclusions bear on likely research avenues for the solution of problems of practical size and complexity. A new set of larger benchmark problems was generated and solved. These problems are available to other researchers who may wish to solve them using their own methods.     

A branch and bound method for the solution of multiparametric mixed integer linear programming problems

In this paper, we present a novel algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch and bound strategy that involves the solution of a multiparametric linear programming sub-problem at leaf nodes and appropriate comparison procedures to update the tree. McCormick relaxation procedures are employed to overcome the presence of bilinear terms in the model. The algorithm generates an envelope of parametric profiles, containing the optimal solution of the mp-MILP problem. The parameter space is partitioned into polyhedral convex critical regions. Two examples are presented to illustrate the steps of the proposed algorithm.     

A comparison of two methods for solving 0–1 integer programs using a general purpose simulated annealing algorithm

0–1 problems are often difficult to solve. Although special purpose algorithms (exact as well as heuristic) exist for solving particular problem classes or problem instances, there are few general purpose algorithms for solving practical-sized instances of 0–1 problems. This paper deals with a general purpose heuristic algorithm for 0–1 problems. In this paper, we compare two methods based on simulated annealing for solving general 0–1 integer programming problems. The two methods differe in the scheme used for neighbourhood transitions in the simulated annealing framework. We compare the performance of the two methods on the set partitioning problem.     

Reformulation and solution approach for non-separable integer quadratic programs

We consider quadratic programs with pure general integer variables. The objective function is quadratic and convex and the constraints are linear. An exact solution approach is proposed. It is decomposed into two phases. In the first phase, the initial problem is reformulated into an equivalent problem with a separable objective function. This is done by use of a Gauss decomposition of the Hessian matrix of the initial problem and requires the addition of some continuous variables and constraints. In the second phase, the reformulated problem is linearized by an approximation of each squared term by a set of K linear functions that correspond to the tangents of a hyperbola in K points. We give a proof of the intuitive property that when K is large enough, the optimal value of the obtained linear program is very close to optimal value of the two previous problems, the initial problem and the reformulated separable problem. The reminder is dedicated to the implementation of a branch-and-bound algorithm for the solution of linearized problem, and its application to a set of instances. Several points are considered among which choice of the right value for parameter K and the implementation of a sophisticated heuristic solution algorithm. The numerical comparison is done with CPLEX 12.2 since, in this case, the initial problem as well as the problem reformulated by the first step can be solved by CPLEX. We show that with our approach, the total CPU time is divided by a factor ranging from 1.2 to 131.6 for instances with 40–60 variables.     

Use of goal programming and integer programming for water quality management—A case study of Gaza Strip

This paper describes a project dealing with achieving an optimum mix of water from different underground wells, each having different amounts of nitrates and chlorides. The amounts of chlorides and nitrates in each of the wells may be higher or lower than the World Health Organization (WHO) standards. Therefore, the optimum mix would be the one that meets WHO standard which is 250 mg/l for chlorides and 50 mg/l for nitrates. A goal programming model was developed to identify the combination of wells along with the amounts of water from each well that upon mixing would result in minimizing the deviation of the amounts of chlorides and nitrates from the standards set by WHO. The output of the goal programming model along with the coordinates of the wells identified above was then used for a second model that determines the locations of the mixing points “reservoirs” in such a way that minimizes the total weighted distances from the corresponding wells. Finally, an easy-to-use pumping schedule was developed using integer programming. Results indicate that for the case study, there exist several optima which make it easier for the decision maker to consider other intangible factors if there are any.     

A goal programming model for the best possible solution to loan allocation problems

In this paper, we propose a multi-criteria decision making approach to address the problem of finding the best possible solution in credit unions. Sensitivity analysis on the priority structure of the goals has been performed to obtain all possible solutions. The study uses the Euclidean distance method to measure distances of all possible solutions from the identified ideal solution. The possible optimum solution is determined from the minimum distance between the ideal solution and other possible solutions of the problem.     

Exact and heuristic solution approaches for the mixed integer setup knapsack problem

We consider a class of knapsack problems that include setup costs for families of items. An individual item can be loaded into the knapsack only if a setup cost is incurred for the family to which it belongs. A mixed integer programming formulation for the problem is provided along with exact and heuristic solution methods. The exact algorithm uses cross decomposition. The proposed heuristic gives fast and tight bounds. In addition, a Benders decomposition algorithm is presented to solve the continuous relaxation of the problem. This method for solving the continuous relaxation can be used to improve the performance of a branch and bound algorithm for solving the integer problem. Computational performance of the algorithms are reported and compared to CPLEX.     

ABS methods for continuous and integer linear equations and optimization

ABS methods are a large class of algorithms for solving continuous and integer linear algebraic equations, and nonlinear continuous algebraic equations, with applications to optimization. Recent work by Chinese researchers led by Zunquan Xia has extended these methods also to stochastic, fuzzy and infinite systems, extensions not considered here. The work on ABS methods began almost thirty years. It involved an international collaboration of mathematicians especially from Hungary, England, China and Iran, coordinated by the university of Bergamo. The ABS method are based on the rank reducing matrix update due to Egerváry and can be considered as the most fruitful extension of such technique. They have led to unification of classes of methods for several problems. Moreover they have produced some special algorithms with better complexity than the standard methods. For the linear integer case they have provided the most general polynomial time class of algorithms so far known; such algorithms have been extended to other integer problems, as linear inequalities and LP problems, in over a dozen papers written by Iranian mathematicians led by Nezam Mahdavi-Amiri. ABS methods can be implemented generally in a stable way, techniques existing to enhance their accuracy. Extensive numerical experiments have shown that they can outperform standard methods in several problems. Here we provide a review of their main properties, for linear systems and optimization. We also give the results of numerical experiments on some linear systems. This paper is dedicated to Professor Egerváry, developer of the rank reducing matrix update, that led to ABS methods.     

The efficient computer implementation of a large-scale integer goal programming model

The development of an efficient solution strategy for solving large-scale integer goal programming problems using commercial integer programming software is described. The procedure was utilized to operationalize a computer-based multi-stage lot sizing model for the aggregate scheduling of a class of tablet products. Computational experience with the procedure in a pharmaceutical manufacturing environment is discussed.     

On the solution of highly degenerate linear programmes

The solution of scheduling problems often gives rise to highly degenerate linear programmes which cause significant computational difficulties for the revised simplex method. Wolfe's highly effective ad hoc method for overcoming the cycling or stalling problems associated with degeneracy is described. Here it is given a geometric interpretation in terms of finding a direction of recession for a reduced problem which is fundamental to a full understanding of the procedure. An example of an aircrew scheduling problem is used to illustrate the effectiveness of the method.     

Uniqueness of integer solution of linear equations

We consider the system of m linear equations in n integer variables Ax = d and give sufficient conditions for the uniqueness of its integer solution x ∈ {−1, 1} ⁿ by reformulating the problem as a linear program. Necessary and sufficient uniqueness characterizations of ordinary linear programming solutions are utilized to obtain sufficient uniqueness conditions such as the intersection of the kernel of A and the dual cone of a diagonal matrix of ±1’s is the origin in R ⁿ . This generalizes the well known condition that ker(A) = 0 for the uniqueness of a non-integer solution x of Ax = d. A zero maximum of a single linear program ensures the uniqueness of a given integer solution of a linear equation.     

On the greedy solution in integer linear programming

A version of the greedy method not using any knapsack relaxation of the integer programming problem is considered in this paper. It is based on a natural partial ordering of the vectors. Our aim is to determine a large class of problems where the greedy solution is always optimal. The results generalize some theorems of an early paper of Magazine, Nemhauser and Trotter and at the same time show a connection between two different notions of combinatorics: the greedy method and the Hilbert basis.

---

Zusammenfassung In dieser Arbeit wird eine Version des Greedy-Algorithmus zur Lösung ganzzahliger linearer Optimierungsprobleme benutzt, die kein Rucksackproblem als Relaxation verwendet. Das Verfahren basiert auf der natürlichen partiellen Ordnung von Vektoren. Ziel der Arbeit ist es, eine möglichst große Problemklasse zu beschreiben, für die die Greedy-Lösung optimal ist. Die Ergebnisse verallgemeinern Sätze einer früheren Arbeit von Magazine, Nemhauser und Trotter und zeigen gleichzeitig einen Bezug zwischen zwei verschiedenen Gebieten der Kombinatorik auf: des Greedy-Verfahrens und von Hubert-Basen.

     

Using integer programming techniques for the solution of an experimental design problem

Latin hypercube sampling is often used to estimate the distribution function of a complicated function of many random variables. In so doing, it is typically necessary to choose a permutation matrix which minimizes the correlation among the cells in the hypercube layout. This problem can be formulated as a generalized, multi-dimensional assignment problem. For the two-dimensional case, we provide a polynomial algorithm. For higher dimensions, we offer effective heuristic and bounding procedures.Supported in part by a grant from the National Institute of Standards and Technology (60NANB9D-0974).Supported in part by grants from the Office of Naval Research (N00014-90-J-1324) and the Air Force Office of Scientific Research (F49 620-90-C-0022).Research partially performed while visiting the Department of Mathematics, Brunel University, Uxbridge, England.