579

INTRODUCTION

Manypracticalproblemsgiverisetosystemsoflinear

inequalitiesas



Ax b  (1)

inwhichtheinequalitiesarecomponentwise,i.e.







ij j i

Ax b, i 1,...,m (2)

where

A  is the (i, j) element of

 

mxn

 and







1im

. Also, let

A ,



A  denote the

transposeandtheMoore‐PenrosepseudoinverseofA,

respectively.



, willstandfortheEuclidean

scalarproductandnorm.

If(1)isconsistent,manyclassesofefficientsolvers,

mostly iterative ones, have been designed for its

numerical solution (see for a good overview the

monograph[3]).Intheinconsistentcaseof(1),forany





x  itexistsatleastoneindex



i 1,...,m  such

that the i‐th inequality in (2) is violated, i.e. the set









I x 1,...,m

,definedby













 

I x i 1,...,m , A ,x b  (3)

is non‐empty for any

x  . Moreover, let us

supposethattheset









I x i ,...,i  isorderedsuch

that





12 p

ii i, then,

 

Ix Ix

A,b will denote the

submatrix of A with the rows

A ,...,A  and the

subvector of b with components

b ,...,b ,

respectively. For any vector

 

y  we define



 

y  by









y max y ,0 , and the convex sets

by





  

iii

Cx ,A,xb,i 1,...,m . The

Regularized Han-type Algorithms for Inconsistent

Maritime Container Transportation Problems

D.Carp

ConstantaMaritimeUniversity,Romania

C.Popa&C.Şerban

OvidiusUniversityofConstanta,Romania



ABSTRACT:InthispaperweanalyseseveralwaystocomputetheweightsfromtheRegularizedHan(RH)

algorithm, the regularized version of Han’s algorithm for approximating the least squares solutions of

inconsistent (incompatible) systems of linear inequalities. We tested our approaches on a classical

transportation problem, aiming to provide a cost optimized solution to real world transportation problems,

whichoftenareunbalancedandinconsistent.



http://www.transnav.eu

the International Journal

on Marine Navigation

and Safety of Sea Transportation

Volume 8

Number 4

December 2014

DOI:10.12716/1001.08.04.13

580

inconsistency of the system (1) is equivalent to





C0,andwereformulateitina“leastsquares

sense”as(seee.g.[5]):find





x  suchthat







fx minfx,x  (4)

with

 





fx Ax b



Thefollowingresultsareprovedalsoin[5].

Proposition1.

(i) The objective function f from (4) is continuously

differentiable,convexand(seealso(3))

  

  







 

Ix Ix Ix

fx AAxb A A xb  (5)

(ii) Thereexists(atleast)aleastsquaressolutionof

(1).

(iii) Avector

 

x  of(1)ifandonlyif

  







*T*

fx A Ax b 0 (6)

The paper is organized as follows: in sections 2

and 3 we present Han’s original algorithm for

inconsistent systems of linear inequalities and the

Regularized version of it, respectively. Section 4

presents the characteristics of a classical

transportation problem and the way it can be

modelled so that the

Han‐type algorithms can be

appliedon.Section5isdedicatedtothemethodswe

usedforchoosingthebestweightsoftheRegularized

Hanalgorithm,thenumericalexperimentsbeingdone

over an unbalanced and inconsistent transportation

problem.

HAN‐TYPEALGORITHMFORINCONSISTENT

SYSTEMSOFLINEARINEQUALITIES

S.P. Han proposed in [5] the following iterative

algorithmforapproximatingaleastsquaressolution

ofthesystem(1):

AlgorithmH.

Let  

x  beaninitialdatum;for k 0,1,...  do:

Step 1. Find





IIx and compute  

d  as

the (unique) minimal norm solution of the linear

equalitiesleastsquaresproblem



 

kkk

III

Ad b Ax min! (7)

Step 2. Compute



 

 as the smallest minimizer

ofthefunction









  





fx d ,  (8)

