The goal of this page is to gather various examples of linear programming in Scilab. We focus here on continuous variables and do not cover integer programming. We consider dense matrices and do not cover sparse linear programs. We used the following functions :
- karmarkar, from Scilab v5.3.2,
- linpro, from the quapro module.
These examples must be used under the terms of the CeCILL.
Contents
-
Linear Programming Examples in Scilab
- The karmarkar function
- Changes in Scilab 5.3.1
- The quapro module
-
Example #1
- With karmarkar
- With linpro
-
Example #2
- With karmarkar
- With linpro
-
Example #3
- With karmarkar
- With linpro
-
Example #4
- With karmarkar
- With linpro
-
Example #5
- With karmarkar
- With linpro
-
Example #6
- With karmarkar
- With linpro
- Acknowledgments
-
Appendix
- Limitations of karmarkar before Scilab 5.3.1
- Feasibility problem
- Slack and positive variables
- An example of karmarkar for Scilab <= 5.3.0
- References
The karmarkar function
The karmarkar function is a linear programming solver. It is able to solve the linear program either in standard form:
ineqlin: [7x1 constant] eqlin: [0x0 constant] lower: [3x1 constant] upper: [3x1 constant] Minimize c'*x such that: Aeq*x = beq x >= 0
or in the more general form with linear inequalities and bounds:
Minimize c'*x such that: Aeq*x = beq A*x <= b lb <= x <= ub
The help of the karmarkar function is provided in Scilab:
http://www.scilab.org/product/man/karmarkar.html
Despite its name, the algorithm is not based on the Karmarkar algorithm, but on a primal affine-scaling interior point algorithm. This algorithm discovered by Dikin in 1967, and then re-discovered by Barnes and Vanderbei et al in 1986.
Changes in Scilab 5.3.1
In the version 5.3.1 of Scilab we improved the karmarkar linear optimization solver. The goal was to improve the usability, and to provide a much more flexible solver. The detailed changes are the following:
- User can configure an output function.
- The number of iterations can be put as an output argument.
- x0 can be put as an optional argument.
- Management of inequality constraints.
- Management of bounds.
- Computation of the exitflag.
- Computation of the Lagrange multipliers.
- Documentation provided for the rtolf and gam parameters.
- Documentation provided for the stopping rule.
- More examples provided.
There are also bugs which have been fixed:
- Bug # 7193 fixed — The karmarkar help page did not document the eps, gamma, and crit arguments.
- Bug # 8719 fixed — The karmarkar function printed unwanted messages.
- Bug # 8720 fixed — The karmarkar function stopped too early in the iterations.
- Bug # 8726 fixed — The karmarkar function produced a division-by-zero error.
- Bug # 8727 fixed — The karmarkar function required the initial guess x0.
- Bug # 8775 fixed — The karmarkar function did not detect unbounded problems.
The quapro module
http://atoms.scilab.org/toolboxes/quapro
The quapro module defines linear quadratic programming solvers. The matrices defining the cost and constraints must be full, but the quadratic term matrix is not required to be full rank.
The features of the quapro module are :
- linpro : linear programming solver
- mps2linpro : convert lp problem given in MPS format to linpro format
- quapro : linear quadratic programming solver
This module was created by Eduardo Casas Renteria, Cecilia Pola Mendez (Universidad De Cantabria), improved by Serge Steer (INRIA) and maintained by Allan Cornet, Michaël Baudin (Consortium Scilab — DIGITEO).
To install the quapro module :
atomsInstall("quapro");
and then re-start Scilab.
In this page, we will focus of the linpro function.
The linpro function can solve linear programs in general form:
Minimize c'*x A*x <= b Aeq*x = beq lb <= x <= ub
Example #1
The following problem is extracted from «Practical Optimization», Antoniou, Lu, 2007, Chapter 11, «Linear Programming Part I: The simplex method», Example 11.9, p. 361. This problem is solved by the primal affine scaling algorithm in Chapter 12, «Linear Programming Part II: Interior point methods», Example 12.2, p.382.
The program is the following.
Minimize 2.x1 + 9.x2 + 3.x3 Such as 2.x1 - 2.x2 - x3 <= -1 -x1 - 4.x2 + x3 <= -1 x >= 0
The solution is
xstar = [0 1/3 1/3]';
With karmarkar
The following script solves the problem with the karmarkar function.
A = [ 2 -2 -1 -1 -4 1 ]; b = [-1;-1]; c = [2;9;3]; lb = [0;0;0]; [xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb) yopt.ineqlin yopt.lower
This produces the following output.
-->[xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
yopt =
ineqlin: [2x1 constant]
eqlin: [0x0 constant]
lower: [3x1 constant]
upper: [3x1 constant]
iter =
70.
exitflag =
1.
fopt =
4.00004
xopt =
0.0000016
0.3333387
0.3333296
-->yopt.ineqlin
ans =
3.5
0.5
-->yopt.lower
ans =
8.5
2.560D-09
- 1.790D-09
With linpro
The following script solves the problem with the linpro function.
A = [ 2 -2 -1 -1 -4 1 ]; b = [-1;-1]; c = [2;9;3]; ci = [0;0;0]; cs = [%inf;%inf;%inf]; [xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
The previous script produces the following output.
-->[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
fopt =
4.
lagr =
- 8.5
0.
0.
3.5
0.5
xopt =
0.
0.3333333
0.3333333
Example #2
This example is extracted from «Operations Research: applications and algorithms», Wayne L. Winstons, Section 5.2, «The Computer and Sensitivity Analysis», in the «Degeneracy and Sensitivity Analysis» subsection.
The linear program is:
Maximize 6*x1 + 4*x2 + 3*x3 + 2*x4 such as: 2*x1 + 3*x2 + x3 + 2 *x4 <= 400 x1 + x2 + 2*x3 + x4 <= 150 2*x1 + x2 + x3 + 0.5*x4 <= 200 3*x1 + x2 + x4 <= 250 x >= 0
The solution is
xstar = [50;100;0;0]
With karmarkar
The following script solves the problem with the karmarkar function.
c = [-6 -4 -3 -2]';
A = [
2 3 1 2
1 1 2 1
2 1 1 0.5
3 1 0 1
];
b = [400 150 200 250]';
lb = [0;0;0;0];
[xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
The previous script produces the following output.
-->[xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
yopt =
ineqlin: [4x1 constant]
eqlin: [0x0 constant]
lower: [4x1 constant]
upper: [4x1 constant]
iter =
69.
exitflag =
1.
fopt =
- 699.99624
xopt =
50.000068
99.998479
0.0003436
0.0004409
With linpro
The following script allows to solve the problem with the linpro function.
c = [-6 -4 -3 -2]';
A = [
2 3 1 2
1 1 2 1
2 1 1 0.5
3 1 0 1
];
b = [400 150 200 250]';
ci=[0 0 0 0]';
cs=[%inf %inf %inf %inf]';
[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
This produces :
-->[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
fopt =
- 700.
lagr =
0.
0.
0.
- 1.5
0.5
1.25
0.
1.25
xopt =
50.
100.
2.842D-14
0.
Example #3
This example is extracted from «Operations Research: applications and algorithms», Wayne L. Winstons, Section 5.2, «The Computer and Sensitivity Analysis», from «Problems Group A, 1.».
We want to solve the linear program:
Maximize 150.x1+200.x2-10.x3
such as:
x1+ x2 <= 45
6.x1+10.x2 - x3 <=0
5.x1 <= 140
4.x2 <= 120
x3 <= 350
x >= 0
The solution is:
xstar = [25,20,350]
With karmarkar
The following script solves the problem with the karmarkar function.
c = [-150 -200 +10]';
A = [
1 1 0
6 10 -1
5 0 0
0 4 0
0 0 1
];
b = [45 0 140 120 350]';
lb = [0;0;0];
[xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
The previous script produces the following output.
-->[xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
yopt =
ineqlin: [5x1 constant]
eqlin: [0x0 constant]
lower: [3x1 constant]
upper: [3x1 constant]
iter =
89.
exitflag =
1.
fopt =
- 4249.9602
xopt =
25.00115
19.998673
349.99469
With linpro
The following script allows to solve the problem with the linpro function.
c = [-150 -200 +10]';
A = [
1 1 0
6 10 -1
5 0 0
0 4 0
0 0 1
];
b = [45 0 140 120 350]';
ci=[0 0 0]';
cs=[%inf %inf %inf]';
[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
This produces :
-->[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
fopt =
- 4250.
lagr =
0.
0.
0.
75.
12.5
0.
0.
2.5
xopt =
25.
20.
350.
Example #4
Consider the linear program:
Minimize -20.x1 - 24.x2 such as: 3.x1 + 6.x2 <= 60 4.x1 + 2.x2 <= 32 x >= 0
The solution is
xstar = [4;8];
With karmarkar
The following script solves the problem with the karmarkar function.
c = [-20 -24]'; A = [ 3 6 4 2 ]; b = [60 32]'; lb = [0;0]; [xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
The previous script produces the following output.
-->[xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
yopt =
ineqlin: [2x1 constant]
eqlin: [0x0 constant]
lower: [2x1 constant]
upper: [2x1 constant]
iter =
66.
exitflag =
1.
fopt =
- 271.99746
xopt =
3.9998866
7.9999887
With linpro
The following script allows to solve the problem with the linpro function.
c = [-20;-24]; A = [ 3 6 4 2 ]; b = [60;32]; ci=[0;0]; cs=[%inf;%inf]; [xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
This produces:
-->[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
fopt =
- 272.
lagr =
0.
0.
3.1111111
2.6666667
xopt =
4.
8.
Example #5
This example is from the Lipsol toolbox, by Yin Zhang, as ported into Scilab by Rubio Scola in example0.sce.
Minimize 2.x1 + 5.x2 - 2.5.x3 such as: x1 S4 x3 <= 5 E2 x1 - x2 - x3 <= 0 -2 <= x1 <= 2 1 <= x2 <= %inf 0 <= x3 <= 3
The solution is
xstar = [-2;1;3];
With karmarkar
The following script solves the problem with the karmarkar function.
S4 = sin(%pi/4)/4;
E2 = exp(2);
c = [ 2; 5; -2.5];
A = [
1 0 S4
E2 -1 -1
1 0 0
0 0 1
-1 0 0
0 -1 0
0 0 -1
];
b = [ 5; 0;2;3;2;-1;0];
lb = [-2;1;0];
ub = [2;%inf;3];
[xopt,fopt,exitflag,iter,yopt]=karmarkar([],[],c,[],[],[],[],[],A,b,lb,ub)
The previous script produces the following output.
-->[xopt,fopt,exitflag,iter,yopt]=karmarkar([],[],c,[],[],[],[],[],A,b,lb,ub)
yopt =
ineqlin: [7x1 constant]
eqlin: [0x0 constant]
lower: [3x1 constant]
upper: [3x1 constant]
iter =
75.
exitflag
1.
fopt =
- 6.4999498
xopt =
- 1.9999916
1.0000033
2.9999933
With linpro
The following script solves the problem with the linpro function.
S4 = sin(%pi/4)/4;
E2 = exp(2);
c = [ 2; 5; -2.5];
A = [
1 0 S4
E2 -1 -1
];
b = [ 5; 0];
ci = [-2;1;0];
cs = [2;%inf;3];
[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
The previous script produces the following output.
-->[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
fopt =
- 6.5
lagr =
- 2.
- 5.
2.5
0.
0.
xopt =
- 2.
1.
3.
Example #6
Minimize 600*x1 + 600*x2 + 600*x3 + 600*x4 + 600*x5 + 600*x6 + 600*x7 + 200*x8 + 200*x9 + 200*x10 + 200*x11 + 200*x12 + 200*x13 + 200*x14
such that
8*x1 + 8*x4 + 8*x5 + 8*x6 + 8*x7 + 4*x8 + 4*x11 + 4*x12 + 4*x13 + 4*x14 >= 88
8*x1 + 8*x2 + 8*x5 + 8*x6 + 8*x7 + 4*x8 + 4*x9 + 4*x12 + 4*x13 + 4*x14 >= 136
8*x1 + 8*x2 + 8*x3 + 8*x6 + 8*x7 + 4*x8 + 4*x9 + 4*x10 + 4*x13 + 4*x14 >= 104
8*x1 + 8*x2 + 8*x3 + 8*x4 + 8*x7 + 4*x8 + 4*x9 + 4*x10 + 4*x11 + 4*x14 >= 120
8*x1 + 8*x2 + 8*x3 + 8*x4 + 8*x5 + 4*x8 + 4*x9 + 4*x10 + 4*x11 + 4*x12 >= 152
8*x2 + 8*x3 + 8*x4 + 8*x5 + 8*x6 + 4*x9 + 4*x10 + 4*x11 + 4*x12 + 4*x13 >= 112
8*x3 + 8*x4 + 8*x5 + 8*x6 + 8*x7 + 4*x10 + 4*x11 + 4*x12 + 4*x13 + 4*x14 >= 128
- 20*x8 - 20*x9 - 20*x10 - 20*x11 - 20*x12 - 20*x13 - 20*x14 >= -840
xi >= 0 (i = 1,...,14)
There are several solutions to this problem, but all are associated with the objective function value:
fstar = 9200
With karmarkar
The following script solves the problem with the karmarkar function.
c = [600 600 600 600 600 600 600 200 200 200 200 200 200 200]';
A = [
8 0 0 8 8 8 8 4 0 0 4 4 4 4
8 8 0 0 8 8 8 4 4 0 0 4 4 4
8 8 8 0 0 8 8 4 4 4 0 0 4 4
8 8 8 8 0 0 8 4 4 4 4 0 0 4
8 8 8 8 8 0 0 4 4 4 4 4 0 0
0 8 8 8 8 8 0 0 4 4 4 4 4 0
0 0 8 8 8 8 8 0 0 4 4 4 4 4
0 0 0 0 0 0 0 -20 -20 -20 -20 -20 -20 -20
];
b = [88 136 104 120 152 112 128 -840]';
A = -A;
b = -b;
lb=zeros(14,1);
[xopt,fopt,exitflag,iter,yopt]=karmarkar([],[],c,[],[],[],[],[],A,b,lb)
The previous script produces the following output.
-->[xopt,fopt,exitflag,iter,yopt]=karmarkar([],[],c,[],[],[],[],[],A,b,lb)
yopt =
ineqlin: [8x1 constant]
eqlin: [0x0 constant]
lower: [14x1 constant]
upper: [14x1 constant]
iter =
68.
exitflag =
1.
fopt =
9200.0482
xopt =
0.2130791
0.2373697
0.2444532
0.1395045
0.2749702
0.0000344
0.2240255
4.7906317
6.9752061
8.1870869
1.7117333
14.116657
0.0000689
6.2185468
With linpro
c = [600 600 600 600 600 600 600 200 200 200 200 200 200 200]';
A = [
8 0 0 8 8 8 8 4 0 0 4 4 4 4
8 8 0 0 8 8 8 4 4 0 0 4 4 4
8 8 8 0 0 8 8 4 4 4 0 0 4 4
8 8 8 8 0 0 8 4 4 4 4 0 0 4
8 8 8 8 8 0 0 4 4 4 4 4 0 0
0 8 8 8 8 8 0 0 4 4 4 4 4 0
0 0 8 8 8 8 8 0 0 4 4 4 4 4
0 0 0 0 0 0 0 -20 -20 -20 -20 -20 -20 -20
];
A = -A;
b = [88 136 104 120 152 112 128 -840]';
b = -b;
[n,p]=size(A);
ci=zeros(p,1);
cs=%inf*ones(p,1);
[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
This produces
-->[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
fopt =
9200.
lagr =
0.
- 6.519D-15
- 6.355D-14
3.411D-13
- 5.084D-13
- 200.
0.
1.990D-13
0.
0.
0.
0.
- 100.
0.
3.038D-14
25.
0.
25.
25.
0.
25.
5.
xopt =
1.475D-15
1.872D-15
- 9.103D-16
0.
- 2.483D-16
1.448D-15
1.3333333
0.
12.666667
10.
0.6666667
14.666667
0.
4.
Acknowledgments
We thank Reinaldo Golmia Dante for providing the initial material for this document.
Appendix
Limitations of karmarkar before Scilab 5.3.1
Before Scilab 5.3.1, the karmarkar function required that we provide a strictly feasible initial guess. This is why the resolution required two steps:
- phase 1 : search for a feasible initial guess based on the resolution of a modified problem,
- phase 2 : resolution of the original problem.
Moreover, the only constraint which was taken into account was the linear equality constraint. This is why we had to introduce slack variables if we wanted to take into account linear inequalities such as A*x <= x.
The feasibility problem (phase 1) and the introduction of slack variables are described in the two next sections. These algorithms are now directly provided by Scilab 5.3.1, so that the user now implicitely use them, but does not have to explicitely call these functions.
Feasibility problem
In this section, we describe a method to find an initial guess x0 which is strictly feasible for a problem in standard form. This method is used by the karmarkar function since Scilab 5.3.1. The method that we present is classical and is presented for example in «A Primal-Dual Exterior Point Algorithm For Linear Programming Problems» by Samaras, Sifaleras, Triantafyllidis. Another version of the same idea was presented in «A modification of karmarkar’s linear programming algorithm» by Vanderbei et al.
Assume that we must solve the linear program:
Minimize c'*x such as: Aeq*x = beq x >= 0
In order to find a feasible point, we solve the following problem :
Minimize z(p+1) such as: AAeq * z = bbeq z >= 0
where
z=[x(1) x(2) ... x(p) x(p+1)].
The matrix AAeq has the same number of rows, but one column more than Aeq. The initial guess for the modified problem is
z0=[1 1 ... 1]'=e(n+1),
where e(n+1) represents a column vector of n+1 ones. The last column of AAeq is
beq-Aeq*e(n)
so that the initial guess z0 satisfies the equation
AAeq*z0=beq.
Then we solve the modified linear program. There are three main cases.
- If the feasibility problem has no solution, then the original problem has no solution.
-
If the feasibility problem has a solution and z(p+1)>0, this means that no strictly feasible point x0 can be found. In this case, the value of z(p+1) measures the smallest offset that must be added to the inequality constraint to create a feasible linear program.
- If the feasibility problem has a solution and z(p+1)=0, we have an initial guess x0 and can move on to the phase 2.
The following function uses the previous method to find a feasible initial guess x0.
function x0 = karmarkar_searchx0 (Aeq,beq,c,eps,gam) // Search a stricly feasible initial guess for the linear program // // Minimize c'*x // Aeq*x = b // x >= 0 // // Copyright (C) 2010 - DIGITEO - Michael Baudin // Must be used under the terms of the CeCILL V2: http://www.cecill.info [n,p]=size(Aeq) cc = [zeros(p,1);1] AAeq = [Aeq,beq-Aeq*ones(p,1)] bbeq = beq z0 = ones(p+1,1) zopt=karmarkar(AAeq,bbeq,cc,z0,eps,gam) x0=zopt(1:p) endfunction
Slack and positive variables
In this section, we show how to change the formulation of an optimization problem in order to manage bounds or linear inequalities. This method is used by the karmarkar function since Scilab 5.3.1.
In practice, we may have to solve linear programs which may not be in standard form. Instead, we may have to solve programs in the form:
Minimize c'*x A*x <= b
where A is a n-by-p matrix, b is a n-by-1 column vector and c is a p-by-1 column vector. We can introduce the slack variable s, as a n-by-1 column vector which satisfy the equality:
A*x + s = b.
We must have
s >= 0.
The equality constraint can be written as
[A I]*[x;s] = b.
From there, there are two cases, depending on the constraint on x:
- either x must be non-negative,
- or x is unrestricted.
In the case where the original problem has the additionnal constraint
x >= 0,
we are done. It now suffices to consider the variable z=[x;s] and to modify the linear cost to cc=[c;0], where the zero column vector has n entries.
In the case where the variable x is unrestricted, we can write it as the difference of two positive variables :
x = xp - xn
where xp and xn are both non-negative. This leads to the linear program:
Minimize c'*(xp-xn) A*(xp-xn) + s = b xp,xn,s >= 0
The previous program can be written in matrix form:
Minimize [c;-c;0]'*[xp;xn;s] [A,-A,I]*[xp;xn;s] = b xp,xn,s >= 0
The previous program is a linear program in standard form :
Minimize cc'*z Aeq*z = b z >= 0
where
cc = [c;-c;0] Aeq=[A,-A,I]
The following function applies the previous method to preprocess a linear program in general form.
function [Aeq,beq,cc] = karmarkar_preprocess ( A , b , c ) // Converts the linear program // // Minimize c'*x // A*x <= b // // into // // Minimize cc'*z // Aeq*z = beq // z >= 0 // // where x = z(1:p) - z(p+1:2*p). // // Copyright (C) 2010 - DIGITEO - Michael Baudin // Must be used under the terms of the CeCILL V2: http://www.cecill.info [n,p]=size(A) Aeq = [A -A eye(n,n)] beq = b cc = [c;-c;zeros(n,1)] endfunction
An example of karmarkar for Scilab <= 5.3.0
In this section, we present the resolution of a linear program with Scilab versions older than 5.3.1. This example is the example #1.
We introduce slack variables and get:
Minimize 2.x1 + 9.x2 + 3.x3 2.x1 - 2.x2 - x3 + x4 = -1 -x1 - 4.x2 + x3 + x5 = -1 x >= 0
The following script solves the problem. Here, the initial guess x0 is given.
Aeq = [ 2 -2 -1 1 0 -1 -4 1 0 1 ]; beq = [-1;-1]; c = [2;9;3;0;0]; x0 = [0.2;0.7;1;1;1]; xopt=karmarkar(Aeq,beq,c,x0)
This produces the following output.
-->xopt=karmarkar(Aeq,beq,c,x0)
1. 0.856E+01 0.117E+00
2. 0.765E+01 0.107E+00
3. 0.690E+01 0.977E-01
4. 0.629E+01 0.878E-01
5. 0.580E+01 0.776E-01
6. 0.541E+01 0.672E-01
7. 0.510E+01 0.571E-01
8. 0.486E+01 0.477E-01
9. 0.467E+01 0.394E-01
10. 0.452E+01 0.321E-01
[...]
36. 0.400E+01 0.278E-04
37. 0.400E+01 0.209E-04
38. 0.400E+01 0.156E-04
39. 0.400E+01 0.117E-04
40. 0.400E+01 0.880E-05
xopt =
0.0000041
0.3333474
0.3333235
0.0000101
0.0000704
Now, assume that the initial guess x0 is unknown.
We solve the feasibility problem by introducing one extra variable x(p+1). The following script solves the problem.
-->x0 = karmarkar_searchx0 (Aeq,beq,c,0,0.999)
1. 0.100E-02 0.999E+00
2. 0.100E-05 0.999E-03
3. 0.100E-08 0.999E-06
4. 0.100E-11 0.999E-09
5. 0.100E-14 0.999E-12
6. 0.100E-17 0.999E-15
7. 0.100E-20 0.999E-18
8. 0.100E-23 0.999E-21
9. 0.100E-26 0.999E-24
10. 0.100E-29 0.999E-27
11. 0.100E-32 0.999E-30
12. 0.100E-35 0.999E-33
13. 0.100E-38 0.999E-36
14. 0.100E-41 0.999E-39
[...]
53. 0.100-158 0.999-156
54. 0.100-161 0.999-159
55. 0.100-161 0.000E+00
x0 =
0.497293
0.7455296
1.3277695
0.8242427
1.1516418
The previous script allows to produces the initial guess:
x0 = [0.497293;0.7455296;1.3277695;0.8242427;1.1516418]
We now plug the initial guess x0 into the original problem and get:
-->xopt=karmarkar(Aeq,beq,c,x0,1.e-14,0.999)
1. 0.537E+01 0.541E+00
2. 0.417E+01 0.222E+00
3. 0.401E+01 0.402E-01
4. 0.400E+01 0.108E-02
5. 0.400E+01 0.195E-03
6. 0.400E+01 0.316E-04
7. 0.400E+01 0.101E-05
8. 0.400E+01 0.156E-06
9. 0.400E+01 0.244E-07
10. 0.400E+01 0.957E-09
11. 0.400E+01 0.130E-09
12. 0.400E+01 0.193E-10
13. 0.400E+01 0.899E-12
14. 0.400E+01 0.110E-12
15. 0.403E+01 0.155E-13
16. 0.403E+01 0.832E-15
xopt =
3.885D-19
0.3361047
0.3362025
1.059D-16
1.218D-16
References
- «Iterative solution of problems of linear and quadratic programming», Dikin, Doklady Akademii Nausk SSSR, Vol. 174, pp. 747-748, 1967
- «A New Polynomial Time Algorithm for Linear Programming», Narendra Karmarkar, Combinatorica, Vol 4, nr. 4, p. 373–395, 1984.
- «A variation on Karmarkar’s algorithm for solving linear programming problems, Earl R. Barnes, Mathematical Programming, Volume 36, Number 2, 174-182, 1986.
- «A modification of karmarkar’s linear programming algorithm», Robert J. Vanderbei, Marc S. Meketon and Barry A. Freedman, Algorithmica, Volume 1, Numbers 1-4, 395-407, 1986.
- «Practical Optimization: Algorithms and Engineering Applications», Andreas Antoniou, Wu-Sheng Lu, Springer, 2007, Chapter 12, «Linear Programming Part II: Interior Point Methods».
- «Global Convergence of a Long-Step Affine Scaling Algorithm for Degenerate Linear Programming Problems», Takashi Tsuchiya and Masakazu Muramatsu, SIAM J. Optim. Volume 5, Issue 3, pp. 525-551 (August 1995)
- «The convergence of dual variables», Dikin, Tech. report, Siberian Energy Institute, Russia, 1991
- «The Affine Scaling Algorithm Fails for Stepsize 0.999», Walter F. Mascarenhas, SIAM J. Optim. Volume 7, Issue 1, pp. 34-46 (1997)
- «A Primal-Dual Exterior Point Algorithm For Linear Programming Problems», Nikolaos Samaras, Angelo ifaleras, Charalampos Triantafyllidis, Yugoslav Journal of Operations Research, Vol 19 (2009), Number 1, 123-132
- «Operations Research: applications and algorithms», Wayne L. Winstons.
|
Fenlou 1 / 1 / 2 Регистрация: 11.03.2014 Сообщений: 483 |
||||||||
|
1 |
||||||||
|
27.04.2016, 20:51. Показов 13403. Ответов 4 Метки нет (Все метки)
Здравствуйте, помогите пожалуйста исправить ошибку при выполнении кода программы
ошибка
__________________ 0 |
|
Programming Эксперт 94731 / 64177 / 26122 Регистрация: 12.04.2006 Сообщений: 116,782 |
27.04.2016, 20:51 |
|
4 |
|
6514 / 4647 / 1932 Регистрация: 02.02.2014 Сообщений: 12,480 |
|
|
27.04.2016, 22:15 |
2 |
|
Решение1 |
Сообщение было отмечено Fenlou как решение
|
0 / 0 / 1 Регистрация: 17.03.2014 Сообщений: 10 |
|
|
20.02.2018, 23:40 |
3 |
|
необходимо загрузить Quapro Toolbox: 0 |
|
0 / 0 / 0 Регистрация: 23.12.2018 Сообщений: 47 |
|
|
01.05.2020, 15:15 |
4 |
|
JRmsk, я посмотрел, а там Quapro нет Добавлено через 28 секунд 0 |
|
6514 / 4647 / 1932 Регистрация: 02.02.2014 Сообщений: 12,480 |
|
|
01.05.2020, 15:24 |
5 |
|
SabLat, вы дату топика посмотрите Добавлено через 2 минуты 0 |
4 года прошло…У меня версия 5.1.1
Как указано в описании quapro 1.0 toolbox (windows 32 bits binary version):
1. Выполнил quapro-1.0-win32.exe и вопросное расширение инсталировалось в директорию
C:Program Filesquapro-toolbox-1.0;
2. В основной т.наз. Console scilab-a вошел в команде File >> Execute, нашел директории
C:Program Filesquapro-toolbox-1.0 с только что инсталированном расширении и там увидел,
выбрал и выполнил как указано «загрузчик» расширения loader.sce. В Consol-е пeрошли тексты:
Startup execution:
loading initial environment
Start quapro toolbox
Load macros
Load gateways
Load help
Execution done.
;
3. Теперь уже в Helpe scilab-a в самом конце наряду с прочими появилось расширение quapro. Там открыл
описание linpro. Из части его Examples скопировал «фирменный» примерчик прямо в Console и нажал Enter;
4. Получил решение
—>//Find x in R^6 such that:
—>//C1*x = b1 (3 equality constraints i.e me=3)
—>C1= [1,-1,1,0,3,1;
—> -1,0,-3,-4,5,6;
—> 2,5,3,0,1,0];
—>b1=[1;2;3];
—>//C2*x <= b2 (2 inequality constraints)
—>C2=[0,1,0,1,2,-1;
—> -1,0,2,1,1,0];
—>b2=[-1;2.5];
—>//with x between ci and cs:
—>ci=[-1000;-10000;0;-1000;-1000;-1000];cs=[10000;100;1.5;100;100;1000];
—>//and minimize p’*x with
—>p=[1;2;3;4;5;6]
p =
1.
2.
3.
4.
5.
6.
—>//No initial point is given: x0=’v’;
—>C=[C1;C2]; b=[b1;b2] ; me=3; x0=’v’;
—>[x,lagr,f]=linpro(p,C,b,ci,cs,me,x0)
f =
— 7706.4681
lagr =
0.
0.
— 3.1914894
— 7.4893617
2.212766
0.
— 0.7659574
— 0.8723404
— 0.5531915
0.
0.
x =
275.2766
— 129.51064
1.537D-14
-1000.
100.
— 703.78723
—>// Lower bound constraints 3 and 4 are active and upper bound
—>// constraint 5 is active —> lagr(3:4) < 0 and lagr(5) > 0.
—>// Linear (equality) constraints 1 to 3 are active —> lagr(7:9) <> 0
5. Последный пункт можно сделать и не прямо из Console, а через Applications >> Editor.
Скопировать примерчик в редактор программ и выполнить его уже оттуда при помощью команды
Execute >> Load into SciLab. Тогда в Console более лаконическое:
->
p =
1.
2.
3.
4.
5.
6.
f =
— 7706.4681
lagr =
0.
0.
— 3.1914894
— 7.4893617
2.212766
0.
— 0.7659574
— 0.8723404
— 0.5531915
0.
0.
x =
275.2766
— 129.51064
1.537D-14
-1000.
100.
— 703.78723
Все.
НавигацияВладельцы сайта |
Решение задач линейного программирования
|
У меня версия 5.1.1
Как указано в описании quapro 1.0 toolbox (windows 32 bits binary version):
1. Выполнил quapro-1.0-win32.exe и вопросное расширение инсталировалось в директорию
C:\Program Files\quapro-toolbox-1.0;
2. В основной т.наз. Console scilab-a вошел в команде File >> Execute, нашел директории
C:\Program Files\quapro-toolbox-1.0 с только что инсталированном расширении и там увидел,
выбрал и выполнил как указано «загрузчик» расширения loader.sce. В Consol-е пeрошли тексты:
Startup execution:
loading initial environment
Start quapro toolbox
Load macros
Load gateways
Load help
Execution done.
;
3. Теперь уже в Helpe scilab-a в самом конце наряду с прочими появилось расширение quapro. Там открыл
описание linpro. Из части его Examples скопировал «фирменный» примерчик прямо в Console и нажал Enter;
4. Получил решение
—>//Find x in R^6 such that:
—>//C1*x = b1 (3 equality constraints i.e me=3)
—>C1= [1,-1,1,0,3,1;
—> -1,0,-3,-4,5,6;
—> 2,5,3,0,1,0];
—>b1=[1;2;3];
—>//C2*x <= b2 (2 inequality constraints)
—>C2=[0,1,0,1,2,-1;
—> -1,0,2,1,1,0];
—>b2=[-1;2.5];
—>//with x between ci and cs:
—>ci=[-1000;-10000;0;-1000;-1000;-1000];cs=[10000;100;1.5;100;100;1000];
—>//and minimize p’*x with
—>p=[1;2;3;4;5;6]
p =
1.
2.
3.
4.
5.
6.
—>//No initial point is given: x0=’v’;
—>C=[C1;C2]; b=[b1;b2] ; me=3; x0=’v’;
—>[x,lagr,f]=linpro(p,C,b,ci,cs,me,x0)
f =
— 7706.4681
lagr =
0.
0.
— 3.1914894
— 7.4893617
2.212766
0.
— 0.7659574
— 0.8723404
— 0.5531915
0.
0.
x =
275.2766
— 129.51064
1.537D-14
-1000.
100.
— 703.78723
—>// Lower bound constraints 3 and 4 are active and upper bound
—>// constraint 5 is active —> lagr(3:4) < 0 and lagr(5) > 0.
—>// Linear (equality) constraints 1 to 3 are active —> lagr(7:9) <> 0
5. Последный пункт можно сделать и не прямо из Console, а через Applications >> Editor.
Скопировать примерчик в редактор программ и выполнить его уже оттуда при помощью команды
Execute >> Load into SciLab. Тогда в Console более лаконическое:
->
p =
1.
2.
3.
4.
5.
6.
f =
— 7706.4681
lagr =
0.
0.
— 3.1914894
— 7.4893617
2.212766
0.
— 0.7659574
— 0.8723404
— 0.5531915
0.
0.
x =
275.2766
— 129.51064
1.537D-14
-1000.
100.
— 703.78723
Все.
Описание
Эта страница представляет таблицу предопределённых сообщений об ошибках и присвоенных им
номерах. Некоторые из этих сообщений об ошибках используются в самой системе Scilab для
синтаксических ошибок или ошибок специальных встроенных функций. Некоторые из них являются
более общими и могут быть использованы в функциях Scilab. Сообщения об ошибках, помеченные
звёздочкой, предназначены для тех, чей синтаксис имеет вид error(n,pos).
1 «Некорректное присвоение.»
2 «Неправильный множитель.»
3 «Ожидание закрывающей скобки.»
4 «Неизвестная переменная: %s»
5 «Несогласованное количество столбцов или строк.»
6 «Несогласованное количество строк или столбцов.»
7 «Точка не может быть использована в качестве модификатора этого оператора.»
8 «Некорректное суммирование.»
9 «Некорректное вычитание.»
10 «Некорректное умножение.»
11 «Некорректное правое деление.»
12 «Некорректное левое деление.»
13 «Переопределение неизменной переменной.»
14 «Переменная единичной матрицы в данном контексте не определена.»
15 «Подматрица задана некорректно.»
16 «Некорректная команда!»
17 «достигнут предел размера стека! Используйте функцию stacksize для его увеличения.»
18 «Слишком много переменных!»
19 «Задача вырождена.»
(*) 20 «Неверный тип первого аргумента %d: ожидалась квадратная матрица.»
21 «Неправильный индекс.»
22 «Проблемы рекурсии. Извините…»
23 «Доступные матричные нормы: 1, 2, inf и fro.»
24 «Проблема сходимости…»
25 «Плохой вызов примитива: %s»
26 «Слишком сложная рекурсия! (заполнена таблица рекурсии)»
27 «Деление на нуль…»
28 «Пустая функция…»
29 «Матрица не является положительно определённой»
30 «Неправильный показатель степени.»
31 «Неправильная строка.»
32 «Особая точка функции log или tan.»
33 «Слишком много «:»»
34 «Неправильный синтаксис управляющей инструкции.»
34 «Ошибка синтаксиса в инструкции «select/case».»
(if,while,select/case)
(*) 36 «Неверный входной параметр %d.»
(*) 37 «Некорректная функция в строке %d.»
38 «Неправильное имя файла.»
39 «Неправильное количество входных аргументов.»
40 «Ожидание конца команды.»
41 «Несовместимый выходной параметр.»
42 «Несовместимый входной параметр.»
43 «Не реализовано в scilab…»
(*) 44 «Неверный параметр %d.»
(*) 45 «нулевая матрица (параметр №%d).»
46 «Некорректный синтаксис.»
47 » пропущен end или else…»
(*) 48 » входная строка длиннее размера буфера: %d»
49 «Некорректный файл или формат.»
50 «подпрограмма не найдена: %s»
51 Нет сообщения
(*) 52 «Неверный тип параметра %d: ожидалась матрица вещественных чисел.»
(*) 53 «Неверный тип входного параметра %d: ожидалась матрица вещественных или комплексных чисел.»
(*) 54 «Неверный тип входного параметра %d: ожидался полином.»
(*) 55 «Неверный тип параметра %d: ожидалась строка.»
(*) 56 «Неверный тип параметра %d: ожидался список.»
57 «Проблема с символом сравнения…»
58 «Неверное число входных параметров.»
59 «Неверное число выходных параметров.»
60 «Неверный размер параметра: размерности несовместимы.»
61 «Прямой доступ: задайте формат.»
(*) 62 «Конец файла в строке %d.»
(*) 63 «%d графический терминал?»
64 «Интегрирование не удалось.»
(*) 65 «%d: логический блок уже используется.»
66 «Открыто слишком много файлов!»
67 «Неизвестный формат файла.»
68 «Неустранимая ошибка!!! Ваши переменные сохранены в файле:
%s
Неверный вызов к функции scilab?
В противном случае отправьте отчёт об ошибке:http://bugzilla.scilab.org/»
69 «Исключение операции с плавающей точкой.»
70 «Слишком много параметров в fort (максимум 30).»
71 «Эта переменная некорректна в fort.»
72 «%s некорректна в этом контексте.»
73 «Ошибка связывания (linking).»
74 «Старший коэффициент равен нулю.»
75 «Слишком большая степень (максимум 100).»
(*) 76 «цикл for x=val для type(val)=%d не реализован в Scilab.»
77 «%s: Неверное количество входных параметров.»
78 «%s: Неверное количество выходных параметров.»
79 «Индексация недопустима для выходных параметров resume.»
80 «Некорректная функция (параметр n: %d).»
81 «%s: Неверный тип параметра %d: ожидалась матрица вещественных или комплексных чисел.»
82 «%s: Неверный тип параметра %d: ожидалась матрица вещественных чисел.»
83 «%s: Неверный тип параметра %d: ожидался вещественный вектор.»
84 «%s: Неверный тип параметра %d: ожидался скаляр.»
85 «Хост не отвечает…»
86 «Неконтролируемая система.»
87 «Ненаблюдаемая система.»
88 «sfact: вырожденная или асимметричная задача.»
(*) 89 «Неверный размер параметра %d.»
(*) 90 «Неверный тип параметра %d: ожидалась передаточная матрица.»
(*) 91 «Неверный тип параметра %d: ожидалась форма в пространстве состояний.»
(*) 92 «Неверный тип параметра %d: ожидалась рациональная матрица.»
(*) 93 «Неверный тип параметра %d: ожидалось в непрерывном времени.»
(*) 94 «Неверный тип параметра %d: ожидалось в дискретном времени.»
(*) 95 «Неверный тип параметра %d: Ожидалось SISO (один вход, один выход).»
(*) 96 «Временной интервал аргумента %d не задан.»
(*) 97 «Неверный тип параметра %d: ожидалась система в пространстве состояний или в форме передаточной матрицы.»
98 «Функция аргумента scilab вернула некорректную переменную.»
(*) 99 «Элементы %d-го параметра должны быть отсортированы по возрастанию.»
(*) 100 «Элементы %d-го параметра не являются непрерывно убывающими.»
(*) 101 «Последний элемент %d-го параметра не равен первому.»
102 «Переменной или функции %s нет в файле.»
103 «Переменная %s не является корректной рациональной функцией.»
104 «Переменная %s не является корректным представлением пространства состояний.»
105 «Неопределённая функция.»
106 «Имя функции уже используется.»
(*) 107 «Определено слишком много функций (максимум: %d).»
108 «Слишком сложно для scilab, возможно слишком длинная управляющая инструкция.»
109 «Слишком велико, невозможно отобразить.»
110 «%s была функцией во время компиляции, а теперь это примитив!»
111 «Попытка переопределить функцию %s.»
112 «Не осталось доступной памяти.»
113 «Слишком длинная строка.»
114 «Слишком много закрытых программ.»
115 «Внутри цикла обнаружена проблема со стеком.
Функция-примитив была вызвана с неверный количеством выходных параметров.
При этом для функции не была произведёна проверка выходных параметров.
Пожалуйста, сообщите об этой проблеме :
http://bugzilla.scilab.org/»
(*) 116 «Неверное значение параметра %d.»
(*) 117 «Элемент списка с номером %d не определён (Undefined).»
(*) 118 «Неверный тип параметра %d: ожидалась именованная переменная или выражение.»
120 «Индексы ненулевых элементов должны быть заданы в виде матрицы из двух столбцов..»
121 «Несовместимые индексы ненулевых элементов.»
(*) 122 «Номер логического блока должен быть больше %d.»
123 «Функция не ограничена снизу.»
125 «Возможно проблема ограничения: слишком большое расстояние между двумя последовательными итерациями.»
126 «Несовместимые ограничения.»
127 «Нет допустимых решений.»
128 «Вырожденная начальная точка.»
129 «Допустимых точек не найдено.»
130 «Оптимизация не удалась: возврат к исходному положению.»
131 «optim: Симулятор запросил остановку (ind=0)»
132 «optim: Неверные входные параметры.»
133 «Слишком мало памяти.»
134 «optim: Проблема с исходными константами симуляции (simul).»
135 «optim : Исходные значения не соответствуют граничным условиям.»
136 «optim : Данный метод не реализован.»
137 «Горячий перезапуск НЕ доступен в этом методе.»
138 «optim: Некорректные параметры остановки.»
139 «optim: Некорректные граничные условия.»
140 «Переменная: %s должна быть списком»
(*) 141 «Некорректная функция (параметр n: %d).»
(*) 142 «Горячий перезапуск: размерность рабочей таблицы (параметр n:%d).»
143 «optim: df0 должен быть положительным!»
144 «Операция для заданных операндов не определена.
отметьте или определите функцию %s как перегружаемую.»
145 to 200: No message
201 «%s: Неверный тип параметра %d: ожидалась матрица вещественных или комплексных чисел.»
202 «%s: Неверный тип параметра %d: ожидалась матрица вещественных чисел.»
203 «%s: Неверный тип параметра %d: ожидался вещественный вектор.»
(*) 204 «%s: Неверный тип параметра %d: ожидался скаляр.»
205 «%s: Неверный размер параметра %d: ожидался размер (%d,%d).»
206 «%s: Неверный размер параметра %d: ожидался размер %d.»
207 «%s: Неверный тип параметра %d: ожидалась матрица строк.»
208 «%s: Неверный тип параметра %d: ожидалась матрица логических значений.»
209 «%s: Неверный тип параметра %d: ожидалась матрица.»
210 «%s: Неверный тип параметра %d: ожидался список.»
211 «%s: Неверный тип параметра %d: ожидалась функция или строка (внешняя функция).»
212 «%s: Неверный тип параметра %d: Ожидался полином.»
213 «%s: Неверный тип параметра %d: ожидалась целочисленная рабочая матрица.»
214 «%s: Неверный тип параметра %d: ожидался вектор.»
(*) 215 «Тип %d-го параметра должен быть логическим.»
(*) 216 «Неверный тип параметра %d: ожидалось логическое значение или скаляр.»
(*) 217 «Неверный тип параметра %d: ожидалась разреженная числовая матрица.»
(*) 218 «Неверный тип параметра %d: ожидался дескриптор разреженных LU-множителей.»
(*) 219 «Неверный тип параметра %d: ожидалась полная или разреженная числовая матрица.»
220 «Здесь не может использоваться пустая переменная.»
221 «Элемент разреженной матрицы был задан двумя разными значениями.»
222 «%s пока не реализована для полных входных параметров.»
223 «Невозможно переопределить примитив %s таким способом (см. clearfun).»
224 «База данных типов заполнена.»
225 «Этот тип данных уже определён.»
226 «Сравнение неравенства с пустой матрицей.»
227 «Пропущен индекс.»
228 «ссылка на очищенную глобальную переменную %s.»
229 «Параметры команд / и \ не могут содержать NaN или Inf.»
230 «частичное определение не удалось.»
231 «Неверный тип первого входного параметра: ожидалась одиночная строка.»
232 «Имя входа не найдено.»
233 «Достигнут предел количества динамических интерфейсов.»
234 «link: ожидалось более одного параметра.»
235 «link: проблема с одной из точек входа.»
236 «link: разделяемый архив не было загружен.»
237 «link: В этой операционной системе допускается только одна точка входа.»
238 «link: Первый параметр не может быть числом.»
239 «Вы не можете связать больше функций, достигнуто значение maxentry.»
240 «Файл «%s» уже существует или нет доступа для записи в каталог.»
241 «Файл «%s» не существует или недоступен для чтения.»
242 «Двоичные файлы прямого доступа могут быть открыты только командой «file».»
243 «Здесь недопустим логический блок C-файла.»
244 «Здесь недопустим логический блок Fortran-файла.»
(*) 245 «С логическим блоком %d не ассоциирован входной файл.»
246 «Функция не определена для заданных типов параметров,
проверьте параметры или определите функцию %s как перегружаемую.»
247 «Неверное значение параметра %d: дескриптор LU более недействителен.»
(*) 248 «Неверное значение параметра %d: ожидалось корректное имя переменной.»
(*) 249 «Неверное значение параметра %d: ожидалась пустая строка.»
250 «Рекурсивное извлечение недопустимо в этом контексте.»
251 «bvode: должен иметь размер как минимум 11..»
252 «bvode: ltol должен соответствовать размеру ipar(4).»
253 «bvode: fixpnt должен соответствовать размеру ipar(11).»
254 «bvode: ожидалось ncomp < 20.»
255 «bvode: m должно соответствовать размеру ncomp.»
256 «bvode: sum(m) должно быть менее 40.»
257 «bvode: sum(m) должно быть менее 40.»
258 «bvode: ошибка во входных данных.»
259 «bvode: количество шагов разбиения не умещается в доступную память.»
260 «bvode: Матрица расположения вырождена.»
261 «Таблица свойств интерфейсов переполнена.»
(*) 262 «Слишком много глобальных переменных! Максимальное число не более %d.»
263 «Ошибка при записи в файл: диск полный или файл удалён.»
(*) 264 «Неверное значение параметра %d0: параметр не должен содержать NaN и Inf.»
265 «A и B должны иметь одинаковое количество строк.»
266 «A и B должны иметь одинаковое количество столбцов.»
267 «A и B должны иметь одинаковые размеры.»
(*) 268 «Неправильное значение возвращено функцией выполненной в качестве параметра %d.»
(*) 269 «Неверное значение параметра %d: собственные значения должны иметь отрицательные вещественные части.»
(*) 270 «Неверное значение параметра %d: модуль собственного значения должен быть меньше единицы.»
(*) 271 «Параметр переменной длины a*eye(), (параметр %d) здесь недопустим.»
272 «пропущено ключевое слово endfunction.»
273 «Левосторонняя инструкция: ожидается точка или открывающая скобка.»
274 «Левосторонняя инструкция: ожидается имя.»
275 «Ключевое слово varargout не может быть использовано здесь.»
276 «Пропущен оператор, запятая или точка с запятой.»
277 «Задано слишком много команд.»
278 «%s: Входные параметры должны иметь одинаковое имя формальной переменной.» или «Входные параметры должны иметь одинаковое имя формальной переменной.»
279, 280: Нет сообщений
 |
Пожалуйста, избегайте использования этого списка, поскольку он может измениться в будущем релизе. |
Примеры
The goal of this page is to gather various examples of linear programming in Scilab. We focus here on continuous variables and do not cover integer programming. We consider dense matrices and do not cover sparse linear programs. We used the following functions :
- karmarkar, from Scilab v5.3.2,
- linpro, from the quapro module.
These examples must be used under the terms of the CeCILL.
Contents
-
Linear Programming Examples in Scilab
- The karmarkar function
- Changes in Scilab 5.3.1
- The quapro module
-
Example #1
- With karmarkar
- With linpro
-
Example #2
- With karmarkar
- With linpro
-
Example #3
- With karmarkar
- With linpro
-
Example #4
- With karmarkar
- With linpro
-
Example #5
- With karmarkar
- With linpro
-
Example #6
- With karmarkar
- With linpro
- Acknowledgments
-
Appendix
- Limitations of karmarkar before Scilab 5.3.1
- Feasibility problem
- Slack and positive variables
- An example of karmarkar for Scilab <= 5.3.0
- References
The karmarkar function
The karmarkar function is a linear programming solver. It is able to solve the linear program either in standard form:
ineqlin: [7x1 constant] eqlin: [0x0 constant] lower: [3x1 constant] upper: [3x1 constant] Minimize c'*x such that: Aeq*x = beq x >= 0
or in the more general form with linear inequalities and bounds:
Minimize c'*x such that: Aeq*x = beq A*x <= b lb <= x <= ub
The help of the karmarkar function is provided in Scilab:
http://www.scilab.org/product/man/karmarkar.html
Despite its name, the algorithm is not based on the Karmarkar algorithm, but on a primal affine-scaling interior point algorithm. This algorithm discovered by Dikin in 1967, and then re-discovered by Barnes and Vanderbei et al in 1986.
Changes in Scilab 5.3.1
In the version 5.3.1 of Scilab we improved the karmarkar linear optimization solver. The goal was to improve the usability, and to provide a much more flexible solver. The detailed changes are the following:
- User can configure an output function.
- The number of iterations can be put as an output argument.
- x0 can be put as an optional argument.
- Management of inequality constraints.
- Management of bounds.
- Computation of the exitflag.
- Computation of the Lagrange multipliers.
- Documentation provided for the rtolf and gam parameters.
- Documentation provided for the stopping rule.
- More examples provided.
There are also bugs which have been fixed:
- Bug # 7193 fixed — The karmarkar help page did not document the eps, gamma, and crit arguments.
- Bug # 8719 fixed — The karmarkar function printed unwanted messages.
- Bug # 8720 fixed — The karmarkar function stopped too early in the iterations.
- Bug # 8726 fixed — The karmarkar function produced a division-by-zero error.
- Bug # 8727 fixed — The karmarkar function required the initial guess x0.
- Bug # 8775 fixed — The karmarkar function did not detect unbounded problems.
The quapro module
http://atoms.scilab.org/toolboxes/quapro
The quapro module defines linear quadratic programming solvers. The matrices defining the cost and constraints must be full, but the quadratic term matrix is not required to be full rank.
The features of the quapro module are :
- linpro : linear programming solver
- mps2linpro : convert lp problem given in MPS format to linpro format
- quapro : linear quadratic programming solver
This module was created by Eduardo Casas Renteria, Cecilia Pola Mendez (Universidad De Cantabria), improved by Serge Steer (INRIA) and maintained by Allan Cornet, Michaël Baudin (Consortium Scilab — DIGITEO).
To install the quapro module :
atomsInstall("quapro");
and then re-start Scilab.
In this page, we will focus of the linpro function.
The linpro function can solve linear programs in general form:
Minimize c'*x A*x <= b Aeq*x = beq lb <= x <= ub
Example #1
The following problem is extracted from «Practical Optimization», Antoniou, Lu, 2007, Chapter 11, «Linear Programming Part I: The simplex method», Example 11.9, p. 361. This problem is solved by the primal affine scaling algorithm in Chapter 12, «Linear Programming Part II: Interior point methods», Example 12.2, p.382.
The program is the following.
Minimize 2.x1 + 9.x2 + 3.x3 Such as 2.x1 - 2.x2 - x3 <= -1 -x1 - 4.x2 + x3 <= -1 x >= 0
The solution is
xstar = [0 1/3 1/3]';
With karmarkar
The following script solves the problem with the karmarkar function.
A = [ 2 -2 -1 -1 -4 1 ]; b = [-1;-1]; c = [2;9;3]; lb = [0;0;0]; [xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb) yopt.ineqlin yopt.lower
This produces the following output.
-->[xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
yopt =
ineqlin: [2x1 constant]
eqlin: [0x0 constant]
lower: [3x1 constant]
upper: [3x1 constant]
iter =
70.
exitflag =
1.
fopt =
4.00004
xopt =
0.0000016
0.3333387
0.3333296
-->yopt.ineqlin
ans =
3.5
0.5
-->yopt.lower
ans =
8.5
2.560D-09
- 1.790D-09
With linpro
The following script solves the problem with the linpro function.
A = [ 2 -2 -1 -1 -4 1 ]; b = [-1;-1]; c = [2;9;3]; ci = [0;0;0]; cs = [%inf;%inf;%inf]; [xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
The previous script produces the following output.
-->[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
fopt =
4.
lagr =
- 8.5
0.
0.
3.5
0.5
xopt =
0.
0.3333333
0.3333333
Example #2
This example is extracted from «Operations Research: applications and algorithms», Wayne L. Winstons, Section 5.2, «The Computer and Sensitivity Analysis», in the «Degeneracy and Sensitivity Analysis» subsection.
The linear program is:
Maximize 6*x1 + 4*x2 + 3*x3 + 2*x4 such as: 2*x1 + 3*x2 + x3 + 2 *x4 <= 400 x1 + x2 + 2*x3 + x4 <= 150 2*x1 + x2 + x3 + 0.5*x4 <= 200 3*x1 + x2 + x4 <= 250 x >= 0
The solution is
xstar = [50;100;0;0]
With karmarkar
The following script solves the problem with the karmarkar function.
c = [-6 -4 -3 -2]';
A = [
2 3 1 2
1 1 2 1
2 1 1 0.5
3 1 0 1
];
b = [400 150 200 250]';
lb = [0;0;0;0];
[xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
The previous script produces the following output.
-->[xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
yopt =
ineqlin: [4x1 constant]
eqlin: [0x0 constant]
lower: [4x1 constant]
upper: [4x1 constant]
iter =
69.
exitflag =
1.
fopt =
- 699.99624
xopt =
50.000068
99.998479
0.0003436
0.0004409
With linpro
The following script allows to solve the problem with the linpro function.
c = [-6 -4 -3 -2]';
A = [
2 3 1 2
1 1 2 1
2 1 1 0.5
3 1 0 1
];
b = [400 150 200 250]';
ci=[0 0 0 0]';
cs=[%inf %inf %inf %inf]';
[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
This produces :
-->[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
fopt =
- 700.
lagr =
0.
0.
0.
- 1.5
0.5
1.25
0.
1.25
xopt =
50.
100.
2.842D-14
0.
Example #3
This example is extracted from «Operations Research: applications and algorithms», Wayne L. Winstons, Section 5.2, «The Computer and Sensitivity Analysis», from «Problems Group A, 1.».
We want to solve the linear program:
Maximize 150.x1+200.x2-10.x3
such as:
x1+ x2 <= 45
6.x1+10.x2 - x3 <=0
5.x1 <= 140
4.x2 <= 120
x3 <= 350
x >= 0
The solution is:
xstar = [25,20,350]
With karmarkar
The following script solves the problem with the karmarkar function.
c = [-150 -200 +10]';
A = [
1 1 0
6 10 -1
5 0 0
0 4 0
0 0 1
];
b = [45 0 140 120 350]';
lb = [0;0;0];
[xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
The previous script produces the following output.
-->[xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
yopt =
ineqlin: [5x1 constant]
eqlin: [0x0 constant]
lower: [3x1 constant]
upper: [3x1 constant]
iter =
89.
exitflag =
1.
fopt =
- 4249.9602
xopt =
25.00115
19.998673
349.99469
With linpro
The following script allows to solve the problem with the linpro function.
c = [-150 -200 +10]';
A = [
1 1 0
6 10 -1
5 0 0
0 4 0
0 0 1
];
b = [45 0 140 120 350]';
ci=[0 0 0]';
cs=[%inf %inf %inf]';
[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
This produces :
-->[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
fopt =
- 4250.
lagr =
0.
0.
0.
75.
12.5
0.
0.
2.5
xopt =
25.
20.
350.
Example #4
Consider the linear program:
Minimize -20.x1 - 24.x2 such as: 3.x1 + 6.x2 <= 60 4.x1 + 2.x2 <= 32 x >= 0
The solution is
xstar = [4;8];
With karmarkar
The following script solves the problem with the karmarkar function.
c = [-20 -24]'; A = [ 3 6 4 2 ]; b = [60 32]'; lb = [0;0]; [xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
The previous script produces the following output.
-->[xopt,fopt,exitflag,iter,yopt] =karmarkar([],[],c,[],[],[],[],[],A,b,lb)
yopt =
ineqlin: [2x1 constant]
eqlin: [0x0 constant]
lower: [2x1 constant]
upper: [2x1 constant]
iter =
66.
exitflag =
1.
fopt =
- 271.99746
xopt =
3.9998866
7.9999887
With linpro
The following script allows to solve the problem with the linpro function.
c = [-20;-24]; A = [ 3 6 4 2 ]; b = [60;32]; ci=[0;0]; cs=[%inf;%inf]; [xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
This produces:
-->[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
fopt =
- 272.
lagr =
0.
0.
3.1111111
2.6666667
xopt =
4.
8.
Example #5
This example is from the Lipsol toolbox, by Yin Zhang, as ported into Scilab by Rubio Scola in example0.sce.
Minimize 2.x1 + 5.x2 - 2.5.x3 such as: x1 S4 x3 <= 5 E2 x1 - x2 - x3 <= 0 -2 <= x1 <= 2 1 <= x2 <= %inf 0 <= x3 <= 3
The solution is
xstar = [-2;1;3];
With karmarkar
The following script solves the problem with the karmarkar function.
S4 = sin(%pi/4)/4;
E2 = exp(2);
c = [ 2; 5; -2.5];
A = [
1 0 S4
E2 -1 -1
1 0 0
0 0 1
-1 0 0
0 -1 0
0 0 -1
];
b = [ 5; 0;2;3;2;-1;0];
lb = [-2;1;0];
ub = [2;%inf;3];
[xopt,fopt,exitflag,iter,yopt]=karmarkar([],[],c,[],[],[],[],[],A,b,lb,ub)
The previous script produces the following output.
-->[xopt,fopt,exitflag,iter,yopt]=karmarkar([],[],c,[],[],[],[],[],A,b,lb,ub)
yopt =
ineqlin: [7x1 constant]
eqlin: [0x0 constant]
lower: [3x1 constant]
upper: [3x1 constant]
iter =
75.
exitflag
1.
fopt =
- 6.4999498
xopt =
- 1.9999916
1.0000033
2.9999933
With linpro
The following script solves the problem with the linpro function.
S4 = sin(%pi/4)/4;
E2 = exp(2);
c = [ 2; 5; -2.5];
A = [
1 0 S4
E2 -1 -1
];
b = [ 5; 0];
ci = [-2;1;0];
cs = [2;%inf;3];
[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
The previous script produces the following output.
-->[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
fopt =
- 6.5
lagr =
- 2.
- 5.
2.5
0.
0.
xopt =
- 2.
1.
3.
Example #6
Minimize 600*x1 + 600*x2 + 600*x3 + 600*x4 + 600*x5 + 600*x6 + 600*x7 + 200*x8 + 200*x9 + 200*x10 + 200*x11 + 200*x12 + 200*x13 + 200*x14
such that
8*x1 + 8*x4 + 8*x5 + 8*x6 + 8*x7 + 4*x8 + 4*x11 + 4*x12 + 4*x13 + 4*x14 >= 88
8*x1 + 8*x2 + 8*x5 + 8*x6 + 8*x7 + 4*x8 + 4*x9 + 4*x12 + 4*x13 + 4*x14 >= 136
8*x1 + 8*x2 + 8*x3 + 8*x6 + 8*x7 + 4*x8 + 4*x9 + 4*x10 + 4*x13 + 4*x14 >= 104
8*x1 + 8*x2 + 8*x3 + 8*x4 + 8*x7 + 4*x8 + 4*x9 + 4*x10 + 4*x11 + 4*x14 >= 120
8*x1 + 8*x2 + 8*x3 + 8*x4 + 8*x5 + 4*x8 + 4*x9 + 4*x10 + 4*x11 + 4*x12 >= 152
8*x2 + 8*x3 + 8*x4 + 8*x5 + 8*x6 + 4*x9 + 4*x10 + 4*x11 + 4*x12 + 4*x13 >= 112
8*x3 + 8*x4 + 8*x5 + 8*x6 + 8*x7 + 4*x10 + 4*x11 + 4*x12 + 4*x13 + 4*x14 >= 128
- 20*x8 - 20*x9 - 20*x10 - 20*x11 - 20*x12 - 20*x13 - 20*x14 >= -840
xi >= 0 (i = 1,...,14)
There are several solutions to this problem, but all are associated with the objective function value:
fstar = 9200
With karmarkar
The following script solves the problem with the karmarkar function.
c = [600 600 600 600 600 600 600 200 200 200 200 200 200 200]';
A = [
8 0 0 8 8 8 8 4 0 0 4 4 4 4
8 8 0 0 8 8 8 4 4 0 0 4 4 4
8 8 8 0 0 8 8 4 4 4 0 0 4 4
8 8 8 8 0 0 8 4 4 4 4 0 0 4
8 8 8 8 8 0 0 4 4 4 4 4 0 0
0 8 8 8 8 8 0 0 4 4 4 4 4 0
0 0 8 8 8 8 8 0 0 4 4 4 4 4
0 0 0 0 0 0 0 -20 -20 -20 -20 -20 -20 -20
];
b = [88 136 104 120 152 112 128 -840]';
A = -A;
b = -b;
lb=zeros(14,1);
[xopt,fopt,exitflag,iter,yopt]=karmarkar([],[],c,[],[],[],[],[],A,b,lb)
The previous script produces the following output.
-->[xopt,fopt,exitflag,iter,yopt]=karmarkar([],[],c,[],[],[],[],[],A,b,lb)
yopt =
ineqlin: [8x1 constant]
eqlin: [0x0 constant]
lower: [14x1 constant]
upper: [14x1 constant]
iter =
68.
exitflag =
1.
fopt =
9200.0482
xopt =
0.2130791
0.2373697
0.2444532
0.1395045
0.2749702
0.0000344
0.2240255
4.7906317
6.9752061
8.1870869
1.7117333
14.116657
0.0000689
6.2185468
With linpro
c = [600 600 600 600 600 600 600 200 200 200 200 200 200 200]';
A = [
8 0 0 8 8 8 8 4 0 0 4 4 4 4
8 8 0 0 8 8 8 4 4 0 0 4 4 4
8 8 8 0 0 8 8 4 4 4 0 0 4 4
8 8 8 8 0 0 8 4 4 4 4 0 0 4
8 8 8 8 8 0 0 4 4 4 4 4 0 0
0 8 8 8 8 8 0 0 4 4 4 4 4 0
0 0 8 8 8 8 8 0 0 4 4 4 4 4
0 0 0 0 0 0 0 -20 -20 -20 -20 -20 -20 -20
];
A = -A;
b = [88 136 104 120 152 112 128 -840]';
b = -b;
[n,p]=size(A);
ci=zeros(p,1);
cs=%inf*ones(p,1);
[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
This produces
-->[xopt,lagr,fopt]=linpro(c,A,b,ci,cs)
fopt =
9200.
lagr =
0.
- 6.519D-15
- 6.355D-14
3.411D-13
- 5.084D-13
- 200.
0.
1.990D-13
0.
0.
0.
0.
- 100.
0.
3.038D-14
25.
0.
25.
25.
0.
25.
5.
xopt =
1.475D-15
1.872D-15
- 9.103D-16
0.
- 2.483D-16
1.448D-15
1.3333333
0.
12.666667
10.
0.6666667
14.666667
0.
4.
Acknowledgments
We thank Reinaldo Golmia Dante for providing the initial material for this document.
Appendix
Limitations of karmarkar before Scilab 5.3.1
Before Scilab 5.3.1, the karmarkar function required that we provide a strictly feasible initial guess. This is why the resolution required two steps:
- phase 1 : search for a feasible initial guess based on the resolution of a modified problem,
- phase 2 : resolution of the original problem.
Moreover, the only constraint which was taken into account was the linear equality constraint. This is why we had to introduce slack variables if we wanted to take into account linear inequalities such as A*x <= x.
The feasibility problem (phase 1) and the introduction of slack variables are described in the two next sections. These algorithms are now directly provided by Scilab 5.3.1, so that the user now implicitely use them, but does not have to explicitely call these functions.
Feasibility problem
In this section, we describe a method to find an initial guess x0 which is strictly feasible for a problem in standard form. This method is used by the karmarkar function since Scilab 5.3.1. The method that we present is classical and is presented for example in «A Primal-Dual Exterior Point Algorithm For Linear Programming Problems» by Samaras, Sifaleras, Triantafyllidis. Another version of the same idea was presented in «A modification of karmarkar’s linear programming algorithm» by Vanderbei et al.
Assume that we must solve the linear program:
Minimize c'*x such as: Aeq*x = beq x >= 0
In order to find a feasible point, we solve the following problem :
Minimize z(p+1) such as: AAeq * z = bbeq z >= 0
where
z=[x(1) x(2) ... x(p) x(p+1)].
The matrix AAeq has the same number of rows, but one column more than Aeq. The initial guess for the modified problem is
z0=[1 1 ... 1]'=e(n+1),
where e(n+1) represents a column vector of n+1 ones. The last column of AAeq is
beq-Aeq*e(n)
so that the initial guess z0 satisfies the equation
AAeq*z0=beq.
Then we solve the modified linear program. There are three main cases.
- If the feasibility problem has no solution, then the original problem has no solution.
-
If the feasibility problem has a solution and z(p+1)>0, this means that no strictly feasible point x0 can be found. In this case, the value of z(p+1) measures the smallest offset that must be added to the inequality constraint to create a feasible linear program.
- If the feasibility problem has a solution and z(p+1)=0, we have an initial guess x0 and can move on to the phase 2.
The following function uses the previous method to find a feasible initial guess x0.
function x0 = karmarkar_searchx0 (Aeq,beq,c,eps,gam) // Search a stricly feasible initial guess for the linear program // // Minimize c'*x // Aeq*x = b // x >= 0 // // Copyright (C) 2010 - DIGITEO - Michael Baudin // Must be used under the terms of the CeCILL V2: http://www.cecill.info [n,p]=size(Aeq) cc = [zeros(p,1);1] AAeq = [Aeq,beq-Aeq*ones(p,1)] bbeq = beq z0 = ones(p+1,1) zopt=karmarkar(AAeq,bbeq,cc,z0,eps,gam) x0=zopt(1:p) endfunction
Slack and positive variables
In this section, we show how to change the formulation of an optimization problem in order to manage bounds or linear inequalities. This method is used by the karmarkar function since Scilab 5.3.1.
In practice, we may have to solve linear programs which may not be in standard form. Instead, we may have to solve programs in the form:
Minimize c'*x A*x <= b
where A is a n-by-p matrix, b is a n-by-1 column vector and c is a p-by-1 column vector. We can introduce the slack variable s, as a n-by-1 column vector which satisfy the equality:
A*x + s = b.
We must have
s >= 0.
The equality constraint can be written as
[A I]*[x;s] = b.
From there, there are two cases, depending on the constraint on x:
- either x must be non-negative,
- or x is unrestricted.
In the case where the original problem has the additionnal constraint
x >= 0,
we are done. It now suffices to consider the variable z=[x;s] and to modify the linear cost to cc=[c;0], where the zero column vector has n entries.
In the case where the variable x is unrestricted, we can write it as the difference of two positive variables :
x = xp - xn
where xp and xn are both non-negative. This leads to the linear program:
Minimize c'*(xp-xn) A*(xp-xn) + s = b xp,xn,s >= 0
The previous program can be written in matrix form:
Minimize [c;-c;0]'*[xp;xn;s] [A,-A,I]*[xp;xn;s] = b xp,xn,s >= 0
The previous program is a linear program in standard form :
Minimize cc'*z Aeq*z = b z >= 0
where
cc = [c;-c;0] Aeq=[A,-A,I]
The following function applies the previous method to preprocess a linear program in general form.
function [Aeq,beq,cc] = karmarkar_preprocess ( A , b , c ) // Converts the linear program // // Minimize c'*x // A*x <= b // // into // // Minimize cc'*z // Aeq*z = beq // z >= 0 // // where x = z(1:p) - z(p+1:2*p). // // Copyright (C) 2010 - DIGITEO - Michael Baudin // Must be used under the terms of the CeCILL V2: http://www.cecill.info [n,p]=size(A) Aeq = [A -A eye(n,n)] beq = b cc = [c;-c;zeros(n,1)] endfunction
An example of karmarkar for Scilab <= 5.3.0
In this section, we present the resolution of a linear program with Scilab versions older than 5.3.1. This example is the example #1.
We introduce slack variables and get:
Minimize 2.x1 + 9.x2 + 3.x3 2.x1 - 2.x2 - x3 + x4 = -1 -x1 - 4.x2 + x3 + x5 = -1 x >= 0
The following script solves the problem. Here, the initial guess x0 is given.
Aeq = [ 2 -2 -1 1 0 -1 -4 1 0 1 ]; beq = [-1;-1]; c = [2;9;3;0;0]; x0 = [0.2;0.7;1;1;1]; xopt=karmarkar(Aeq,beq,c,x0)
This produces the following output.
-->xopt=karmarkar(Aeq,beq,c,x0)
1. 0.856E+01 0.117E+00
2. 0.765E+01 0.107E+00
3. 0.690E+01 0.977E-01
4. 0.629E+01 0.878E-01
5. 0.580E+01 0.776E-01
6. 0.541E+01 0.672E-01
7. 0.510E+01 0.571E-01
8. 0.486E+01 0.477E-01
9. 0.467E+01 0.394E-01
10. 0.452E+01 0.321E-01
[...]
36. 0.400E+01 0.278E-04
37. 0.400E+01 0.209E-04
38. 0.400E+01 0.156E-04
39. 0.400E+01 0.117E-04
40. 0.400E+01 0.880E-05
xopt =
0.0000041
0.3333474
0.3333235
0.0000101
0.0000704
Now, assume that the initial guess x0 is unknown.
We solve the feasibility problem by introducing one extra variable x(p+1). The following script solves the problem.
-->x0 = karmarkar_searchx0 (Aeq,beq,c,0,0.999)
1. 0.100E-02 0.999E+00
2. 0.100E-05 0.999E-03
3. 0.100E-08 0.999E-06
4. 0.100E-11 0.999E-09
5. 0.100E-14 0.999E-12
6. 0.100E-17 0.999E-15
7. 0.100E-20 0.999E-18
8. 0.100E-23 0.999E-21
9. 0.100E-26 0.999E-24
10. 0.100E-29 0.999E-27
11. 0.100E-32 0.999E-30
12. 0.100E-35 0.999E-33
13. 0.100E-38 0.999E-36
14. 0.100E-41 0.999E-39
[...]
53. 0.100-158 0.999-156
54. 0.100-161 0.999-159
55. 0.100-161 0.000E+00
x0 =
0.497293
0.7455296
1.3277695
0.8242427
1.1516418
The previous script allows to produces the initial guess:
x0 = [0.497293;0.7455296;1.3277695;0.8242427;1.1516418]
We now plug the initial guess x0 into the original problem and get:
-->xopt=karmarkar(Aeq,beq,c,x0,1.e-14,0.999)
1. 0.537E+01 0.541E+00
2. 0.417E+01 0.222E+00
3. 0.401E+01 0.402E-01
4. 0.400E+01 0.108E-02
5. 0.400E+01 0.195E-03
6. 0.400E+01 0.316E-04
7. 0.400E+01 0.101E-05
8. 0.400E+01 0.156E-06
9. 0.400E+01 0.244E-07
10. 0.400E+01 0.957E-09
11. 0.400E+01 0.130E-09
12. 0.400E+01 0.193E-10
13. 0.400E+01 0.899E-12
14. 0.400E+01 0.110E-12
15. 0.403E+01 0.155E-13
16. 0.403E+01 0.832E-15
xopt =
3.885D-19
0.3361047
0.3362025
1.059D-16
1.218D-16
References
- «Iterative solution of problems of linear and quadratic programming», Dikin, Doklady Akademii Nausk SSSR, Vol. 174, pp. 747-748, 1967
- «A New Polynomial Time Algorithm for Linear Programming», Narendra Karmarkar, Combinatorica, Vol 4, nr. 4, p. 373–395, 1984.
- «A variation on Karmarkar’s algorithm for solving linear programming problems, Earl R. Barnes, Mathematical Programming, Volume 36, Number 2, 174-182, 1986.
- «A modification of karmarkar’s linear programming algorithm», Robert J. Vanderbei, Marc S. Meketon and Barry A. Freedman, Algorithmica, Volume 1, Numbers 1-4, 395-407, 1986.
- «Practical Optimization: Algorithms and Engineering Applications», Andreas Antoniou, Wu-Sheng Lu, Springer, 2007, Chapter 12, «Linear Programming Part II: Interior Point Methods».
- «Global Convergence of a Long-Step Affine Scaling Algorithm for Degenerate Linear Programming Problems», Takashi Tsuchiya and Masakazu Muramatsu, SIAM J. Optim. Volume 5, Issue 3, pp. 525-551 (August 1995)
- «The convergence of dual variables», Dikin, Tech. report, Siberian Energy Institute, Russia, 1991
- «The Affine Scaling Algorithm Fails for Stepsize 0.999», Walter F. Mascarenhas, SIAM J. Optim. Volume 7, Issue 1, pp. 34-46 (1997)
- «A Primal-Dual Exterior Point Algorithm For Linear Programming Problems», Nikolaos Samaras, Angelo ifaleras, Charalampos Triantafyllidis, Yugoslav Journal of Operations Research, Vol 19 (2009), Number 1, 123-132
- «Operations Research: applications and algorithms», Wayne L. Winstons.