18
There is a series of three lectures of Robert Bixby (the Bi in Gurobi) on Solving Linear Programs: The Dual Simplex Algorithm. Have a look at the third part Implementing the algorithm where he talks about many details and tricks for implementing general bounds, finding a feasible basis, pricing, and solving linear systems.
In particular at about 38:00 he ...
17
Let's start with the easy one:
Ellipsoid Method
Never use it. Even though it might appear efficient in the complexity-theory sense, it performs terrible and suffers heavily from numerical issues.
Primal Simplex
Mostly studied for historical interest, but there are some cases where it might outperform dual simplex (when the basis matrix in the primal revised ...
16
It has nothing to do even with linear programming. It's a simple mathematical fact:
$$\min \left( f \left( x \right) \right) = - \max \left( -f \left( x \right) \right)$$
which still holds when you restrict the domain of the function by the constraints (actually to a convex polyhedron in case of LP).
16
First of all, usually implementations are centered around the revised dual simplex, not the primal (even though solvers will still use a primal simplex method implementation for some tasks in the solution process).
According to Huangfu and Hall and Koberstein, the most important non-textbook techniques for the dual revised simplex appear to be:
Dual ...
13
First, the problem is not a linear optimization problem, at least not for the objective function shown (which is nonlinear due the conditional portion in lines 10-13 and particularly the division by E_ges_i in line 13. Simulated annealing might be fine as a heuristic approach, but given the nonlinear objective, only accepting improving steps might or might ...
13
The slow convergence of the Gomory cuts was well-known and source of frustration for the field up until the 90s. It seemed that Gomory cuts would be a cute idea, but not one that would lead to any real computational success.
Then work by Balas, Ceria, Cornuejols, and Natraj rekindled interest in the area, and Gomory cuts became very important in real ...
10
Dual simplex is the method of choice for resolving an LP if you have an optimal solution and you change the problem by modifying the feasible region. Ranging the RHS, adding cuts or branching in MIP, Benders decomposition, etc. are examples where that happens. Some other problems are easy to start in the dual method, for example, when all variables have ...
9
Bob Bixby (as just one representative of many computational guys) talks regularly about progress in LP and MIP solving; for the 50th anniversary issue of "Operations Research" he wrote an article on history and progress in LP solving that also contains perspectives on different algorithms (here), his general message is: these algorithms became vastly more ...
9
From the slack form we can observe two things about your starting point $(x_1,x_2) = (0,0)$.
The starting point is not primal feasible. This follows from the fact that not all variables $x_1$, $x_2$, $x_3$, $x_4$ are non-negative ($x_4 < 0$).
The starting point is not dual feasible. This follows from the fact that not all variable coefficients in the $z$-...
8
In addition to @Michael's comment you have to distinguish between the algorithm used to solve the root node of a problem and the algorithm used for the nodes in the branch-and-bound tree.
gurobi (and very likely also other commercial solvers) offer parameters to specify this separately:
Method for changing the algorithm used at the root node. If you have ...
8
Not an expert on simplex, but here's my attempt on an answer:
In general, the solution of the (previous) LP Relaxation will no longer be primal feasible when the primal LP is tightened (e.g. new cut in branch & bound).
In the dual simplex, new primal cuts correspond to new dual variables, which are initialized as nonbasic, and thus the previous ...
8
Maybe the unnecessarily large value for $A$ is causing numerical trouble. Try instead $A = \max_{i,j} p_{i,j} = 9$.
Probably your $=0$ in the declaration of $x$ should be $\ge 0$. In fact, you generally need to declare $x$ to be binary when you include side constraints.
8
the Simplex algorithm iterates from extreme point to extreme point
Technically, no. The simplex algorithm iterates from basis to basis. It just happens that feasible basic solutions correspond to extreme points.
(for instance, the dual simplex iterates through dual-feasible basic solutions, which are not extreme points of the primal-feasible region).
...
6
If you want to implement an algorithm by your own, then we suggest you a randomized, derivative-free search, even simpler than Nelder-Mead approaches. Given a feasible solution (respecting the sum equal to 1), move randomly the values of the variables by an epsilon while maintaining the constraint feasible. If the solution is better, then keep it, otherwise ...
6
It is common practice for MIP solvers to solve node LPs (other than at the root node) via dual simplex. I can't say with certainty that they terminate dual simplex prematurely if the objective value becomes inferior to the current incumbent, but I would think it likely.
That does not address the question of stopping dual simplex early when the bound is ...
6
Yes, you can solve the dual and use that as a (weaker) bound than the optimal solution of the LP. This leads to the trade off between faster processing nodes vs processing more nodes. This approach is often exemplified in the choice between Lagrangean relaxation and Dantzig Wolfe decomposition. In its pure form you need to solve the DW to optimality in order ...
6
Your constraint matrix is changing with each new problem, so it might not be easy to warm-start ... and it might not be worthwhile, even if you could. One nice thing (among several) about transportation problems is that the origin is feasible, meaning the simplex method has an obvious starting basis. Warm-starting would require you to massage the previous ...
6
I actually have quite a few points. As usual, things are not as clear cut.
I use advanced bases for LPs very often and they are surprisingly effective and tolerant of quite a few changes in the model.
For large problems, often a good strategy is to use the barrier method for the first problem (solved from scratch) and the simplex for subsequent related ...
5
It is explained in this link as:
Simplex multipliers are essentially the shadow prices associated with a particular basic solution. Those are the multiples of their initial system of equations such that, when all of these equations are multiplied by their respective simplex multipliers and subtracted from the initial objective function, the coefficients of ...
5
When taking a step in the dual simplex method, if a dual variable is zeroed, the dual objective may continue to improve if the variable passes through zero. To maintain dual feasibility, the variable must be associated with a primal variable with finite lower and upper bounds. As the dual variable passes through zero, the corresponding primal variable [which ...
5
In page 17 of this note by Michel Goemans, the process of converting $T_2 \iff T_1$, has been explained. If you define $Ax=b$ as $A_Bx_B+A_Nx_N=b$ (in your formulation for $T_1$, $A_B=B$) in which $x_B$ are the basic variables and $x_N$ are the Non-basic variables, then $T_1$ has been obtained from the $T_2$ by a sequence of elementary row operations.
From ...
4
The only requirements for the constraints, that I am aware of, when using the simplex algorithm to solve a minimization (and maximization) problem is to include the slack and surplus variables where needed, and the decision variables have to be non-negative. Below is an example to illustrate how to formulate a problem to be solved using the simplex algorithm ...
4
Here is a link that includes all the information that you need. The matrix should include all the capacity limitations on all the connections between nodes. Actually, for your example, it should be a $8\times8$ matrix with all the coefficients. Each row represents one of the constraints in your LP model. In other words for each row, you consider one of the ...
4
My guess would be that the variable is not basic, it is non-basic but at the upper bound of 1.0.
Modern solvers use the generalized simplex method which allows for lower and upper bounds on a variable. If a variable is upper bounded, its optimal reduced cost needs to be non-positive.
I can't say I fully understand the output you pasted, but it looks like ...
4
All your constraints are equality. So, add an artificial variable to each constraint (let's call them $a_i \quad i\in\{1,..,4\}$). Now all these artificial variables need to be in the objective function with a coefficient of Big-M. Since you are maximizing, you want to make sure using any of them will penalize your objective function (so, you add them with ...
4
I'll try to give a geometrical approach.
You are considering a polyhedron
$$
P = \{x \in \mathbb{R}^{n} \ | \ Ax \leq b \}.
$$
where $b \in \mathbb{R}^{m}$ and $A \in \mathbb{R}^{n \times m}$.
(I'm using $Ax$ and not $A^{T}x$ to match the dimensions in the OP).
The easy case: no degeneracy
Let's assume that
there is no primal degeneracy, i.e., no ...
4
The "goods" going to or coming from the dummy node are not really moved; hence the cost of zero, no matter the quantity.
If the problem is solved to optimality, using Network Simplex, or whatever, there is no "first" which can't be changed later as the algorithm proceeds. The algorithm ensures the total cost for moving everything is ...
3
The point of the 2-phase simplex is to find a feasible initial solution (a starting point for the "normal" simplex). Indeed finding a set of $X$ values that satisfy the constraints can be hard (manually). This is not a problem when you have constraints of the form $Ax\le b$, as $x=0$ is a trivial possibility.
To do this you introduce one artificial variable ...
3
There is no way to do this with CPLEX directly as far as I know, but you can use CPLEX's C++ API to code the iterative process yourself. The API allows the user to build/modify the model in C++ as well as to retrieve solutions, so you can retrieve the solution in code, add the new constraint, and resolve. You can also use the solution pool to get other ...
2
The shadow prices are an optimal solution to the dual problem. Adjusting the right-hand side of the primal problem is equivalent to adjusting the objective coefficients of the dual, which changes the slope of the objective hyperplane tangent to the dual feasible region at the dual optimum. Let's assume that the initial dual optimum is non-degenerate, so that ...
Only top voted, non community-wiki answers of a minimum length are eligible