Step3.Set







k1 k k k

xx d

Theexistenceofthesmallerminimizerfortheconvex

functionfrom(8)wasprovedin[5]andaprocedure

tofinditwasgivenin[1].

Theorem1.

(i) Let







x  be the sequence generated by

algorithm

Hfromany





x .Then,







fx 0,for

a



k  or











limf x 0 .

(ii) For any m x n matrix A, any right‐hand side

 

b  and any initial datum  

x , Han’s

algorithm

Hproducesaleastsquaressolutionofthe

system (1) in a finite number of steps (in exact

arithmetic).

REGULARIZEDHAN(RH)ALGORITHM

The Regularized Han algorithmwas introduced in

[10]andthoroughlystudiedin[9].In[10]theauthor

comments on Han’s algorithm by considering its

major drawback in the fact that, in each iteration,

initialobjectivefunctionfrom(4)isreplacedby

 



 

kk k

fx Ax b Ax b

.

In this way, many originally satisfied constraints

might be violated in the new iterative solution

.

Regarding this aspect, he also proposed to use the

complement of the set

I , denoted by

J  and

characterizedby













 

kii

J J x i 1,...,m ,A x b  (9)

together with a diagonal weights matrix









kkk

k1qi

W diag w ,...,w ,w 0 , where

q  is the

numberofelementsintheset



J, k 0

.Withthese

ideas he designed the Regularized version of Han’s

algorithmfrombelow.

AlgorithmRH.

Let





 beaninitialdatum;for

k 0,1,...

 do:

Step 1. Find







IIx,





JJx as before and

compute







d  the minimal norm solution of the

(regularized)linearleastsquaresproblem



  

kkk k

III kJ

Ad b Ax WAd min!

 (10)

Step2.Compute







 asthesmallestminimizerof

thefunction

581



  

 





fx d ,  (11)

Step3.Set









k1 k k k

xx d.

Theorem2.

Let  

x  be arbitrary fixed, and





x  the

sequencegeneratedbythealgorithm

RH.Then,either

it exists



k0 such that







fx 0, or









limf x 0 .

THETRANSPORTATIONPROBLEM

Aclassicaltransportationproblemimpliesfindingthe

minimumcostof transportingcertainquantitiesofa

single type of commodity from a given number of

loading ports (sources) to a given number of

unloadingports(destinations).

At each source







i 1,...,n

S , supplies





s 1,...,n 

ofsomegoodsareavailable,andateachdestination







1,...,m

D  some demands





d1,...,m

 are

requested. Table 1 illustrates the classical

transportation problem,





 



i 1,...,n ,j 1,...,m

c  being the

costsofshippingoneunitofcommodityfromsource

S  todestination

D .

Table1.Theclassicaltransportationproblem

_______________________________________________

D1  D2  D3 … DmSupply(s)

_______________________________________________

S1c11  c12  c13 … c1ms1

S2c21  c22  c23 … c2ms2

……  …  … … ……

ncn1  cn2  cn3 … cnms n

_______________________________________________

Demand(d) d1  d2  d3 … dm

_______________________________________________



If we denote by 

x,i 1,...,n,j 1,...,m  the

number of units transported from source

S  to

destination

D , we get the following mathematical

modelofthe(classical)transportationproblem:





ij ij

i1j1

min c x  (12)







ij j

s.t. x d ,j 1,...,m  (*)







ij i

xs,i 1,...,n  (**)

 

x0,i 1,...,n,j 1,...,m. 

Remark1.

Some arguments for the relations (*)‐(**) are as

follows:



for(*):ateachdestination,thedemandhasto be

”at least” satisfied (e.g. the construction of a

buildingwillnotbestarted if we do not have at

leastaminimalamountofmaterials)



for(**):allavailableunitsmustbesupplied.

Theproblemiscalled

balancedifthetotalsupply

equals the total demand (i.e.







i1 j1

sd) and

unbalanced otherwise. In the balanced case or the

