An optimization-based approach to assess non-interference in labeled and bounded Petri net systems

An optimization-based approach to assess both strong non-deterministic non- interference (SNNI) and bisimulation SNNI (BSNNI) in discrete event systems modeled as labeled Petri nets is presented in this paper. The assessment of SNNI requires the solution of feasibility problems with integer variables and linear constraints, which is derived by extending a previous result given in the case of unlabeled net systems. Moreover, the BSNNI case can be addressed in two different ways. First, similarly to the case of SNNI, a condition to assess BSNNI, which is necessary and sufficient, can be derived from the one given in the unlabeled framework, requiring the solution of feasibility problems with integer variables and linear constraints. Then, a novel necessary and sufficient condition to assess BSNNI is given, which requires the solution of integer feasibility problems with nonlinear constraints. Furthermore, we show how to recast these problems into equivalent mixed-integer linear programming (MILP) ones. The effectiveness of the proposed approaches is shown by means of several examples. It turns out that there are relevant cases where the new condition to assess BSNNI that requires the solution of MILP problems is computationally more efficient, when compared to the one that requires the solution of feasibility problems.     

A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem

This paper presents an efficient solution algorithm for the multiconstraint zero-one knapsack problem through a branch and bound search process. The algorithm has been coded in FORTRAN; and a group of thirty 5-constraint knapsack problems with 30-90 variables were run on IBM 360/75 using two other codes as well, in order to compare the computational efficiency of the proposed method with that of the original Balas and an improved Balas additive algorithms. The computational results show that the proposed method is markedly faster with regard to the total as well as the individual solution times for these test problems, and such superiority becomes more evident as the number of variables and the difficulty of the problems increase. The results also indicated that the original Balas method is extremely inefficient for the type of problems being considered here. The total solution time for the thirty problems is 13 min for the proposed method, 109 min for the improved Balas algorithm, and over 380 min for the original Balas algorithm. Extension of the solution algorithm to the generalized knapsack problem is also suggested.     

求解非凸区域上凸函数比式和问题的全局优化方法

针对非凸区域上的凸函数比式和问题,给出一种求其全局最优解的确定性方法.该方法基于分支定界框架.首先通过引入变量,将原问题等价转化为d.c.规划问题,然后利用次梯度和凸包络构造松弛线性规划问题,从而将关键的估计下界问题转化为一系列线性规划问题,这些线性规划易于求解而且规模不变,更容易编程实现和应用到实际中;分支采用单纯形对分不但保证其穷举性,而且使得线性规划规模更小.理论分析和数值实验表明所提出的算法可行有效.     

Cutting and Surrogate Constraint Analysis for Improved Multidimensional Knapsack Solutions

We use surrogate analysis and constraint pairing in multidimensional knapsack problems to fix some variables to zero and to separate the rest into two groups – those that tend to be zero and those that tend to be one, in an optimal integer solution. Using an initial feasible integer solution, we generate logic cuts based on our analysis before solving the problem with branch and bound. Computational testing, including the set of problems in the OR-library and our own set of difficult problems, shows our approach helps to solve difficult problems in a reasonable amount of time and, in most cases, with a fewer number of nodes in the search tree than leading commercial software.     

Combinatorial integral approximation

We are interested in structures and efficient methods for mixed-integer nonlinear programs (MINLP) that arise from a first discretize, then optimize approach to time-dependent mixed-integer optimal control problems (MIOCPs). In this study we focus on combinatorial constraints, in particular on restrictions on the number of switches on a fixed time grid. We propose a novel approach that is based on a decomposition of the MINLP into a NLP and a MILP. We discuss the relation of the MILP solution to the MINLP solution and formulate bounds for the gap between the two, depending on Lipschitz constants and the control discretization grid size. The MILP solution can also be used for an efficient initialization of the MINLP solution process. The speedup of the solution of the MILP compared to the MINLP solution is considerable already for general purpose MILP solvers. We analyze the structure of the MILP that takes switching constraints into account and propose a tailored Branch and Bound strategy that outperforms cplex on a numerical case study and hence further improves efficiency of our novel method.     

A Branch and Contract Algorithm for Problems with Concave Univariate, Bilinear and Linear Fractional Terms

