ABSTRACT

In this paper, we propose a modified centered climbing algorithm (MCCA) for linear programs, which improves the centered climbing algorithm (CCA) developed for linear programs recently. MCCA implements a specific climbing scheme where a violated constraint is probed by means of the centered vector used by CCA. Computational comparison is made with CCA and the simplex method. Numerical tests show that, on average CPU time, MCCA runs faster than both CCA and the simplex method in terms of tested problems. In addition, a simple initialization technique is introduced.

1. Introduction

In the last decades a variety of algorithms have been proposed for solving linear programming (LP) problems (see, e.g., [1-5]). However, so far there hasn’t been an available single best LP algorithm which is suitable for solving all types of LP problems. Considerable research is still under way to find a faster LP algorithm.

Recently, a ladder method was developed in [5] for solving general LP problems. In this method, the inclusive normal cone is updated at each iteration by climbing in the associated inclusive region (ladder) until the problem is solved. A climbing rule used to update the inclusive normal cone is of crucial importance, directly determining the performance of a ladder algorithm. The climbing rule involves picking up a violated constraint and dropping a constraint from the current inclusive cone. Ladder algorithms applying various climbing rules were proposed in [5,6]. In this paper, we present a new ladder algorithm called “the Modified Centered Climbing Algorithm (MCCA)”, where a specific climbing rule is employed by means of the centered vector used by CCA [5]. At each iteration, a violated constraint is selected whose associated outer normal vector forms the minimum angle with the centered vector. Computational results show that, the proposed ladder algorithm has surprising superiority to CCA as well as the simplex method in terms of average CPU time for randomly generated test problems. In addition, the single artificial constraint technique is presented to initialize the ladder method for a certain class of LP problems.

The paper is organized as follows. In the remaining of this section, for the sake of readability, we introduce concepts used in the ladder method. A new ladder algorithm is proposed in Section 2, followed by an initialization technique of the ladder method in Section 3. In Section 4, a specific example is provided to illustrate effectiveness of the new algorithm. We report computational results in Section 5, followed by a brief conclusion in Section 6.

Consider the following linear programming problem:

(P):                                                             4-7400957\422ab33b-8e3d-4c60-8007-d192a7503881.jpg width=76.380001449585 height=31.919998550415  />

                                                                4-7400957\707d31a3-928b-4799-a6bf-6433d1bdcf54.jpg width=94.8100028991699 height=28.5  />

where 4-7400957\54285a31-7d0b-4a54-b163-8d9ca4ef6b9a.jpg width=55.3849992752075 height=28.5  /> is decision variables, 4-7400957\f4eb486a-cc5f-4fcd-a7fd-640a6ad7a7f7.jpg width=73.8149971008301 height=26.8849992752075  />with m ≥ n, c = [c₁; c₂; ···; c_n] 4-7400957\1689c1db-d8d3-4ff7-891a-97880431f62a.jpg width=16.8150007247925 height=16.8150007247925  />Rⁿ (c ≠ 0), and b = [b₁; b₂; ···; b_m] 4-7400957\fa4d3d78-99c5-47d7-923f-af3e40bd102f.jpg width=16.8150007247925 height=16.8150007247925  />R^m. Here, square brackets with entries separated by semi-colons indicate column vectors. Throughout the paper, we assume that rank(A) = n.

We denote the constraint index set {1, 2, ···, m} by4-7400957\7046c2bc-356a-4cf2-a58b-3fe9f9bbd6cd.jpg width=16.8150007247925 height=22.7049996376038  />. Let J be an ordered subset of4-7400957\e2d66dcb-0780-4986-900e-919f776a8521.jpg width=16.8150007247925 height=22.7049996376038  />. Denote by J(i ↔ j) the ordered subset with i-th entry of J replaced by4-7400957\8470e439-8be3-4d88-8be1-40ad967774d4.jpg width=66.3100028991699 height=28.5  />. The j-th row of A is denoted by a_j. We denote by A(J) the k × n submatrix with its j-th row as the i_j-th row of A. Also, denote by b(J) the k-vector with j-th element of b(J) as the i_j-th element of b. In addition, 4-7400957\bfce35d2-5a29-405f-9ae0-023ef0e786c4.jpg width=22.7049996376038 height=31.919998550415  />denotes the Euclidean norm.

