A Modified Centered Climbing Algorithm for Linear Programming ()

Ming-Fang Ding, Yanqun Liu, John Anthony Gear

School of Mathematical & Geospatial Sciences, RMIT University, Melbourne, Australia.

**DOI: **10.4236/am.2012.330200
PDF
HTML
4,200
Downloads
6,952
Views
Citations

School of Mathematical & Geospatial Sciences, RMIT University, Melbourne, Australia.

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.

Share and Cite:

Ding, M. , Liu, Y. and Gear, J. (2012) A Modified Centered Climbing Algorithm for Linear Programming. *Applied Mathematics*, **3**, 1423-1429. doi: 10.4236/am.2012.330200.

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_{1}; c_{2}; ···; c_{n}] 4-7400957\1689c1db-d8d3-4ff7-891a-97880431f62a.jpg width=16.8150007247925 height=16.8150007247925 />R^{n} (c ≠ 0), and b = [b_{1}; b_{2}; ···; 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_{0}. 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_{1} – x_{2} – ··· – 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_{1} + x_{2} + ··· + 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_{1}, s_{2}, s_{3} ≥ 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^{n} – 1 = 2^{3} – 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_{1} + x_{2} + x_{3} ≤ 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

4-7400957\f7573d5a-091c-4e8c-b8cb-58e7cb456a6e.jpg width=914.755023193359 height=531.430023193359 />4-7400957\9bc5e0f6-ad4a-4193-a242-43a9ea0d158f.jpg width=913.994976806641 height=440.42000579834 />

Table 1. The tableau obtained from simplex for Example 1.

4-7400957\dbfee550-069d-4c94-817c-bc0b952f7ae3.jpg width=913.994976806641 height=177.07999420166 />

Table 2. The table obtained from MCCA for Example 1.

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.

4-7400957\eabc7f04-36fb-479a-925f-bd34d761b902.jpg width=437.28498840332 height=352.45 />

Table 3. Average CPU time (in seconds) for test problems in Example 2 (m = 2n).

4-7400957\eeb235ed-3fa2-45d3-958d-5464e175e0f0.jpg width=438.14001159668 height=327.275 />

Table 4. Average CPU time (in seconds) for test problems in Example 2 (m – n = 100).

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.

Conflicts of Interest

The authors declare no conflicts of interest.

[1] | G. B. Dantzig, “Linear Programming and Extensions,” Princeton University Press, Princeton, 1963. |

[2] | N. Karmarkar, “A New Polynomial-time Algorithm for Linear Programming,” Combinatorica, Vol. 4, No. 4, 1984, pp. 373-395. doi:10.1145/800057.808695 |

[3] | K. G. Murty and Y. Fathi, “A Feasible Direction Method for Linear Programming,” Operations Research Letters, Vol. 3, No. 3, 1984, pp. 121-127. doi:10.1016/0167-6377(84)90003-8 |

[4] | L. G. Khachian, “A Polynomial Algorithm in Linear Programming,” Soviet Mathematics Doklady, Vol. 20, 1979, pp. 191-194. |

[5] | Y. Liu, “An Exterior Point Linear Programming Method Based on Inclusive Normal Cones,” Journal of Industrial and Management Optimization, Vol. 6, No. 4, 2010, pp. 825-846. doi:10.3934/jimo.2010.6.825 |

[6] | M.-F. Ding, Y. Liu and J. A. Gear, “An Improved Targeted Climbing Algorithm for Linear Programs,” Numerical Algebra, Control and Optimization (NACO), Vol. 1, No. 3, 2011, pp. 399-405. doi:10.3934/naco.2011.1.399 |

[7] | R. J. Vanderbei, “Linear Programming: Foundations and Extensions,” 3rd Edition, Springer, New York, 2008. |

[8] | V. Klee and G. J. Minty, “How Good Is the Simplex Algorithm?” In: O. Shisha, Ed., Inequalities III, Academic Press, New York, 1972, pp. 159-175. |

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2024 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.