A new deterministic branch and bound algorithm is presented in this paper for the global optimization of continuous problems that involve concave univariate, bilinear and linear fractional terms. The proposed algorithm, the branch and contract algorithm, relies on the use of a bounds-contraction subproblem that aims at reducing the size of the search region by eliminating portions of the domain in which the objective function takes only values above a known upper bound. The solution of contraction subproblems at selected branch and bound nodes is performed within a finite contraction operation that helps reducing the total number of nodes in the branch and bound solution tree. The use of the proposed algorithm is illustrated with several numerical examples.     

Parallel distributed block coordinate descent methods based on pairwise comparison oracle

The aim of this paper is to find the global solutions of uncertain optimization problems having a quadratic objective function and quadratic inequality constraints. The bounded epistemic uncertainties in the constraint coefficients are represented using either universal or existential quantified parameters and interval parameter domains. This approach allows to model non-controlled uncertainties by using universally quantified parameters and controlled uncertainties by using existentially quantified ones. While existentially quantified parameters could be equivalently considered as additional variables, keeping them as parameters allows maintaining the quadratic problem structure, which is essential for the proposed algorithm. The branch and bound algorithm presented in the paper handles both universally and existentially quantified parameters in a homogeneous way, without branching on their domains, and uses some dedicated numerical constraint programming techniques for finding a robust, global solution. Several examples clarify the theoretical parts and the tests demonstrate the usefulness of the proposed method.     

Relaxations and approximations of chance constraints under finite distributions

Optimization problems with constraints involving stochastic parameters that are required to be satisfied with a prespecified probability threshold arise in numerous applications. Such chance constrained optimization problems involve the dual challenges of stochasticity and nonconvexity. In the setting of a finite distribution of the stochastic parameters, an optimization problem with linear chance constraints can be formulated as a mixed integer linear program (MILP). The natural MILP formulation has a weak relaxation bound and is quite difficult to solve. In this paper, we review some recent results on improving the relaxation bounds and constructing approximate solutions for MILP formulations of chance constraints. We also discuss a recently introduced bicriteria approximation algorithm for covering type chance constrained problems. This algorithm uses a relaxation to construct a solution whose (constraint violation) risk level may be larger than the pre-specified threshold, but is within a constant factor of it, and whose objective value is also within a constant factor of the true optimal value. Finally, we present some new results that improve on the bicriteria approximation factors in the finite scenario setting and shed light on the effect of strong relaxations on the approximation ratios.     

A new branching rule for the branch and bound algorithm for solving nonlinear integer programming problems

We examine a branch and bound algorithm for solving nonlinear (convex) integer programming problems. In this note we generalize previous results for the quadratic case. The variables are branched in such a way that the number of branch and bound nodes checked in the process is small. Numerical results confirm the efficiency.     

A relaxation method for nonconvex quadratically constrained quadratic programs

We present an algorithm for finding approximate global solutions to quadratically constrained quadratic programming problems. The method is based on outer approximation (linearization) and branch and bound with linear programming subproblems. When the feasible set is non-convex, the infinite process can be terminated with an approximate (possibly infeasible) optimal solution. We provide error bounds that can be used to ensure stopping within a prespecified feasibility tolerance. A numerical example illustrates the procedure. Computational experiments with an implementation of the procedure are reported on bilinearly constrained test problems with up to sixteen decision variables and eight constraints.This research was supported in part by National Science Foundation Grant DDM-91-14489.     

可靠性网络中费用最小化问题的一种新的分枝定界算法

本文对可靠性网络中串-并系统的费用最小化问题提出一种新的分枝定界算法.我们根据这类网络的特殊结构和性质,建立了新的最优性必要条件,在分枝搜索过程中增加新的剪枝准则,从而加速了算法的收敛速度.有效的数值试验表明,该算法可求解大规模可靠性网络的费用最小化问题.     

A Branch and Bound Algorithm for Separable Concave Programming

In this paper, we propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles when one problem is branched into two subproblems. It is proved that the LDB method is a normal rectangle subdivision(NRS). Numerical tests on problems with dimensions from 100 to 10000 show that the proposed branch and bound algorithm is efficient for solving large scale separable concave programming problems, and convergence rate is faster than ω-subdivision method.     

Global optimization algorithm for sum of generalized polynomial ratios problem

In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum.     

A New Approach to Optimization Under Monotonic Constraint

A new efficient branch and bound method is proposed for solving convex programs with an additional monotonic nonconvex constraint. Computational experiments demonstrated that this method is quite practical for solving rank k reverse convex programs with much higher values of k than previously considered in the literature and can be applied to a wider class of nonconvex problems.     

