Table of Content

15 June 2020, Volume 24 Issue 2

Previous Issue    Next Issue

The fundamental theorem for the probability calculations of the paradox of voting

HU Yuda

2020, 24(2):  1-13.  doi:10.15960/j.cnki.issn.1007-6093.2020.02.001

Asbtract ( 1179 )   PDF (538KB) ( 330 )  

References | Related Articles | Metrics

The majority preference rule is one of the most important and widely used rule in solving group optimization problems. However, in the process of using this rule to find the optimal solution for a given group optimization problem, sometimes there will be a "paradox of voting" phenomenon of group preference cyclic ordering. Therefore, the probability calculations of "paradox of voting" has become a fundamental research topic in group optimization. In this paper, the concepts of "sorting profile of the paradox of voting" and "selection profile of the paradox of voting" of a group on scheme set are introduced. With the help of them, a fundamental theorem for the probability calculations of the "paradox of voting" is established under the general condition that each individual in a group has different probability distribution for the preference ranking of all schemes, and when a group chooses the best scheme for a problem. Thus, the fundamental problem that has not been solved thoroughly for a long time in the study for the probability calculations of the "paradox of voting" is solved.

Fixed points and equilibrium points

YU Jian, JIA Wensheng

2020, 24(2):  14-22.  doi:10.15960/j.cnki.issn.1007-6093.2020.02.002

Asbtract ( 1174 )   PDF (533KB) ( 296 )  

References | Related Articles | Metrics

In this paper, we introduce some equivalence results of the existence theorem on Brouwer fixed point theorem, Kakutani fixed point theorem, equilibrium points of mathematical economics and Nash equilibrium theorem of game theory.

Some advances in low-rank matrix optimization

LI Xinrong, XIU Naihua, LUO Ziyan

2020, 24(2):  23-41.  doi:10.15960/j.cnki.issn.1007-6093.2020.02.003

Asbtract ( 1278 )   PDF (704KB) ( 584 )  

References | Related Articles | Metrics

Low-rank matrix optimization is a class of matrix optimization problems with rank minimization or rank constraint. With wide applications ranging from statistics and machine learning, signal and image processing, communication and quantum computing, system identification and control, to economics and finance, low-rank matrix optimization is currently a key research direction in optimization and related fields. However, due to the intrinsic non-convexity and discontinuity in the rank function, low-rank matrix optimization is generally NP-hard. Existing research results in this direction are not very rich, and further research is urgently needed. In this paper, we mainly summarize and review some latest research results on low-rank matrix optimization in theory and in algorithm, along with related important references, so as to dedicate to readers.

Optimal algorithms for hybrid flow shop schedule on two machines with learning effect

ZHAO Congcong, FANG Dandan, LI Rongheng

2020, 24(2):  42-60.  doi:10.15960/j.cnki.issn.1007-6093.2020.02.004

Asbtract ( 761 )   PDF (1803KB) ( 165 )  

References | Related Articles | Metrics

In this paper, optimal algorithms are proposed for hybrid flow shop schedule of identical jobs on two machines (named as M₁ and M₂) with learning effect. In our problem, each job has two tasks, named as task A and task B respectively, and two optional processing modes. The task B can start to be processed only if after task A has been finished. The first processing mode, named as mode 1, is to assign both task A and B to machine M₂. The second processing mode, named mode 2, is to assign task A and B to machine M₁ and M₂, respectively. It is assumed that each machine has learning effect when processing the job, in other words, the actual processing time of the job is related to the processing position of the job. Our objective is to minimize the makespan. Optimal algorithms are given for two systems with no buffer and infinite buffer respectively.

A second-order cone programming algorithm for pooling problem

REN Yequan, BAI Yanqin, LI Qian, YU Changjun, ZHANG Liansheng

2020, 24(2):  61-72.  doi:10.15960/j.cnki.issn.1007-6093.2020.02.005

Asbtract ( 713 )   PDF (709KB) ( 265 )  

References | Related Articles | Metrics

The pooling problem plays an important role in industrial production planning. The optimization model of this problem is similar to the minimum cost problem. However, due to the complexity of the problem, the pooling problem is strong NP-hard even with only one quality. In this paper, based on the optimization model proposed by Dai, we reformulate the model step by step. First, we reformulated the primal model into a quadratic non-convex optimization model equivalently. Then, we relaxed and inner approximate quadratic non-convex optimization model into both second-order cone programming problem, respectively. To solve both second-order cone programming problem, we used the branch and bound method to approximate the optimal solution of the original problem by solving the upper and lower bounds. Finally, we carried out the numerical experiments by using seven examples to demonstrate the effectiveness of our models and the algorithm.

A survey on streaming algorithms for maximizing submodular functions

YANG Ruiqi, XU Dachuan, DU Donglei, ZHANG Dongmei

