Minimize[{x+2 y,-5x+y==7 &&x+y≥26&& x≥3&&y≥4},{x,y}]

NMinimize[{x+2 y,-5x+y==7 &&x+y≥26&& x≥3&&y≥4},{x,y}]

LinearProgramming[{1,2},{{-5,1},{1,1}},{{7,0},{26,1}},{{3,Infinity},{4,Infinity}}]

Options for (RefLink[LinearProgramming, paclet:ref/LinearProgramming]).

LinearProgramming[{-1.,-1},{{1.,1.}},{{1.,-1}},Method->"InteriorPoint"]

LinearProgramming[{-1.,-1},{{1.,1.}},{{1.,-1}},Method->"RevisedSimplex"]

m=SparseArray[RandomChoice[{0.1,0.9}->{1.,0.},{50,200}]];
xi=LinearProgramming[Range[200], m, Table[0,{50}], 
 Method -> "InteriorPoint"];//Timing

xs=LinearProgramming[Range[200], m, Table[0,{50}], 
 Method -> "Simplex"];//Timing

Range[200].xi-Range[200].xs

{x,y,z,w}=DualLinearProgramming[{3,4},{{1,2}},{5},{{1,4},{1,4}}]

{3,4}.x

{5,1,1,-4,-4}.Flatten[{y,z,w}]

{x,y,z,w}=DualLinearProgramming[{3,4},{{1,2}},{5+0.001},{{1,4},{1,4}}]

{3,4}.x - 11

LinearProgramming[{1.,1},{{1,1},{1,1}},{{1,-1},{2,1}},Method->"InteriorPoint"]

LinearProgramming[{-1.,-1.},{{1.,1.}},{1.},Method->"InteriorPoint"]

LinearProgramming[{-1.,-1.},{{1.,1.}},{1.},Method->"Simplex"]

A=SparseArray[{{i_,i_}->1.,{i_,1}->1.},{300,300}];
c = Table[1,{300}];
b = A.Range[300];

