链接：https://pan.baidu.com/s/1o_6QHyXKZ3Y4fpKRFO4dWQ 

提取码：28ch 

 

. Introduction

In general a linear program (LP) has an optimal solution if and only if the primal problem

and the corresponding dual problem is feasible and in this case the optimal value of the two

problems coincide. This implies if a primal and dual solution is computed and reported,

then optimality of the primal solution can easily be verified by checking whether the primal

and dual solution is feasible and the duality gap is zero. Hence, the optimal dual solution is

a certificate of the optimality of the primal solution. In practice this also implies that it is

easy for an user of an LP software to verify the correctness of the solution produced by the

software.

Similarly, in the case an LP is primal or dual infeasible, then a certificate should be

reported which allows easy verification of the infeasible status of the LP.

The reader may question why optimization software should return a certificate of the

infeasible status and not just a status indicator which indicates that the problem is infea￾sible. One reason is optimization software may produce incorrect results, so it advanta￾geous to be able to check the software. Moreover, if for example the LP is a subproblem

arising within a column generation based solution method for large-scale LPs, then a

certificate is required to generate more columns or to prove that the “real” problem is

infeasible.

Hence, a certificate of the infeasible status may be important for both theoretical and

practical reasons.

172 ANDERSEN

Recently interior-point methods have emerged as an efficient alternative to simplex based

solution methods for LPs. Unfortunately some of these methods such as the primal-dual

algorithm discussed in [6] do not handle primal or dual infeasible LPs very well [6, p. 177].

However, interior-point methods based on the homogeneous model (or equivalently the self￾dual embedding) detects a possible infeasible status both in theory and practice [1, 5]. These

interior-point methods generates an infeasibility certificate using Farkas’s lemma. This leads

to the question about the relation between an “interior-point” certificate of infeasibility and

the certificate of infeasibility generated by the simplex method. Moreover, in the case an

optimal interior-point solution is known, then it is possible to compute an optimal basic

solution in strongly polynomial time [3]. However, is it also possible given an “interior￾point” certificate of infeasibility to compute a basis certificate of infeasibility?

The computation of a basis certificate of infeasibility starting from an arbitrary certificate

of infeasibility may not only be relevant for interior-point methods. For instance when an

LP is solved using the primal simplex method, then in the case the LP is primal infeasible an

optimal basis to a phase 1 problem is computed and reported. The optimal basic solution is

a certificate of the primal infeasibility, but unfortunately a phase 1 problem is not uniquely

defined [4, ch. 8]. Hence, it may be difficult to verify the conclusion of the certificate.

However, if such a certificate could easily be converted to a basis certificate of infeasibility

(to be defined precisely later), then a well defined certificate could always be reported.

The outline of the paper is as follows. First in Section 2 we present our notation. In

Section 3 we discuss primal infeasible LPs and give a definition of an optimal basis to an

infeasible LP. Moreover, by generalizing previous work in [2, 3] we show that such a basis

can be computed in strongly polynomial time given a Farkas type certificate of infeasibility.

In Section 4 we analyze dual infeasible problems. In Section 5 we discuss the usefulness

of computing a basis certificate of infeasibility and finally in Section 6 we present our

conclusions.

2. Notation and theory

The problem of study is an LP in standard form

(P) minimize cTx

subject to Ax = b, x ≥ 0,

where b ∈ Rm, A ∈ Rm×n, and c, x ∈ Rn. For convenience and without loss of generality

we assume that rank (A) = m. The dual problem corresponding to (P) is

(D) maximize bTy

subject to ATy + s = c, s ≥ 0,

where y ∈ Rm and s ∈ Rn. (P) is said to be feasible if a solution satisfying the constraints

of (P) exists. Similarly (D) is said to be feasible if (D) has at least one solution satisfying

the constraints of (D). The following lemma is a well-known fact of linear programming.

LINEAR PROGRAMMING 173

Lemma 2.1.

a. (P) has an optimal solution if and only if (x∗, y∗,s∗) exists such that

Ax∗ = b, AT y∗ + s∗ = c, cT x∗ = bT y∗, x∗,s∗ ≥ 0.

b. (P) is infeasible if and only if an y∗ exists such that

AT y∗ ≤ 0, bT y∗ > 0. (1)

c. (D) is infeasible if and only if an x∗ exists such that

Ax∗ = 0, cT x∗ < 0, x∗ ≥ 0. (2)

Proof: See [5]. ✷

Hence, (P) has an optimal solution if and only if (P) and (D) are both feasible. Moreover, a

primal and dual optimal solution is a certificate of that the problem has an optimal solution.

In the case the problem is primal or dual infeasible, then any y∗ satisfying (1) and any x∗

satisfying (2) is a certificate of the primal and dual infeasible status respectively.

An LP may be both primal and dual infeasible and in that case both a certificate for the

primal and dual infeasibility exists.

Note that the statements b and c in Lemma 2.1 are nothing but Farkas’s lemma. Also note

that in the case an LP is solved using a column generation method and for example the first

subproblem is infeasible, then any column having a positive inner product with a certificate

y∗ of primal infeasibility is a potential candidate to be included in the next subproblem. If

no such column exists, then the complete problem can be concluded to be infeasible.

Furthermore, by using the so-called homogeneous model and an interior-point algorithm

combined with a finite termination method then either an optimal solution or an infeasibility

certificate can be computed in polynomial time, see [7, pp. 159–167, 5]. However, in the case

the problem is both primal and dual infeasible then this method is only guaranteed to compute

one of the primal and dual infeasibility certificates.

Given the assumption A is of full row rank, then a basic partition of the indices of the

variables denoted (B, N ) satisfying

|B| = m and rank (B) = m

always exists where we use the definition that

B := A:B and N := A:N ·

Also B is denoted the basis.

An optimal basic partition of the indices of the variables is defined by

xB = B−1b ≥ 0, xN = 0, (3)

and

y = B−T (cB − sB), sB = 0, s = c − AT y ≥ 0. (4)

174 ANDERSEN

Subsequently we say a basic partition of the indices of the variables is primal feasible if

it satisfies (3), where the requirement xN = 0 may be relaxed to xN ≥ 0. Similarly, a basic

partition of the indices of the variables is dual feasible if it satisfies (4) possible with sB = 0

relaxed to sB ≥ 0.

It has been proved in [3] that given any primal and dual optimal solution, then an optimal

basic partition of the indices of the variables can be computed in strongly polynomial time.

However, in the case (P) is primal or dual infeasible, then it is undefined what constitutes

an “optimal” basic partition of the indices of the variables. Furthermore, given a definition

of an optimal basic partition of the indices of the variables to an infeasible LP, then it is

unclear whether such a basis can be computed in strongly polynomial time starting from an

arbitrary certificate of the infeasible status.

In the subsequent two sections we will give a definition of an optimal basic partition

of the indices of the variables for a primal and dual infeasible LP. Moreover, we will

present a strongly polynomial procedure to compute such a basic partition starting from

any infeasibility certificate.