# Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

266 questions
Filter by
Sorted by
Tagged with
89 views

### Can I replace the objective function $f$ with $g$ if $g \ge f$?

I am working on a project where the customer requested to change the current objective function $f$ to another function $g$ (both linear). It is easy to prove that $f \le g$ and as both are linear ...
40 views

### How to properly define an edge set with an uncommon condition

I am trying to define an edge set as follows: $\mathcal{E}=\{(i,j)|i,j\in\mathcal{V}\land T_{ij}\leq R \land \text{$i$and$j$are not jointly in$\mathcal{K}$\}}$, where $\mathcal{V}$ is the set of ...
47 views

### linearisation of if-then constraint [duplicate]

Is it possible to translate this if-then constraint in linear manner to be solved with a linear programming solver? If not, how can it be translated into a integer programming manner to be solved by ...
190 views

### Output of binary variable greater than one

I am working on a shipping demurrage problem that uses a binary variable to denote the date a specific vessel can be loaded (I have been kindly helped by Wesley on OR before with this). I am confident ...
43 views

### How to deal with the sub-problem with zero reduced cost in D-W decomposition

The specific linear programme has an optimal solution as $x_1 = 0.66$, $x_2 = 1.33$, $x_3 = 12.2$, $x_4 = 0.0$ and the objective value is $33.3$. While the problem is solved by D-W decomposition ...
152 views

### Polynomial algorithm for a special ILP problem

Given the following problem: \begin{align} & z=\min \sum_{ij} x_{ij}\\ \text{s.t.} & \quad \sum_i d_{ij} x_{ij} \ge s_j, \quad \forall j \tag1 \\ & \quad \sum_j x_{ij} \le 1, \quad \...
144 views

### A more efficient way of solving an peculiar optimization problem

Given the table ...
116 views

### Representing Date Variables in Pulp

I am working on an optimisation problem that involves minimising shipping demurrage. I am struggling to model how to represent the difference, (x-y) between dates where the ship is ready to be loaded ...
123 views

### Pulp Python: How to formulate a time-based variable for shipping demurrage

I am working on a shipping optimisation problem that aims to minimise demurrage charges as a result of low/insufficient inventory. I have daily vessel requirement (sales) data in the format ...
41 views

### Linearize max function in a constraint [duplicate]

I have a constraint as follows: $\sum_i {r_i} \geq \max \{g_j, B_j\}$ where, $r_i$, $g_j$ are variables and $B_j$ is a parameter. How do I linearize the constraint (I suppose using big-M method)?...
120 views

### Pyomo add constraint error: Rule failed when generation expression for constraint

I am trying to solve a model with Pyomo and struggling with indexing. Below is a simple problem instance, where you can also see the error. The message is straightforward and self-explanatory but ...
77 views

### Linearity of an optimization problem which comprises the product of variables with constant values from a non-linear function

In a mathematical integer optimization problem, if the objective function is represented as $\sum x_k \cdot M_k$, where $M_k$ is a non-linear function whose value is known and just plugged in to the ...
69 views

### Cplex giving different solutions for equivalent Linear problems

I'm trying to simplify a linear problem by removing "useless" variables and constraints. After simplifying my initial problem and solving both instances with Cplex, it seems like the results differ ...
644 views

### Can presolve reductions change the value of the linear programming relaxation?

For integer programs solvers (like Gurobi, Cplex, ...) report the value of the linear programming relaxation for integer programs, i.e. ...
598 views

### Linear optimization problem with user-defined cost function

I have a linear optimization problem for which I am looking for a suitable optimization solution that can fulfill my requirements. Here is an explanation of the optimization problem: There are a ...
60 views

### Proof that the leaving variable cannot be selected as the entering one in the next round

Using the Dantzig's pivoting rule, can it be proven that the leaving variable of one round cannot be selected as the entering variable in the next round?
52 views

### Linear programming: extending problems yields non linearity

I had a linear programming problem with the following objective function $$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$ Where $q, p, C, c$ are known. Let the term ...
170 views

### Pulp: slack variable to identify & measure extent infeasible in supply problem

I am currently modelling a supply problem that attempts to optimise a rail schedule which moves products from a production plant, to a warehouse to satisfy sales. The model is working fine (thanks in ...
87 views

### Physical Interpretation of a dual of an LP

I was recently asked to physically interpret a dual of an LP for an audience who does not know mathematics/OR (without LP, dual, bounds, etc.). Though I attempted it and was very close to what the ...
120 views

### Estimation of the number of optimum vertices

Consider any linear programming model of $n$ variables and $m$ constraints which has multiple optimum solutions. If it is possible, I'd like to know the lower and upper limits (in terms of $n$, $m$ ...
629 views

### Linear programming convexity

Is it possible for a linear programming model to be non-convex ? If it is, please, provide a simple 2 variables example and explain why it is non-convex. EDIT 1: I have been wondering, maybe the ...
55 views

### Weapon Target Assignment Problem + Time Windows

So I am very familiar with the WTAP it the static case. What I am wondering, is there a formulation that has "time windows" as well? Let's say you have some weapons and some targets, you know the ...
38 views

### Public available MPS files with semi-continuous variables

Is there some MPS files with semi-continuous variables public available anywhere? To me it seems MIPLIB does not contain any. Erling
54 views

### Complexity of determining whether a LP or MIP is infeasible

What is the best complexity for the worst case scenario and the algorithm associated with it to determine if a linear programming (LP) is infeasible ? Further, what if we consider a mixed integer ...
99 views

### Does anyone have the criss cross algorithm programming code to solve linear programming problems?

I have a project that requires programming code for the simplex algorithm and criss-cross algorithm. The purpose of this project is to compare the two methods. I've tried to find it, but the ...
56 views

### Linear programming with correction term based on decision vector

I had a linear programming problem where I am optimizing some function $$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$ Where $q, p, C, c$ are known. I now want to ...
134 views

### Suggest me good books to learn heuristics to solve Operations Research problems using python

Suggest me some good books with implementation of heuristics using python to solve operations research problems
54 views