unbalancedonewith







i1 j1

sd,thelinearprogram

(12)isconsistentandwellknownmethods(including

Simplex‐type algorithms) are available (see [4]). We

willconsiderinthispapertheunbalancedcase







i1 j1

sd (13)

for which the linear program (12) becomes

inconsistent.

Let us suppose that there exist 7 sources of

containers

S ,...,S  and7warehouses

D ,...,D .

Wewillconsidertheunbalancedandinconsistent

transportationproblem

PdescribedinTable2.

Table2.Theunbalancedtransportationproblem(P)

_______________________________________________

D1 D2 D3 D4 D5 D6 D7 Supply(s)

_______________________________________________

S13 3 4 12 20 5 9 1050

27 1 5 3 6 8 4 350

35 4 7 6 5 12 3 470

44 5 14 10 9 8 7 600

58 2 12 9 8 4 2 600

66 1 8 7 2 3 1 480

79 10 6 8 7 6 5 450

_______________________________________________

Demand(d) 455 320 540 460 760 830 780

_______________________________________________



Afterapplyingaseriesofrefinements(see[2]),we

canwritetheproblem

Pasthelinearprogram

min c,y s.t.By d,y0 (14)

withthecorrespondingdualproblemgivenby





max d,u s.t.Bu c,u0 (15)

In [2] we also proved a result that gives us the

possibilitytoexpressinanequivalentwaytheprimal‐

dual pair of linear programs (14‐15) as the linear

systemofinequalities(1)where



























































A,b

 (16)

So,insteadofsolvingthelinearprograms(14‐15),

onecouldsolvethesystem(1)byapplyingtheHan‐

typealgorithms.

582

COMPUTINGTHEREGULARIZATION

PARAMETERS

The success of Regularized Han algorithm depends

on making a good choice of the weights





kkkk

1qi

w w ,...,w ,w0. In the literature,

w  are

called the regularization parameters. Hence, one

question that can occur related to Regularized Han

algorithmis:howcanwecomputetheregularization

parameters

w  so that the RH algorithm preserves

itspropertiesgivenbyTheorem2?In[10],theauthor

only remarks that we can impose the appropriate

penalties when

x  approaches





Hj,Axb

byassigningalargerweight

w  forj‐thequationif

thecurrentiterativesolutionisclosetotheboundary

H ,andasmallerweightifisfaraway.Takingthese

remarksintoconsideration,weanalysedseveralways

forchoosinggoodregularizationparameters,ourgoal

beingtocomputeagoodestimateofthesolutionto1.

Wetestedthemethodsontheinconsistentproblem

P

describedinsection4,knowingthatforthisproblem,

theminimalcostsolutionis15336,obtainedwithHan

algorithm. Both algorithms,

H and RH, were

implemented in Matlab R2010a, using the built‐in

Matlabfunctionpinvtocomputethedirection(Step1

of the algorithms), all runs being started with the

initial datum





xy,0 with



 and being

terminated if at the current iterations

x  satisfy







AAx b  AT(Axk−b)+i.

Thefirstmethodconsidered(

M1)triestoseteach



w,j 1,...,q  according to 

Ax b . We can

implementitunderthe

M1

 fork=0,1,...do





hAxb



forj=1,…,

 do

if



h10

then





else





w10

Table3.Thecostsolutionofproblem(P)

_______________________________________________

HanRHwithM1

_______________________________________________

1533615981

_______________________________________________



Next,wetooksomefixedweightsateachstepk, 

bysettingeach 

w,j 1,...,q  equalto 

Ax b 

M2

 fork=0,1,...do







w , j 1,...,q

Ax b



Table4.Thecostsolutionofproblem(P)

_______________________________________________

HanRHwithM1

_______________________________________________

1533616257

_______________________________________________



The third method considered uses fixed weights

forallstepsk

M3





w 10 , k, j 1,...,q



Table5.Thecostsolutionofproblem(P)

_______________________________________________

