Linear Optimization
The Associated Data Files

D. Baruth, Dr. rer. nat.
Los Angeles, California
x86@iging.com



Standard file structures for efficient storage and transport of optimization data are proposed.  The input data, defining a linear maximization problem, can be in any standard x86/87 format.   The elements in the output file containing the resulting optimal decision variables are 80-bit floating point (R*10, Tbyte).




Introduction

Linear optimization is a procedure to optimally plan complex operations.  It is based on a set of variables, so called decision variables, that define the objective of a particular operation.  Quantitative constraints are defined as a set of linear inequalities (or equalities).

For example, consider a manufacturing operation of some products, using different resources in the process, with the objective to maximize profits under known quantifiable constraints. Such an operation can be formulated mathematically as follows:

Decision Variables   m different products xi ≥ 0,
Objective Coefficients    pi = profit per product ;  i ≤ m
Constraints    n resources and other constraints rj ≥ 0,
Operation Coefficients    aji = constraint j per product i ;  j ≤ n
Objective    Maximize (Minimize) P =  p1x1+p2x2+...+pmxm
Operation Matrix    Solve:
   a11x1+a12x2+... +a1mxm ≤ r1
   a21x1+a22x2+... +a2mxm ≤ r2
   ..................................
   aj1x1+aj2x2+ ...  +ajmxm ≥ rj
   ..................................
   an1x1+an2x2+... +anmxm ≤ rn
Notice the "≥" relation in row j of the linear system above.  This indicates a non-standard optimization problem.  In standard linear optimization problems the production matrix contains only the "≤" relations.  minimization problems are solved by finding the maximum of the negative objective function.


The Input Data File

Given all required quantitative information about an operation, mathematical algorithms can be applied to solve related linear optimization problems; the most popular of which being the Simplex Method. Using a computer program, all data relevant to an operation must be accessed either through human interface or electronic storage.  There are a few popular (ASCII) file formats for data acquisition and storage, e.g. MPS (Mathematical Programming System), that are comprehensive in scope and have the ability to describe a variety of linear problems.   However, for a computer program, the most efficient method to save, transport and access data is through binary files.  The following file structure, in x86/87 notation, contains all required data elements to solve a linear maximization problem.

   VarType DB ?    ; 0 = Integer, 1 = Real, 2 = BCD
   VarSz DB ?    ; 1=Byte,2=Word,4=Dword,8=Qword,10=Tbyte
   NumD DD m    ; number of decision variables (products)
   NumC DD n    ; number of constraints (resources)
   ConRel DB n   DUP (?)    ; constraints relation flags [j] ε {-1,0,+1}, jn
   Objective [VarSz] m  DUP (?)    ; objective (profit) coef. array [pi] with m elements
   Constraint [VarSz] n   DUP (?)    ; constraints array [rj] with n elements
   OpMtrx [VarSz] n   DUP (m  DUP (?))    ; operation (production) coef. matrix [aji] with m columns and n rows

The elements of the constraints relations flags array (ConRel) represent the type of constraint for each row in the Operations Matrix: "≤" ≡ −1, "=" ≡ 0, "≥" ≡ +1.  Therefore, in standard linear optimization problem all flags are set to −1.  The minimal size of an input data file will thus be   10 + VarSz*(m + n + m*n) + n  bytes.  This structure enables the solver (_Simplex) to decode any standard (x86/87) number.  Note that all array elements must be of the same size (VarSz) and type (VarType).  In particular, Integers may be  1,2,4 or 8  bytes long; Real numbers,  4,8  or 10 bytes and BCD  10  bytes.


The Results File

A problem solving procedure can save the results to any memory device.  The associated binary file may have the following structure:

   NumD DD m    ; number of decision variables (products)
   NumC DD n    ; number of constraints (resources)
   Max DT P    ; resulting maximum (profit) P
   D_Var DT m   DUP (?)    ; array of resulting decision variables [xi], im
   S_Var DT n   DUP (?)    ; array of resulting slack or surplus variables [sj], jn

The slack or surplus variables  sj  are the quantities of constraints that have not been utilized.  Note that all results are returned as 80 bit floating point numbers (DT = Tbyte), and the file size is  8 + 10*(1 + m + n)  bytes.


System Requirements & Limitations

Optimizing large and complex operations involves large numbers of parameters that have to be processed fast.  Hence, the higher the CPU's clock-speed and the more RAM available, the better.  However, today's personal computers are capable of handling relatively large and complex optimization problems.  Furthermore, when constrained by a real 16-bit operating system - e.g. MSDOS (in short DOS) - a (hard) disk can compensate for RAM limitations; noting that its environment is limited to 640KB RAM, 8GB disk space and 2GB file size.   A Simplex algorithm running under DOS[1] can therefore handle efficiently no more than 3276 constraints and requires a minimum 256KB of RAM and 1GB free disk space.  Nonetheless, also larger problems can be handled, but with (much) less efficiency.  Furthermore, by utilizing unused SVGA video memory some RAM limitations can be overcome.

Large optimization problems require many computations and algorithmic iterations, often resulting in large errors and unreliable solutions.  To overcome this difficulty (up to a certain degree) extended precision arithmetic can be used internally.  Even under DOS limitations, large optimization problems can be successfully handled by using internally defined high precision numbers[2].   The allowed number of constraints is then reduced, accordingly.  For example, using internally 256-bit-mantissa FP numbers (e.g. 256 bit mantissa, 31 bit exponent and 1 bit for the sign) the number of constraints may not exceed 720.






[1]   The computer program _Simplex, written by the author, solves linear optimization problems using the Simplex Method.  It runs with DOS as well as with Windows operating systems.  Coded in Assembly (MASM 5.10), it can be readily called by higher level x86/87 computer programs.   The only interface needed, is a far pointer (DS:DX) to the ASCIIZ file name containing the input data, as described in the file structure above.  The results are returned in a newly created file SMPLX.RES, in the current directory.

[2]   The computer program _Simplex256 uses internally 256-bit mantissa virtual FP registers.   It is similar to _Simplex[1], but more reliable for large optimization problems - and much slower.  It is useful when large computational errors are anticipated as well as to verify results from other solvers.




Copyright D. Baruth © 2009. All rights reserved