Solving nonlinear integer programs with large-scale optimization software

This paper describes recent experience in tackling large nonlinear integer programming problems using the MINOS large-scale optimization software. A technique is presented for extending the constrained search approach used in MINOS to exploring integer-feasible solutions once a continuous optimal solution is obtained. Computational experience with this approach is described for two classes of problems: quadratic assignment problems and pipeline network design problems.     

Optimal sequencing in the presence of setup times for tow/barge traffic through a river lock

Queues of tow/barges form when a river lock is rendered inoperable due to lock malfunction, a tow/barge accident or adverse lock operating conditions. In this paper, we develop model formulations that allow the queue to be cleared using a number of differing objectives. Of particular interest is the presence of different setup times between successive passages of tow/barges through the lock. Dependent on the objective chosen, we are able to show that certain ordering protocols may be used to markedly reduce the sequencing search space for N tow/barges from the order of N! to 2^N. We present accompanying linear and nonlinear integer programming formulations and carry out computational experiments on a representative set of problems.     

MONOTONIZATION IN GLOBAL OPTIMIZATION

A general monotonization method is proposed for converting a constrained programming problem with non-monotone objective function and monotone constraint functions into a monotone programming problem. An equivalent monotone programming problem with only inequality constraints is obtained via this monotonization method. Then the existing convexification and concavefication methods can be used to convert the monotone programming problem into an equivalent better-structured optimization problem.     

Flow-shop scheduling with setup and assembly operations

A scheduling model for a production system including machining, setup and assembly operations is considered. Production of a number of single-item products is ordered. Each product is made by assembling a set of several different parts. First, the parts are manufactured in a flow-shop consisting of multiple machines. Then, they are assembled into products on a single assembly stage. Setup operation and setup time are needed when a machine starts processing the parts or it changes items. The operations are partitioned into several blocks. Each block consists of the machining operations, the setup operations, and the assembly operation(s) for one or several products. The parts of the same item in a block are processed successively. The objective function is the mean completion time for all products. We consider a problem to partition the operations into blocks and sequence the parts in each block so as to minimize the objective function. Solution procedures using pseudo-dynamic programming and a branch-and-bound method are proposed. Computational experiments are carried out to evaluate the performance of the solution procedures. It has been found that a good near-optimal schedule is obtained efficiently by the proposed solution procedures.     

Finding multiple solutions to general integer linear programs

Integer linear programming (ILP) problems occur frequently in many applications. In practice, alternative optima are useful since they allow the decision maker to choose from multiple solutions without experiencing any deterioration in the objective function. This study proposes a general integer cut to exclude the previous solution and presents an algorithm to identify all alternative optimal solutions of an ILP problem. Numerical examples in real applications are presented to demonstrate the usefulness of the proposed method.     

求解0-1背包问题的两种方法的分析与比较

背包问题(KP)是计算机科学中典型的NP-hard问题,不存在多项式时间的精确算法。本文首先给出了求解0-1KP问题的一种改进的近似算法,讨论了算法复杂度与近似比;然后,给出了求解0-1KP的动态规划算法描述,并分析了算法的复杂度;最后,对两种方法进行了理论分析,并利用3个较大规模0-1KP实例的仿真计算结果与GDPSO进行比较。     

正值函数乘积的极小和问题

研究下述非线性规划问题（ＮＬＰ）ｍｉｎΣｉ－１↑ｓ（Пｊ＝１↑ｋｆｉｊ（ｘ）＾１／ｋ，这里ｆｉｊ：Ｘ→Ｒ＾＋，其中Ｘ表示Ｒ＾ｎ中的非空紧致集，Ｒ＾＋表示正实数集，ｉ＝１，２，…，ｓ，ｊ＝１，２，…，ｋ。借助〔１〕的引理１，（ＮＬＰ）问题可简化为含ｓ×ｋ个参数的因子函数之和的最小化问题，证明最优参数只须取一些特定的值。特别，如果ｆｉｊ均为线性函数，Ｘ为凸多面体，则其最优解必定可以在Ｘ的顶点处实现。     

CGC using a programmable electronic pressure controller

Capillary gas chromatographic separations were performed with an electronic pressure control system developed to provide precise closed-loop control of inlet pressure through the use of a solid state micro-machined pressure sensor and electronically controlled proportional valve. The closed-loop control of the electronic system provided better precision than the open-loop control achieved by manual pressure regulation. Closed-loop control can perform pressure programming, which can be combined with temperature programming to optimize separations. The pressure sensor monitors the integrity of the flow system and singals the controller to reduce flow in the presence of a sudden loss of system pressure.     

Design and implementation of DBC based on dynamic AOP

Traditional approach of design by contract, due to mixing the contract code with application code, is difficult for the extensibility and reusability of software system. This paper presents a framework named JADBC for design by contract based on Aspect-Oriented Programming (AOP) to resolve these problems. By providing a new modularized element, aspect, the framework successfully separates the contracts in design by contract, from functional codes. The implementation of this framework is based on dynamic AOP which can have the contract changed at runtime, consequently, enhancing program flexibility. JADBC framework modularizes the contracts in a clear-cut fashion that is easier to design, implement, and maintain. Biography: WEN Jing (1982–), female, Ph.D. candidate, research directions: software engineer, aspect-oriented software development.     

On the noniterative multiproduct multiperiod production planning method

Bahl and Zionts [H.C. Bahl, S. Zionts, A noniterative multiproduct multiperiod production planning method, Operations Research Letters 1 (1982) 219-221] formulated a problem for planning multiproduct multiperiod production on a single facility. They developed a column-minima noniterative method and claimed that it gave an optimal solution. We show that the claim is incorrect.