8

This may depend on how you define "reduced costs". If you mean reduced costs as computed by the simplex algorithm, then no, it is not possible that all are strictly positive due to the mechanics of the algorithm. If you mean $c^\prime - y^{*\prime}A$ for the original variables and $y^{*\prime} I$ for the surplus variables, where $y^*$ is any optimal dual ...


6

I would approach this as a mixed integer linear programming (MILP) problem. There are a number of MILP solvers, some open source, some commercial (with some of the commercial solvers providing free licenses for educational use). Many of them either have a Python API or can be used with PuLP (mentioned in comment to the selected answer). You might want to ...


5

I won't write a python solution as i am not familiar with any python modeling language but i can describe the approach i took in the past to solve problems like this. I would solve this problem using a technique of finite horizon optimal control where we have an $x_t$ a state vector for each time point, a control signal $u_t$, a prediction $p_t$. The core of ...


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

If your sub-problem is a shortest path problem on a complete graph, without resource constraints, you can delete vertices which don't decrease the reduced cost. Indeed, for any path containing such a vertex, removing the vertex gives another path which is both feasible for the sub-problem and which corresponds to a master problem column with smaller reduced ...


2

It's a bit tricky to sort out what is going on here. Given a dual solution ($\lambda,\gamma,\theta$) to the LP relaxation of the master problem, your subproblem will need to solve for $a_{ir}$ and $\beta_{bs}$ (or not; see below) so as to maximize the expression on the left side of your dual constraint, subject to whatever constraints there are for $a_{ir}$ ...


1

Depending on what your decision variables are you are looking at an integer, mixed integer, or mixed integer linear programming problem. It seems to me that you want to solve it using a Python model. If that is the case, you can look at Pyomo or PuLP systems if you're looking for open-source solvers.


1

I think I have answered my own question over the last day. I found that fixing non-basic variable with non-zero reduced was enough to keep the optimal value of higher priority goals. The reason I was not getting the solution to retain the higher priority goal's optimality was due to a different reason. I have been using a tolerance to limit the upper bound ...


Only top voted, non community-wiki answers of a minimum length are eligible