Before proceeding, we present the following definitions developed in [5], which will be used in this paper.

Definition 1 [5] Consider problem (P). Let 4-7400957\ddfd8fbb-cea8-4b14-8d3e-f31780119f83.jpg width=174.61000289917 height=31.919998550415  /> be an ordered subset. A convex cone generated by n linearly independent vectors4-7400957\9da34c6b-f976-4b62-b902-ed533c1a5865.jpg width=115.805001449585 height=37.8099992752075  />, where 4-7400957\d906aef8-c784-44c0-94e2-f320bc2b7753.jpg width=108.3 height=36.1  /> are rows of A, is said to be an inclusive normal cone generated by J if it contains the vector –c, where c is the objective vector. The generated cone is denoted by N(J). If J generates an inclusive cone, the set defined by

4-7400957\507387b9-c6b7-47d5-897e-4fa9e8c4b3e4.jpg width=285.37999420166 height=36.1  />

is called the inclusive region or the ladder associated with J. The corresponding ordered index set J is called the generator of L(J), and the unique solution of A(J)x = b(J), denoted by x_J, is called the base point of the ladder L(J).

According to Theorem 2.2 in [5], problem (P) has an optimal solution (if an optimal solution exists) if and only if it has a feasible base point. A feasible base point is exactly an optimal solution.

Definition 2 [5] A ladder L(J) of problem (P) is said to be degenerate if at least one of its n edges is normal to the objective vector c. Problem (P) is said to be nondegenerate if it does not have a degenerate ladder.

Throughout the paper, we assume that problem (P) is non-degenerate since it is shown in [5] that the degenerate case can be readily treated by imposing an appropriate perturbation on the objective function of the original problem without affecting the optimal solution of the original problem. On the basis of the above assumption, we give the following ladder algorithm.

2. The Modified Centered Climbing Algorithm (MCCA)

Step 0 Initialization.

Start with a known ladder generator, which is denoted by 4-7400957\91e89863-132b-4d4e-8fa0-2ca0d2d2ce35.jpg width=188.00499420166 height=36.1  /> (Refer to [5] or the subsequent section for how to find such a generator if it is not immediately available). Denote by 4-7400957\514648db-b36b-4cfe-9330-47764aa9e47a.jpg width=68.780001449585 height=37.8099992752075  /> the base point associated with J₀. Calculate the initial base point

4-7400957\a7391709-194a-4fa2-a9ae-0b91f8fe497d.jpg width=172.9 height=40.280001449585  />.

Set k = 0 and4-7400957\0dbada91-6d72-4060-b8c1-6de750693888.jpg width=76.380001449585 height=28.5  />.

Step 1 Check optimality.

Let4-7400957\f4c8b886-50af-48ad-91ee-de77586228d0.jpg width=282.81501159668 height=40.280001449585  />.

• If4-7400957\b4b79094-5cdd-4d6c-a41c-e5ef29be10f7.jpg width=64.6 height=28.5  />, exit with “the problem attains optimality”.

• Otherwise, go to Step 2.

Step 2 Updating the ladder.

2.1 Picking up a new index as a pick.

Let           4-7400957\16879f2e-119b-4ab2-bd83-28e7e2e76088.jpg width=171.18999710083 height=41.9900007247925  />where4-7400957\cb9cf4b8-ccb6-4447-885b-c6cdf2bba7c9.jpg width=163.68500289917 height=34.3900007247925  />, and 4-7400957\5712a0e1-1321-427c-adc4-a604b4e30292.jpg width=30.2099992752075 height=34.3900007247925  /> is the center vector of the current ladder L(J_k) [5]. Select 4-7400957\13fc0153-1874-489d-af58-3f735aeda118.jpg width=66.3100028991699 height=31.919998550415  /> as a pick such that

4-7400957\ca10b802-2d45-41a3-97ce-d8e6c3f2670d.jpg width=115.805001449585 height=43.605001449585  />where

4-7400957\38f3c17d-13fc-46e1-86c2-554c834ab7c4.jpg width=88.919998550415 height=66.3100028991699 /> (1)