{x1=LinearProgramming[c,A,b,Method->"InteriorPoint"];//Timing, x2=LinearProgramming[c,A,b,Method->{"InteriorPoint","TreatDenseColumns"->False}];//Timing}

x1.c-x2.c

p=Import["Optimization/Data/afiro.mps"]

NMinimize@@p

p=Import["Optimization/Data/ganges.mps","Elements"]

{c,A,b,bounds}=Import["Optimization/Data/ganges.mps","LinearProgrammingData"];

x=LinearProgramming[c,A,b,bounds];

c.x

p=Import["Optimization/Data/ganges.mps","ConstraintMatrix"]

txt = "NAME TESTPROB\nROWS\n N COST\n L CON1\n G CON2\n E CON3 \nCOLUMNS\n x COST 1 CON1 2\n x CON2 3\n y COST 4 CON1 5\n y CON3 6\n Z COST 7 CON2 8\n Z CON3 9\nRHS\n RHS1 CON1 10 CON2 11\n RHS1 CON3 12\nBOUNDS\n UP BND1 x 13\n LO BND1 y 14\n UP BND1 y 15\nENDATA\n";

file = Close[OpenWrite[]];
Export[file,txt,"Text"];

Import[file, "MPS","FreeFormat"->True]

ExampleData["LinearProgramming"]

ExampleData[{"LinearProgramming","afiro"}]

LinearProgramming@@%

ExampleData[{"LinearProgramming","afiro"},"Properties"]

ExampleData[{"LinearProgramming","afiro"},"Equations"]

L1Minimization[A_,b_]:= Module[
{m,n,B,c,Aall,ball,x,lb,AT },
{m,n}=Dimensions[A];
AT = Transpose[A];
B=SparseArray[{{i_,i_}->1},{m,m}];
Aall=Join[Transpose[Join[B,-AT]],Transpose[Join[B,AT]]];
ball=Join[-b,b];
c=Join[Table[1,{m}],Table[0,{n}]];
lb = Table[-Infinity,{m+n}];
x=LinearProgramming[c,Aall,ball,lb];
x=Drop[x,m]
]

A=SparseArray[{{1,2,3},{5,6,7},{7,8,9},{10,11,12}}];
b={1,2,3,4};
LinearSolve[A,b]

x=L1Minimization[A,b]

{Norm[A.x-b,1],Norm[A.x-b,2]}//N

x2=PseudoInverse[A].b

{Norm[A.x2-b,1],Norm[A.x2-b,2]}//N

OptimalAnchorDesign[X_,Y_,ANCHORS_,forcepoints_,dist_: 3]:=Module[{a,c,ldist,p,NODES,UNANCHORED,setx,sety,length,xload,yload,nnodes,getarcs,ARCS,comp,comps,tensions,const1,const2,lengths,volume,inedges,outedges,nodebalance,const3,vars,totalf,maxf,res,tens,setInOutEdges,consts,sol,f,xii,yii,xjj,yjj,t,rhs,ma,obj,m,n},
Clear[comp,tensions,tens,vars];

(* need at least 2 anchor points *)
If[Length[Union[ANCHORS]]==1,Return[{}]];

(* a lattice of nodes *)
NODES=Partition[Flatten[Outer[List,X,Y]],2];

(* these are the nodes near the wall that will be anchored *)
UNANCHORED=Complement[NODES,ANCHORS];
(* the many links exist in the structure that we try to optimize away *)
setx[{x_,y_}]:=(xload[x,y]=0);
sety[{x_,y_}]:=(yload[x,y]=0);
Map[setx,UNANCHORED];
Map[sety,UNANCHORED];
Map[(yload[#[[1]],#[[2]]]=-1)&,forcepoints];

(* get the edges that link nodes with neighbors of distance ≤ 3 *)
nnodes=Length[NODES];
getarcs=Compile[{{NODES,_Integer,2}},Module[{xi,yi,xj,yj,i,j,nn=0,NN},
(* we use a two-sweep strategy as a nested list that would not be allowed to compile by Compile *)
Do[Do[{xi,yi}=NODES[[i]];
{xj,yj}=NODES[[j]];
If[Abs[xj-xi]≤dist&&Abs[yj-yi]≤dist&&Abs[GCD[xj-xi,yj-yi]]==1&&(xi>xj||(xi==xj&&yi>yj)),nn++],{j,Length[NODES]}],{i,Length[NODES]}];
NN=Table[{1,1,1,1},{nn}];
nn=1;
Do[Do[{xi,yi}=NODES[[i]];
{xj,yj}=NODES[[j]];
If[Abs[xj-xi]≤dist&&Abs[yj-yi]≤dist&&Abs[GCD[xj-xi,yj-yi]]==1&&(xi>xj||(xi==xj&&yi>yj)),NN[[nn++]]={xi,yi,xj,yj}],{j,Length[NODES]}],{i,Length[NODES]}];
NN]];
ARCS=Partition[Flatten[getarcs[NODES]],{4}];
length[{xi_,yi_,xj_,yj_}]:=Sqrt[(xj-xi)^2+(yj-yi)^2]//N;
(* the variables: compression and tension forces *)
comps=Map[(comp@@#)&,ARCS];
tensions=Map[(tens@@#)&,ARCS];
const1=Thread[Greater[comps,0]];
const2=Thread[Greater[tensions,0]];
lengths=Map[(length[#])&,ARCS]//N;

(* objective function *)
volume=lengths.(comps+tensions);

Map[(inedges[#]=False)&,NODES];
Map[(outedges[#]=False)&,NODES];
setInOutEdges[{xi_,yi_,xj_,yj_}]:=Module[{},If[outedges[{xj,yj}]===False,outedges[{xj,yj}]={xi,yi,xj,yj},outedges[{xj,yj}]={outedges[{xj,yj}],{xi,yi,xj,yj}}];
If[inedges[{xi,yi}]===False,inedges[{xi,yi}]={xi,yi,xj,yj},inedges[{xi,yi}]={inedges[{xi,yi}],{xi,yi,xj,yj}}];];
Map[(setInOutEdges[#])&,ARCS];
Map[(inedges[#]=Partition[Flatten[{inedges[#]}],{4}])&,NODES];
Map[(outedges[#]=Partition[Flatten[{outedges[#]}],{4}])&,NODES];

nodebalance[{x_,y_}]:=Module[{Inedges,Outedges,xforce,yforce},Inedges=inedges[{x,y}];
Outedges=outedges[{x,y}];
xforce[{xi_,yi_,xj_,yj_}]:=((xj-xi)/length[{xi,yi,xj,yj}])*(comp[xi,yi,xj,yj]-tens[xi,yi,xj,yj]);
yforce[{xi_,yi_,xj_,yj_}]:=((yj-yi)/length[{xi,yi,xj,yj}])*(comp[xi,yi,xj,yj]-tens[xi,yi,xj,yj]);
(* constraints *)
{Total[Map[xforce,Inedges]]-Total[Map[xforce,Outedges]]==xload[x,y],Total[Map[yforce,Inedges]]-Total[Map[yforce,Outedges]]==yload[x,y]}
];
const3=Flatten[Map[nodebalance[#]&,UNANCHORED]];
(* assemble the variables and constraints, and solve *)


vars=Union[Flatten[{comps,tensions}]];
{rhs,ma}=CoefficientArrays[const3,vars];
obj=CoefficientArrays[volume,vars][[2]];
{m,n}=Dimensions[ma];
Print["Number of variables = ",n," number of constraints = ",m];

(* solve *)
t=Timing[sol=LinearProgramming[obj, ma, Transpose[{-rhs,Table[0,{m}]}],Table[{0,Infinity},{n}]];];
Print["CPU time = ",t[[1]]," Seconds"];
Map[Set@@#&,Transpose[{vars,sol}]];

(* Now add up the total force on all links, and scale them to be between 0 and 1. *)
maxf=Max[comps+tensions];
Evaluate[Map[totalf[#]&,ARCS]]=(comps+tensions)/maxf;

(* Now we plot the links that have a force at least 0.001 and get the optimal design of the anchor. We color-code the drawing so that red means a large force and blue a small one. Also, links with large forces are drawn thinner than those with small forces. *)

res={EdgeForm[Black],White,Polygon[{{0,0},{0,Length[Y]},{1,Length[Y]},{1,0}}],Map[({xii,yii,xjj,yjj}=#;f=totalf[{xii,yii,xjj,yjj}];
If[f>0.001,{Hue[.7*(1-f)],Thickness[.02 Sqrt[f]],Line[{{xii,yii},{xjj,yjj}}]},{}])&,ARCS],GrayLevel[.5],PointSize[0.04],{Black,Map[{Arrow[{#,#+{0,-4}}]}&,forcepoints]},Map[Point,ANCHORS]};
Graphics[res]
];

m=30;(* y direction. *)
n=30;(* x direction. *)
X=Table[i,{i,0,n}];
Y=Table[i,{i,0,m}];
res=OptimalAnchorDesign[X,Y,Table[{1,i},{i,Round[m/3],Round[m/3*2]}],{{n,m/2}},3]

m=40;(*must be even*)
n=40;
X=Table[i,{i,0,n}];
Y=Table[i,{i,0,m}];
res=OptimalAnchorDesign[X,Y,Table[{Round[n/3],i},{i,Round[m/2]-1,Round[m/2]+1}],{{n,m/2}},3]

SeedRandom[123];
{m,n}={20,200};
c=Table[RandomInteger[{1,10}],{n}];
A=Table[RandomInteger[{-100,100}],{m},{n}];
b = A.Table[1,{n}];
bounds = Table[{-10,10},{n}];

t=Timing[x=LinearProgramming[c,A,b,bounds,Method->"Simplex"];]; Print["time = ",t[[1]]," optimal value = ",c.x," or ",N[c.x]]

t=Timing[x=LinearProgramming[c,A,b,bounds,Method->"RevisedSimplex"];]; Print["time = ",t[[1]]," optimal value = ",c.x," or ",N[c.x]]

t=Timing[x=LinearProgramming[N[c],N[A],N[b],N[bounds],Method->"InteriorPoint"];]; Print["time = ",t," optimal value = ",c.x]

Interior Point Formulation

Convergence Tolerance