Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
97 views

Condition for an integer program and its linear relaxation to have the same value

Let $A$ be a $(0,1)$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad ...
3
votes
1answer
198 views

Why is the Lagrange Multiplier not equal the Shadow Price (Excel solver, Matlab linprog, Gurobi)?

I have a LP with equality and inequality constraints. When solving the LP with the excel-solver (GRG Nonlinear) the sensitivity report returns the lagrange multiplier for all constraints. When solving ...
3
votes
2answers
99 views

Modelling a data-sensitivity scenario as an ILP problem

I am new to linear programming, and I recently came across the following exercise, which I do not know how to solve: When publishing data, it is sometimes important to "suppress" sensitive ...
7
votes
0answers
79 views

Building the Scheurman's Model II constraints for a multi period linear program

Scheurman's paper discusses Model I and model II Formulation to solve harvesting and scheduling problems. It is a specific implementation to solve multi period linear programs. Both models are also ...
2
votes
1answer
80 views

Can CPLEX output LP solution with primal variables only?

CPLEX writeSolution method outputs both primal and dual variable values of a LP. I know how to parse through the solution file to extract specific primal variable ...
2
votes
1answer
154 views

Linearize sum of continuous and boolean variable

For maximizing the objective function $\sum_i{d_i y_i}+ A x - B \cdot \mathbb{I}_{x>0}$, how can I linearize $ A x - B \cdot \mathbb{I}_{x>0}$ term where $d_i, A$ and $B$ are positive constants ...
1
vote
0answers
86 views

Expansion heuristic using gurobi reduced cost / shadow price (LP)

Gurobi 9.0.0 // C++ // LP Let us assume the following problem with three nodes: (1)-----(2)-----(3) node (1) is producing ...
1
vote
2answers
94 views

How this problem can be defined as MultiObjective optimisation

I need to optimize the end-to-end latency of a multi-component application. Assuming that the application has 10 components, component 1-5 is hosted by device 1, and device 2 is hosting the other 5 ...
2
votes
1answer
87 views

Specific usecase of two-phase simplex algorithm

The problem below aims to find to most optimal way to transport the fuel : A company Er must transport a type of fuel from its two refineries Ra and Rb to its two points of sale PV1 and PV2. The ...
3
votes
3answers
111 views

How to write distance specific constraint?

Suppose there are a few plants (p) and few customers (c). The supply (Sp), distance (Dpc), cost (COSTpc) and demand (DEMANDc) between them is given. I have a constraint that 90% of total demand of all ...
2
votes
1answer
122 views

Is my formulation correct and how to formulate this IF-THEN constraint?

I have system with $N_U$ users and $N_T$ transmitters. Multiple transmitters can transmit to a single users and one transmitter can transmit to many users, i.e., two sets of transmitters serving two ...
4
votes
1answer
82 views

How would you linearize this scheduling problem? Or how would you solve this? It is variation of a set coverage problem for OpenSolver

So, it's been about 15 years since I took my OR class in college. I'm not versed in any programming language besides a little bit of VBA. A client of mine is looking to solve the following problem. I ...
4
votes
1answer
101 views

Formulating these logical constraint in an ILP

I have these two constraints : $z \leq My$ $t \leq M'y $ where $z$ and $t$ are two integer variables $ z, t\geq 0$, $y$ is a binary variable, and $M$, $M'$ are two big numbers. So basically these ...
3
votes
0answers
45 views

High-mix manufacturing capacity

I'm not an expert in OR but I would like to determine what is the maximum manufacturing capacity of a plant (or how much a plant can produce of mix products). Each person in the plant has a known set ...
7
votes
0answers
104 views

Provide basic solution to CLP

I'm using Pyomo to formulate an LP with approx 500,000 constraints and 200,000 decision variables. The LP is solved using CLP. Some instances fail to return even a feasible solution after many ...
19
votes
2answers
281 views

Automating the column generation decomposition process

When trying a decomposition technique such as column generation, most of the times my approach is to look at the problem and then: Decide what a column should represent Write the Master Problem Write ...
6
votes
2answers
191 views

Simplex algorithm and extreme points