2.2 Try to find an index 4-7400957\c6932b95-2e2c-4f82-ba49-0f82215752cb.jpg width=62.9850028991699 height=31.919998550415  /> as a drop such that 4-7400957\5f908443-b6b0-497e-b9b0-0bd33cb0da61.jpg width=163.68500289917 height=36.1  /> is a ladder generator and the associated base point 4-7400957\e332e6bd-9a34-44cd-91e8-2039aee0ab7e.jpg width=104.880001449585 height=34.3900007247925  /> (See Procedure 2 in [5] for how to identify).

• If such an index does not exist, exit with “the problem is infeasible”.

• Otherwise, go to next step.

2.3 Let 4-7400957\89f7977c-abc8-4eb3-9428-af720b4872d0.jpg width=163.68500289917 height=36.1  /> and4-7400957\1800e163-cf30-4e50-959f-6d7833eaba5c.jpg width=83.8850028991699 height=36.1  />. Calculate the updated base point

4-7400957\2ce8c3e4-ce33-4388-8c83-cfa54e2f1c4a.jpg width=209 height=40.280001449585  />.

Set4-7400957\ab45be9b-5f7f-48ee-abb4-ba1e28323c7e.jpg width=73.8149971008301 height=24.3200003623962  />. Go to Step 1.

Note that existence of an initial ladder (generator) implies that the case of unboundedness can not occur (Refer to Theorem 2.5 (d) in [5] for details). Step 2.1 constitutes the main difference with respect to the previous ladder algorithms. At each iteration, a violated constraint is selected as a pick whose associated outer normal vector forms the minimum angle with the centered vector. Before numerically examining its efficiency, we would like to introduce the single artificial constraint technique to construct an initial ladder for a certain class of LP problems.

3. Finding an Initial Ladder for LP Problems with Bounded Variables

An initial ladder is required to get the ladder algorithm started. To find a ladder L(J) is to find the associated generator4-7400957\b7c96601-efd8-4ac3-a35d-821fe22f9870.jpg width=174.61000289917 height=31.919998550415  />, equivalently, to find n independent outward normals 4-7400957\2b82372b-1130-42f5-8f4d-9bb5a638c2ee.jpg width=30.2099992752075 height=34.3900007247925  /> (k = 1, 2, ···, n) such that there exist n constants 4-7400957\fab9cfdf-6c3b-466b-aefd-449d96a98ac6.jpg width=66.3100028991699 height=34.3900007247925  /> (k = 1, 2, ···, n) satisfying

4-7400957\5d75ebef-0f95-4183-9065-2f3ef5330074.jpg width=138.51000289917 height=40.280001449585  />

Various approaches were developed in [5] to obtain an initial ladder. In the following, we present an initialization technique for LP problems involving bounded variables.

3.1. Variables with Upper Bounds

In this subsection, we consider the case where variables of problem (P) have upper bounds. Temporarily, we assume that at least one component of c is positive. For convenience of discussion, write the problem as below:

(P1) 4-7400957\b54a22db-4a59-4d33-9096-1464f922712f.jpg width=288.70499420166 height=28.5 />

4-7400957\a420edc2-8c36-40d6-a61c-6b83081f3d62.jpg width=254.31501159668 height=28.5  />

4-7400957\77122b4f-770e-42d8-9e33-7051ef41dade.jpg width=224.10499420166 height=28.5  />

4-7400957\2bbf5320-dc44-462d-8d7b-d594c9f7b44d.jpg width=22.7049996376038 height=15.1049996376038  />

4-7400957\c4bb195d-a2b1-4830-b89d-49911a0c19ac.jpg width=334.02000579834 height=34.3900007247925  />

4-7400957\75416636-c016-4a4b-9c6d-4243c38c8a79.jpg width=83.8850028991699 height=28.5  />

4-7400957\6dea3a79-534e-495e-b5ae-7350964bffda.jpg width=87.305001449585 height=28.5  />

4-7400957\49fbbd60-c6b5-4997-966c-396716a859a1.jpg width=22.7049996376038 height=15.1049996376038  />

4-7400957\098e4a8d-72de-4059-ac86-d0c19d3faebe.jpg width=91.4850028991699 height=28.5  />

4-7400957\205287be-f8f4-44ea-bee2-f18366fde6b6.jpg width=22.7049996376038 height=15.1049996376038  />