HanRHwithM1

_______________________________________________

1533616113

_______________________________________________



Analysing (10), we observe that we can make an

analogybetweentheRegularizedHanalgorithmand

TikhonovRegularization.



II k

Ad r d min! (17)

with



kk k

III

rbAx and 

kkJ

WA . The most

popular method used to find the regularization

parameter of a Tikhonov Regularization is the L‐

curveapproach.AnL‐curveisdefinedby









log Lx ,log Ax b , 0 

and the L‐curve method selects the regularization

parameterasthecorner ofL‐curve,i.e. thepointof

maximumcurvature(seefordetails[6]).



For implementation, we used Hansen’s

Regularization Tools package ([7]) to compute the

cornerofL‐curvefor(10).

M4

 fork=0,1,...do

lcorner=l_curve(U,S,rz’,Tikh’,L,V)





wlcorner, j 1,...,q



583

where

[U,S,V] = csvd(

A ) where ‘csvd’ stands for

CompactSVD: 

Irrr

AUSV



rz b A x 



LIA

Table6.Thecostsolutionofproblem(P)

_______________________________________________

HanRHwithM1

_______________________________________________

1533624703

_______________________________________________



AfterimplementingM4onproblemP,wenoticed

thatanadjustmentisneedtobemade.

M5

 fork=0,1,...do

lcorner=l_curve(U,S,rz’,Tikh’,L,V)





wlcorner, j 1,...,q 







iflcorner 10 thenlcorner 10 





wlcorner, j 1,...,q



Table7.Thecostsolutionofproblem(P)

_______________________________________________

HanRHwithM1

_______________________________________________

1533615336

_______________________________________________



REFERENCES

[1]Carp,D.,Popa,C.&SerbanC.2013.Iterativesolutionof

inconsistent systems of linear inequalities, Proceedings

on Applied Mathematics and Mechanics (PAMM), 13,

DOI10.1002/pamm.201310199,407–408.

[2]Carp, D., Popa, C. & Serban C. 2014. Modifed Han

algorithm for maritime containers transportation

problem, ROMAI Journal, v.10, no.1, ISSN 1841

‐5512,

ISSNOnline2065‐7714,11–23

[3]Censor, Y. & Stavros, A.Z. 1997. Parallel optimization:

theory,algorithmsandapplications, Numer.Math.and

Sci.Comp.Series,OxfordUniv.Press,NewYork

[4]Koopmans, T.C. &  Beckmann, M. 1957. Assignment

problems and location of economic activities,

Econometrica,Vol.25,No.1,53–76.

[5]

Han, S.‐P. 1980. Least squares solution of linear

inequalities,Tech.Rep.TR‐2141,MathematicsResearch

Center,UniversityofWisconsin‐Madison.

[6]Hansen, P. C. & O’LearyD. P. 1993. Theuse oftheL‐

curve in the regularization of discrete ill‐posed

problems,SIAMJ.Sci.Comput.,14,1487‐1503.



[7]Hansen, P. C. 1992. Regularization Tools, a Matlab

PackageforAnalysisandSolutionofDiscreteIll‐posed

Problems, Technical Report UNIC‐92‐03, Danish

Computing Center for Research and Education,

TechnicalUniversityofDenmark,(RevisedJuly2007).

[8]Popa,C.1998.Extensionsofblock‐projectionsmethods

with relaxation parameters

to inconsistent and rank‐

defficientleast‐squaresproblems,BIT,38(1),151–176.

[9]Popa, C. & Serban, C. 2014. Han‐ type algorithms for

inconsistent systems of linear inequalities‐a unifed

approach, Applied  Mathematics and Computation,

Volume 246, ISSN: 0096‐3003, DOI:10.1016/

j.amc.2014.08.018,247–256

[10]Yang, K. 1990. New iterative methods

 for linear

inequalities,Tech.report90‐6,DepartmentofIndustrial

and Operations Engineering, University of Michigan,

USA

