Method of Linear Programming as an Idea for High School Curriculum

2010 Mathematics Subject Classification: 97D40, 97M10, 97M40, 97N60, 97N80, 97R80

Data Flow Analysis and the Linear Programming Model

* The research is supported partly by INTAS: 04-77-7173 project, http://www.intas.be

A Mixed Integer Quadratic Programming Model for the Low Autocorrelation Binary Sequence Problem

In this paper the low autocorrelation binary sequence problem (LABSP) is modeled as a mixed integer quadratic programming (MIQP) problem and proof of the model’s validity is given. Since the MIQP model is semidefinite, general optimization solvers can be used, and converge in a finite number of iterations. The experimental results show that IQP solvers, based on this MIQP formulation, are capable of optimally solving general/skew-symmetric LABSP instances of up to 30/51 elements in a moderate time. ACM Computing Classification System (1998): G.1.6, I.2.8.

CAPS in Z(2,n)

We consider point sets in (Z^2,n) where no three points are on a line – also called caps or arcs. For the determination of caps with maximum cardinality and complete caps with minimum cardinality we provide integer linear programming formulations and identify some values for small n.

Maximization of a Linear Utility Function over the Set of the Housing Market Short-Term Equilibria

AMS subject classification: 90C05, 90A14.

New Upper Bounds for Some Spherical Codes

The maximal cardinality of a code W on the unit sphere in n dimensions with (x, y) ≤ s whenever x, y ∈ W, x 6= y, is denoted by A(n, s). We use two methods for obtaining new upper bounds on A(n, s) for some values of n and s. We find new linear programming bounds by suitable polynomials of degrees which are higher than the degrees of the previously known good polynomials due to Levenshtein [11, 12]. Also we investigate the possibilities for attaining the Levenshtein bounds [11, 12]. In such cases we find the distance distributions of the corresponding feasible maximal spherical codes. Usually this leads to a contradiction showing that such codes do not exist.

Exact Discriminant Function Design Using Some Optimization Techniques

Some aspects of design of the discriminant functions that in the best way separate points of predefined final sets are considered. The concept is introduced of the nested discriminant functions which allow to separate correctly points of any of the final sets. It is proposed to apply some methods of non-smooth optimization to solve arising extremal problems efficiently.

An Interactive Method of Linear Mixed Integer Multicriteria Optimization

The paper describes a learning-oriented interactive method for solving linear mixed integer problems of multicriteria optimization. The method increases the possibilities of the decision maker (DM) to describe his/her local preferences and at the same time it overcomes some computational difficulties, especially in problems of large dimension. The method is realized in an experimental decision support system for finding the solution of linear mixed integer multicriteria optimization problems.

Integer Programming Approach to HP Folding

One of the most widely studied protein structure prediction models is the hydrophobic-hydrophilic (HP) model, which explains the hydrophobic interaction and tries to maximize the number of contacts among hydrophobic amino-acids. In order to find a lower bound for the number of contacts, a number of heuristics have been proposed, but finding the optimal solution is still a challenge. In this research, we focus on creating a new integer programming model which is capable to provide tractable input for mixed-integer programming solvers, is general enough and allows relaxation with provable good upper bounds. Computational experiments using benchmark problems show that our formulation achieves these goals.

Non-Linear Network-Flow Model of Lukasiewicz’s Multivalue Logic

The paper presents a new network-flow interpretation of Łukasiewicz’s logic based on models with an increased effectiveness. The obtained results show that the presented network-flow models principally may work for multivalue logics with more than three states of the variables i.e. with a finite set of states in the interval from 0 to 1. The described models give the opportunity to formulate various logical functions. If the results from a given model that are contained in the obtained values of the arc flow functions are used as input data for other models then it is possible in Łukasiewicz’s logic to interpret successfully other sophisticated logical structures. The obtained models allow a research of Łukasiewicz’s logic with specific effective methods of the network-flow programming. It is possible successfully to use the specific peculiarities and the results pertaining to the function ‘traffic capacity of the network arcs’. Based on the introduced network-flow approach it is possible to interpret other multivalue logics – of E.Post, of L.Brauer, of Kolmogorov, etc.

Optimal Decision Rules in Logical Recognition Models

The task of smooth and stable decision rules construction in logical recognition models is considered. Logical regularities of classes are defined as conjunctions of one-place predicates that determine the membership of features values in an intervals of the real axis. The conjunctions are true on a special no extending subsets of reference objects of some class and are optimal. The standard approach of linear decision rules construction for given sets of logical regularities consists in realization of voting schemes. The weighting coefficients of voting procedures are done as heuristic ones or are as solutions of complex optimization task. The modifications of linear decision rules are proposed that are based on the search of maximal estimations of standard objects for their classes and use approximations of logical regularities by smooth sigmoid functions.

N–Dimensional Orthogonal Tile Sizing Problem

AMS subject classification: 68Q22, 90C90