2020, 24(2):  73-86.  doi:10.15960/j.cnki.issn.1007-6093.2020.02.006

Asbtract ( 1313 )   PDF (634KB) ( 492 )  

References | Related Articles | Metrics

While submodular function optimization has been studied extensively in computer science, mathematics, and economics, etc., submodular optimization in big data environment is a relatively new field that has attracted many attentions recently. In particular, submodular optimization with streaming data is the focus of this work. Facing real-time streaming data revealed in real time, the goal is to select a sparse subset satisfying certain desirable features from the stream to maximize certain submodular utility function. The main purpose of this paper is to provide suggestions for future research on this important class of problems. We introduce the threshold and preemption methods for the streaming submodular maximization problem. We also investigate the development of streaming algorithms for some variants of submodular maximization problems.

The models and optimization method for power system unit commitment problems

JIAN Jinbao, YANG Linfeng, ZHANG Chen

2020, 24(2):  87-102.  doi:10.15960/j.cnki.issn.1007-6093.2020.02.007

Asbtract ( 2220 )   PDF (704KB) ( 592 )  

References | Related Articles | Metrics

Unit commitment problem is an important part of the power system, which can often be modeled as a high-dimensional mixed integer programming problem. This paper aims to systematically collect and analyze the frontier work of UC modeling and optimization methods, including part of the work of the author and his collaborators. This paper firstly gives the mathematical model of UC problem, and deeply analyzes the basic principles for solving UC problems and the research results obtained are discussed. And the UC extension problem (including valve-point effect, hydraulic power generation and optimal power flow) were discussed and analyzed. Finally, this paper discusses the development direction of UC in the smart grid environment, puts forward the problems that need to be studied and solved (such as multi-energy flow, stochastic factors, deep learning, etc.), so as to provide reference for research of UC.

Mathematical model of compensating magnetic field for ferromagnetic equipment and its application

DING Yujie, ZHANG Jie, LU Zhen, LU Xiwen

2020, 24(2):  103-110.  doi:10.15960/j.cnki.issn.1007-6093.2020.02.008

Asbtract ( 657 )   PDF (4220KB) ( 169 )  

References | Related Articles | Metrics

In this paper, the problem of magnetic field compensation for ferromagnetic equipment with permanent magnets is studied, and a mathematical model of the compensation magnetic field is established. After dividing the device into several small cuboids, a mathematical model is established based on the magnetic moment method to simulate the compensation magnetic field. When calculating the coupling coefficient matrix in the model, we use the average of multiple points as the effective value of the coupling coefficient, which improves the reliability and stability of the calculation results. Moreover, for the nonlinear magnetization characteristics of the equipment when the permanent magnet is close to the equipment, the equivalent susceptibility of each unit is solved by optimization method. This method does not need to know the magnetization curve of the ferromagnetic material, which is convenient for calculation and practical application. Finally, through the experimental design and numerical calculation, the magnetic field distribution of the permanent magnet compensation device is obtained. The error between our model calculation result and the actual measurement data is within 11%, which shows that the model can satisfy the industrial requirements. Therefore, the models and calculation method have practical application value.

A survey on job scheduling with rejection

ZHANG Yuzhong

2020, 24(2):  111-130.  doi:10.15960/j.cnki.issn.1007-6093.2020.02.009

Asbtract ( 1087 )   PDF (776KB) ( 309 )  

References | Related Articles | Metrics

Scheduling with rejection is a representative and applied scheduling that emerged around 2000. It is one of the generalizations of the classical scheduling problems. In classical scheduling problems, it is assumed that all jobs have to be processed. However, in practice, for some special reasons, policy makers will reject the processing of some jobs. That is what we called job scheduling with rejection. It is noteworthy that the problem has a certain application background and great application value, and also has important significance in theory. The problem is gaining more and more attention recently and new results are welling up.In this paper, we give a comprehensive introduction to online and offline scheduling with job rejection. We also give abundant references, including many existing research results and new research directions. It's designed to help the interested readers rapidly to the research frontier.

Single-machine scheduling to minimize total weighted late work with positional due-indices

CHEN Rubing, YUAN Jinjiang

2020, 24(2):  131-144.  doi:10.15960/j.cnki.issn.1007-6093.2020.02.010

Asbtract ( 689 )   PDF (525KB) ( 153 )  

References | Related Articles | Metrics

We consider the single-machine scheduling problem to minimize the total weighted late work with positional due-indices. In the problem, each job J_j has a positional due-index k_j. That is, if J_j is the x-th job in a feasible schedule, then it is required that x ≤ k_j. In this paper, we show that (i) the problem is binary NP-hard and can be solved in pseudo-polynomial-time if all the jobs have a common due date, (ii) the problem is unary NP-hard even if all the jobs have a unit weight.