4-7400957\6e00b09a-b88f-4ec7-b384-a4b4596ef24c.jpg width=60.419998550415 height=28.5  />

With this assumption that c contains at least one positive component, it is easily seen that the index set {m – n + 1, m – n + 2, ···, m – n + d, ···, m} is not a ladder generator. In order to obtain a ladder for the above problem, we add an artificial constraint

4-7400957\90ef8c61-9c70-407c-a4dc-095efe8f46ab.jpg width=109.91499710083 height=36.1  />where M is a sufficiently large number. For clarity, display the problem with the additional constraint as below:

4-7400957\eeb32f38-ff6c-4bc5-a6d8-be460896c65d.jpg width=300.48498840332 height=31.919998550415  />

4-7400957\60378923-f36b-42fa-b84c-74d68d8e7fb7.jpg width=255.17000579834 height=31.919998550415  />

4-7400957\d6de1b02-ff07-492d-8b42-bd3e56393f4d.jpg width=224.10499420166 height=31.0650007247925  />

4-7400957\405aea99-6f98-4579-9495-4eec9d12b4d8.jpg width=22.7049996376038 height=15.1049996376038  />

4-7400957\a1084752-c9bc-482c-a460-827271f80999.jpg width=334.02000579834 height=34.3900007247925  />

4-7400957\a0795d4d-309b-414a-8c24-910bb2310de5.jpg width=83.8850028991699 height=28.5  />

4-7400957\ea87dafb-14c9-4878-880a-f89befde3fd9.jpg width=87.305001449585 height=28.5  />

4-7400957\828da613-8c57-4701-8b62-cee9c2998ecd.jpg width=22.7049996376038 height=15.1049996376038  />

4-7400957\85849e1d-6fce-4359-a257-45509755e929.jpg width=91.4850028991699 height=28.5  />

4-7400957\1a0e61de-40f0-46a8-99a4-010494bf7fe4.jpg width=22.7049996376038 height=15.1049996376038  />

4-7400957\6da92523-6401-4ace-944e-308de5a7e82d.jpg width=60.419998550415 height=28.5  />

4-7400957\579355a0-9462-4818-9089-f57cbec54ffe.jpg width=172.9 height=28.5  />

Executing the following simple procedure, we can readily find an initial ladder for the above problem. At start, take J = {m – n + 1, m – n + 2, ···, m – n + d, ···, m}. Let c_d = max{c_i} > 0 (1 ≤ d ≤ n). Take j = m – n + d as a drop (the associated constraint is –x_d ≤ b_{m – n + d}) and p = m + 1 a pick (the associated constraint is –x₁ – x₂ – ··· – x_n ≤ M). It is easy to verify that J(j ↔ p) is a ladder generator of the above problem. Indeed, from

4-7400957\2be9b259-4a62-4826-a78d-b585329e5e55.jpg width=410.4 height=229.99500579834  />

we have

4-7400957\66c56f16-d233-4782-9b44-1648cbcb24ee.jpg width=281.2 height=31.919998550415  />

which implies J(j ↔ p) is a ladder generator of the above problem.

3.2. Variables with Lower Bounds

In this subsection, we consider the case where variables of problem (P) have lower bounds. For convenience of discussion, we rewrite the problem in the following form:

(P2) 4-7400957\52a08243-e8be-4e56-b666-52e0535d3929.jpg width=290.41501159668 height=28.5 />

4-7400957\f558f84c-60a0-4ccb-a4ae-de56a83dc395.jpg width=254.31501159668 height=28.5  />

4-7400957\ae21c643-b6f2-416c-a9f2-40c1556d9a40.jpg width=224.10499420166 height=28.5  />

4-7400957\5552b99e-31d2-4345-a2f8-ed741bcc3344.jpg width=22.7049996376038 height=15.1049996376038  />

4-7400957\6babdb2c-fa2f-46fa-add9-fe21daa3b9d9.jpg width=334.02000579834 height=34.3900007247925  />

4-7400957\0a38cfdd-6b4c-42a7-b827-ebdf717ee93b.jpg width=94.8100028991699 height=28.5  />

4-7400957\d0fff6a0-a5a1-48ef-beca-da37243f62f4.jpg width=98.9899971008301 height=28.5  />