For this question my short-hand is LP = linear program, BFS = basic feasible solution, SEF = standard equality form. Since the Simplex algorithm iterates from extreme point to extreme point (...
3
votes
1answer
132 views

Logical constraint in ILP

I want to write the following constraint: Let $z$ be an integer variable such that $0\le z\le M$, and $t$ be a binary variable where $M$ denotes big-M. The logical constraint is as follows: if $z \...
3
votes
1answer
163 views

How to express this logical constraint for an ILP?

I am trying to write an ILP for a problem but I have this logical constraint and I'm stuck. In my model I have: two binary variables: $x$ and $y$ One Integer variable: $z$ The logical constraint I am ...
3
votes
0answers
36 views

Linear functions in Lenstra's algorithm

I had asked this question at MathOverflow and was pointed here. I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to ...
1
vote
0answers
120 views

Resource constrained LP problem

I am working on Diet Allocation problem. Where we need to provide food piece for protein deficiency. The data is as below: ...
1
vote
0answers
317 views

Canonical form of a linear program

I have a linear programming problem that I want to write in the canonical form: \begin{align}\min&\quad c^\top X\\\text{s.t.}&\quad A\cdot X\le b\end{align} The problem is given by \begin{...
5
votes
1answer
549 views

Simplex Multiplier

I am reading through a book which provides an example of a linear program given by \begin{align}\min&\quad-24y_{1}-28y_{2}\\\text{s.t.}&\quad6y_{1}+10y_{2} \leq 2400\\&\quad8y_{1}+5y_{2} \...
6
votes
2answers
214 views

Linear objective function with non-linear constraints

I would like to choose a set of $\beta_j$s that maximizes a simple linear objective function of the type $$ \underset{\beta_j}{\operatorname{max}}\sum_{j=1}^{J}X_j\beta_j \\ $$ subject to the ...
2
votes
0answers
69 views

Finding Optimal Route using different Paths

I have a list of paths e.g. path 1 takes you from point A to B. A person needs to complete 5 of such paths. $$Route1 = path1 + ...
1
vote
0answers
43 views

Verifying the correctness of KKT conditions

I have a LP problem and derived the corresponding KKT conditions for the same. I simulated the LP and obtained the primal and dual values and manually checked if the KKT conditions hold. Is there any ...
5
votes
2answers
202 views

What is a general procedure to prove that the LP relaxation of an IP delivers the optimal IP solution?

Say that I have a binary IP $$z=\max_x \{c^\top x: Ax=b, x\in B^n\}$$ where $B^n$ is the set of $n$-dimensional $0-1$ vectors. Its LP relaxation will be $$z^{LP}=\max_x \{c^\top x: Ax=b, 0\leq x\leq 1\...
4
votes
2answers
203 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 ...
5
votes
1answer
187 views

Linearizing a constraint with square root of a variable

I am trying to linearize the constraint set (2) in the following simplified program. The parameters: $A,C,D,T\in\mathbb{R}^+$. The set $\mathcal{J}$ is polynomially-sized. \begin{alignat}2\min &\...
6
votes
1answer
93 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 ...
2
votes
1answer
43 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 ...
5
votes
2answers
178 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 \...
2
votes
1answer
149 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 ...
0
votes
1answer
57 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 ...
2
votes
1answer
163 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 ...
1
vote
0answers
57 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)?...
3
votes
1answer
357 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 ...
2
votes
4answers
84 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 ...
1
vote
1answer
88 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 ...
16
votes
1answer
925 views

Prove that these linear programming problems are bounded by $O(k^{1/2})$

Prove that these linear programming problems are bounded by $O(k^{1/2})$ Conjecturally the expanded partial sums of the Möbius transform of the Harmonic numbers have two out of three properties in ...
11
votes
2answers
681 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. ...
4
votes
1answer
306 views

PuLP Transport Problem - How to add outcomes of decision variables together

I am working on a rail scheduling problem that moves product from a production plant to a storage facility to satisfy demand. I am new to PuLP so finding this difficult to understand why this isn't ...
6
votes
0answers
65 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?
2
votes
0answers
64 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 ...
1
vote
2answers
376 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 ...
5
votes
1answer
133 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 ...
3
votes
0answers
43 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
4
votes
3answers
707 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 ...
3
votes
1answer
141 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$ ...

1 2 3
4
5
8