Global optimization algorithm for a generalized linear multiplicative programming

This article present a branch and bound algorithm for globally solving generalized linear multiplicative programming problems with coefficients. The main computation involve solving a sequence of linear relaxation programming problems, and the algorithm economizes the required computations by conducting the branch and bound search in R ^p , rather than in R ⁿ , where p is the number of rank and n is the dimension of decision variables. The proposed algorithm will be convergent to the global optimal solution by means of the subsequent solutions of the series of linear relaxation programming problems. Numerical results are given to show the feasibility and effectiveness of the proposed algorithm.     

Robust scheduling of parallel machines with sequence-dependent set-up costs

In this paper we propose a robust approach for solving the scheduling problem of parallel machines with sequence-dependent set-up costs. In the literature, several mathematical models and solution methods have been proposed to solve such scheduling problems, but most of which are based on the strong assumption that input data are known in a deterministic way. In this paper, a fuzzy mathematical programming model is formulated by taking into account the uncertainty in processing times to provide the optimal solution as a trade-off between total set-up cost and robustness in demand satisfaction. The proposed approach requires the solution of a non-linear mixed integer programming (NLMIP), that can be formulated as an equivalent mixed integer linear programming (MILP) model. The resulting MILP model in real applications could be intractable due to its NP-hardness. Therefore, we propose a solution method technique, based on the solution of an approximated model, whose dimension is remarkably reduced with respect to the original counterpart. Numerical experiments conducted on the basis of data taken from a real application show that the average deviation of the reduced model solution over the optimum is less than 1.5%.     

Solving a two-dimensional trim-loss problem with MILP

In this paper a two-dimensional trim-loss problem connected to the paper-converting industry is considered. The problem is to produce a set of product paper rolls from larger raw paper rolls such that the cost for waste and the cutting time is minimized. The problem is generally non-convex due to a bilinear objective function and some bilinear constraints, which give rise to difficulties in finding efficient numerical procedures for the solution. The problem can, however, be solved as a two-step procedure, where the latter step is a mixed integer linear programming (MILP) problem. In the present formulation, both the width and length of the raw paper rolls as well as the lengths of the product paper rolls are considered variables. All feasible cutting patterns are included in the problem and global optimal cutting patterns are obtained as the solution from the corresponding MILP problem. A numerical example is included to illustrate the proposed procedure.     

Nonlinear integer programming for optimal allocation in stratified sampling

A stratified random sampling plan is one in which the elements of the population are first divided into nonoverlapping groups, and then a simple random sample is selected from each group. In this paper, we focus on determining the optimal sample size of each group. We show that various versions of this problem can be transformed into a particular nonlinear program with a convex objective function, a single linear constraint, and bounded variables. Two branch and bound algorithms are presented for solving the problem. The first algorithm solves the transformed subproblems in the branch and bound tree using a variable pegging procedure. The second algorithm solves the subproblems by performing a search to identify the optimal Lagrange multiplier of the single constraint. We also present linearization and dynamic programming methods that can be used for solving the stratified sampling problem. Computational testing indicates that the pegging branch and bound algorithm is fastest for some classes of problems, and the linearization method is fastest for other classes of problems.     

Parallel branch and bound for multidimensional scaling with city-block distances

Multidimensional scaling is a technique for exploratory analysis of multidimensional data. The essential part of the technique is minimization of a multimodal function with unfavorable properties like invariants and non-differentiability. Recently a branch and bound algorithm for multidimensional scaling with city-block distances has been proposed for solution of medium-size problems exactly. The algorithm exploits piecewise quadratic structure of the objective function. In this paper a parallel version of the branch and bound algorithm for multidimensional scaling with city-block distances has been proposed and investigated. Parallel computing enabled solution of larger problems what was not feasible with the sequential version.     

A Branch and Bound Algorithm to Minimize Total Weighted Tardiness on a Single Processor

In this paper, we consider the problem of minimizing the total weighted tardiness of a set of jobs processed on a single processor. First, a lower bound based on a Lagrangian decomposition is presented. The particularity of this decomposition, based on a 0–1 time indexed formulation, is to be sensitive to the domain reduction of jobs which are proposed. A branch and bound strategy including these different components is proposed. The results obtained on problems from the literature can be favourably compared to previously works and seem to prove that a trade-off between a tight lower bound and time consuming in the enumeration process can be a good strategy.