4-7400957\224bc79c-6291-4ade-80ac-1b3cbc6cab49.jpg width=22.7049996376038 height=15.1049996376038  />

4-7400957\9a5d6c13-5938-4b84-97e9-591df7428fa2.jpg width=102.41000289917 height=28.5  />

4-7400957\0bcd7225-05dc-42ba-87ed-356bed330802.jpg width=22.7049996376038 height=15.1049996376038  />

4-7400957\ab067640-be00-4f30-9d6b-fd0763b877c5.jpg width=72.2 height=28.5  />

Note that here we use the same notations in problem (P2) as in (P1) for convenience. In this subsection, we temporarily assume that c contains at least one negative component. With this assumption, it is easy to be seen that the index set {m – n + 1, m – n + 2, ···, m – n + d, ···, m} is not a ladder generator. Adding an artificial constraint4-7400957\39006e14-dfdc-41f3-b306-0b767e928cf1.jpg width=98.9899971008301 height=36.1  />, we get the following system:

4-7400957\70750b62-a62f-46b1-92fc-226e48692726.jpg width=290.41501159668 height=28.5  />

4-7400957\35ae2ad3-3007-42f5-bcca-99daa82c4a5c.jpg width=254.31501159668 height=28.5  />

4-7400957\3dc5a578-6568-4af4-b342-fd4f6d809014.jpg width=224.10499420166 height=28.5  />

4-7400957\9280b929-6645-4a25-b98f-050e235ad91a.jpg width=22.7049996376038 height=15.1049996376038  />

4-7400957\d0282c17-eadb-41b9-a575-7ab41b3a5ade.jpg width=334.02000579834 height=34.3900007247925  />

4-7400957\46c26d0a-7a2d-4fc8-b498-7c8ddba8582b.jpg width=94.8100028991699 height=28.5  />

4-7400957\2311e4ee-3b55-4f8f-addf-487d2bb7f4bc.jpg width=98.9899971008301 height=28.5  />

4-7400957\2e6e1f76-6f7e-4957-afdd-ceb999f91e8d.jpg width=22.7049996376038 height=15.1049996376038  />

4-7400957\636fa2b6-625f-47d8-9a2c-e50d3e791e1b.jpg width=102.41000289917 height=28.5  />

4-7400957\164df5b4-10fb-4651-a9e1-5f30088cbd9a.jpg width=22.7049996376038 height=15.1049996376038  />

4-7400957\9159af69-ea72-4021-9c3b-08fc37dc7e66.jpg width=72.2 height=28.5  />

4-7400957\8507fa13-c4b1-4c70-97a0-a3fd1af1be54.jpg width=163.68500289917 height=28.5  />

Performing the similar procedure as the above subsection, we can easily obtain an initial ladder for the above problem. Initially, take J = {m – n + 1, m – n + 2, ···, m – n + d, ···, m}. Let c_d = min{c_i} < 0 (1 ≤ d ≤ n). Take j = m – n + d as a drop (the associated constraint is –x_d ≤ b_m–n+d) and p = m + 1 as a pick (the associated constraint is x₁ + x₂ + ··· + x_n ≤ M). It is easy to verify that J(j ↔ p) is a ladder generator of the above problem. In fact, from

4-7400957\5b094cde-cf1c-4fed-9ba2-311a2c7bb8cd.jpg width=419.61501159668 height=229.99500579834  />

we have

4-7400957\3915e184-8900-448c-9482-65b5ef61df98.jpg width=303.80998840332 height=31.919998550415  />

which implies J(j ↔ p) is a ladder generator of the above problem.

If variables in an LP problem are bounded from both below and above, that is, an LP problem contains n constraints taking the form of l_i ≤ x_i ≤ u_i (1 ≤ i ≤ n), where l_i and u_i denote the lower and upper bounds of x_i and l_i < u_i, then after rewriting the above constraints as two constraints –x_i ≤−l_i and x_i ≤ u_i we can follow the procedure in either Subsection 3.1 or Subsection 3.2 to obtain an initial ladder for the problem.

4. A Specific Example

To illustrate the efficiency of the above ladder algorithm, we use both the simplex method and MCCA to solve a Klee-Minty problem [7,8].

Example 1 Consider the following Klee-Minty problem with n = 3

4-7400957\92511a97-bd1c-487b-8bd2-09fc051317a5.jpg width=186.29500579834 height=28.5  />

4-7400957\0cb536b5-495a-4cd4-864d-c89a558aff4a.jpg width=79.705001449585 height=28.5  />

4-7400957\087924b4-5311-41fe-ae1c-f26c7a7b7cab.jpg width=121.69500579834 height=28.5  />

4-7400957\ad4e2541-213b-46c5-9abb-c0bc820bfcf5.jpg width=210.61499710083 height=28.5  />

4-7400957\7a5c1497-878c-40ce-858e-ee60ed19cc09.jpg width=104.880001449585 height=28.5  />

On the one hand, we use the simplex method to solve the above problem. Introducing the slack variables s₁, s₂, s₃ ≥ 0, write the above problem as the standard form

4-7400957\03b94364-8474-4ce6-8642-d42399d3c32a.jpg width=186.29500579834 height=28.5  />

4-7400957\48906bcf-21e3-4e60-85f8-2f76145928d0.jpg width=109.91499710083 height=28.5  />

4-7400957\09695648-327f-40f9-af32-1a641d0096e2.jpg width=156.08500289917 height=28.5  />

4-7400957\87b5e33d-cffe-4819-9f60-956b61ae79d5.jpg width=249.27999420166 height=28.5  />

4-7400957\786d2213-9adc-444e-b5dd-ad66e739d61c.jpg width=168.72000579834 height=28.5  />

The tableau in Table 1 shows that the simplex method with the most negative rule requires 2ⁿ – 1 = 2³ – 1 = 7 iterations to attain the optimality.

On the other hand, we solve the same problem using MCCA. Firstly we rewrite all constraints as ≤–type:

4-7400957\79ce968e-7bc9-4f26-bd50-6b13787d469a.jpg width=186.29500579834 height=28.5  />

4-7400957\37280f1c-65be-430c-aa08-a474242c809a.jpg width=79.705001449585 height=28.5  />

4-7400957\e6953594-6e2d-4e03-9718-9d34d9fc65dd.jpg width=121.69500579834 height=28.5  />

4-7400957\3964edcd-5349-48c4-afe4-92563a65f48c.jpg width=210.61499710083 height=28.5  />

4-7400957\a7102940-184f-4090-8d89-3a7a1e85e999.jpg width=62.9850028991699 height=28.5  />

4-7400957\70e593ad-1c63-41cf-b581-4a3b4f48df4b.jpg width=64.6 height=28.5  />

4-7400957\c696d076-2435-4911-9255-1396d2aaaa0c.jpg width=62.9850028991699 height=28.5  />

To find an initial ladder, we add an artificial constraint x₁ + x₂ + x₃ ≤ M. For clarity, write the problem with the additional constraint as below.

4-7400957\766823f8-a48d-44bd-a478-89949b82e777.jpg width=186.29500579834 height=28.5  />

4-7400957\8ae3a284-c443-4ec5-aec2-716813662549.jpg width=79.705001449585 height=28.5  />

4-7400957\45613a38-d3b6-42d3-a868-e28574428f37.jpg width=121.69500579834 height=28.5  />

4-7400957\0082b492-cc41-4e08-8676-e5df6d9cd9ac.jpg width=203.11000289917 height=28.5  />

4-7400957\314877f0-b771-488c-a59c-52299e568453.jpg width=62.9850028991699 height=28.5  />

4-7400957\185ff558-83b6-42d1-b7c2-f0cb7f9056ac.jpg width=64.6 height=28.5  />

4-7400957\af819514-e328-45c2-9e00-f9838c62ed64.jpg width=62.9850028991699 height=28.5  />

4-7400957\97eeb534-bc87-4da7-9a57-1d1110d08e70.jpg width=129.2 height=28.5  />

It is easy to verify that the index set {7, 5, 6} is an initial ladder generator (see Subsection 3.2). With the known ladder generator at hand, it takes only two iterations to reach an optimal solution for MCCA. For solution detail, see Table 2.

Clearly MCCA is much more efficient for solving the above Klee-Minty problem. Firstly, our algorithm requires no additional variables (slack, surplus and artificial variables). Secondly, the number of iterations is reduced greatly. In addition, we would like to stress that

although here we use an example with non-negativity variables to illustrate the efficiency of our algorithm, there is no non-negativity requirement for variables in our problem form. Thus, our algorithm is suitable for a wider range of LP problems.

5. Numerical Tests

In this section, we make computational tests to demonstrate the efficiency of MCCA. The ladder algorithms were coded in MATLAB 7.11.0. Test problems are randomly generated in the same way as in [5], which is presented as below.

Example 2 [5] (Randomly generated feasible problem) Generate a linear programming problem by specifying4-7400957\beeff2f5-31df-4333-bce6-2c86c0352b89.jpg width=73.8149971008301 height=26.8849992752075  />, 4-7400957\d593d2ff-5de9-4643-876f-8a0addc09c20.jpg width=171.18999710083 height=34.3900007247925  />, and 4-7400957\e5a93f4b-8932-4cbb-87e1-026de2ba1dbc.jpg width=177.07999420166 height=34.3900007247925  /> in the following method.

1. Randomly generate 4-7400957\d1213469-8533-418a-8ca5-11d9a79a601e.jpg width=55.3849992752075 height=28.5  /> and a vector 4-7400957\53261f74-0095-4a8e-89dd-febb5f7ee8ec.jpg width=57.094998550415 height=28.5  /> such that components of c take values between –25 and 25, and components of 4-7400957\089f9759-6582-4946-9b59-a36fd9477fc4.jpg width=19.2849992752075 height=22.7049996376038  /> between 0 and 20.

2. Generate A and b by two steps.

(a) For 1 ≤ j ≤ n, the j-th row a_j of A is4-7400957\5f2fd506-5135-4582-be7b-fc82ebd18d8a.jpg width=182.11499710083 height=36.1  />, where e_j is the j-th row of the n × n identity matrix. Then, b_j is defined by4-7400957\59d0e9d6-bf2d-4199-8fc2-ec135a8fb900.jpg width=104.880001449585 height=30.2099992752075  />, where γ_j is a random number in (0, 1).

(b) For n + 1 ≤ j ≤ m, randomly generate a row vector 4-7400957\8b5fde50-f41f-4e72-97b5-5166c5280edb.jpg width=66.3100028991699 height=34.3900007247925  /> and a number 4-7400957\14475d29-9cef-4b69-8263-879e1cc2c8df.jpg width=58.7099992752075 height=30.2099992752075  /> such that β_j and all the components of α_j are between –25 and 25. If4-7400957\e5c72e53-f0d7-4b96-9118-472f09a01a35.jpg width=73.8149971008301 height=30.2099992752075  />, then the j-th row a_j of A and the j-th element of b are defined by a_j = α_j, b_j = β_j. Otherwise, they are defined by a_j = −α_j, b_j = −β_j.

Tests were run on a desk-top computer (HP Intel(R) Core(TM), i7-2600 CPU@3.40GHz, 3.39GHz, 3.24GB of RAM) under Microsoft Windows XP operating system. For comparison, the centered climbing algorithm (CCA) [5] and the linprog solver in MATLAB optimization toolbox (Version 5.1, (R2010b)) were used for solving the same test problems. The medium-scale simplex algorithm (SP) was implemented. Tables 3 and 4 present computational results for 20 test problems with various dimensions. The average CPU time is reported in seconds. Since our algorithm and the simplex method actually work on problems with different forms and dimensions, the number of iterations does not provide much helpful information. Therefore, here we do not take the comparison of iteration numbers into account.

Tables 3 and 4 reveal that, MCCA has the absolute advantage over CCA as well as the simplex method for tested problems. We would like to point out that in the present code we adopt the traditional technique of the inverse of matrix to calculate base points. If the advanced numerical technique was incorporated into the current code, the computational performance would promise further improvement.

6. Conclusion

A new ladder algorithm, termed “the Modified Centered Climbing Algorithm”, was proposed in this paper. Computational results demonstrated that the ladder algorithm outperforms CCA as well as the simplex algorithm in terms of average CPU time for randomly generated test problems. In addition, the single artificial constraint technique was presented to initialize the ladder method for LP problems with bounded variables. An illustration showed that this initialization technique is intuitive and simple.

REFERENCES