# Questions tagged [linear-programming]

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

352 questions
Filter by
Sorted by
Tagged with
242 views

### Multi-period linear dynamic programming with differing in-period dependencies and changes

I’m not sure if I’m wording this right but in a nutshell, my problem is: I’m modelling potential actions a boat owner can do to their boat. Let’s say he wants to know over the 50 year lifespan of the ...
103 views

### Minimum value for a group of variables in linear programming

I want to use linear programming to assign weights to a number of groups of variables. Let's assume we have group $A$ with $x,y,$ and $z$ and group $B$ with $m,n,$ and $p$. Is it possible to define ...
114 views

### Maximizing a Ratio/Percent

I'm using cvxpy to model a problem. Inside a very large and complex LP, I create two continuous, affine (unconstrained) expressions: $x$ and $y$. Due to how they ...
149 views

### Derive “true” shadow price for degenerated LPs using commercial solvers (e.g. Gurobi)

In linear programming for an optimal primal degenerate solution the values of the dual variables are in general not identical with the corresponding shadow prices. Several proposals on how to find the ...
281 views

### Can GLPK be used to solve an optimal team selection problem?

My Problem I am quite new to optimisation, so any advice is appreciated. I am currently trying to solve a problem as follows: Given a pool of people, we want to create n teams such to find the optimal ...
91 views

### Which method to use to solve this multi-objective conflicting objectives

I have the following multiobjective problem. I need to minimize the user-perceived latency while doing so aggressively minimizing user-perceived latency generates large switching cost (Reconfiguration ...
40 views

### Finding bounds on a data sensitivity scenario ILP problem

This is a follow up to a problem I posted here: Modelling a data-sensitivity scenario as an ILP problem As a recap, I was interested in finding the minimum number of cells that need to be suppressed ...
96 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 ...
181 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 ...
97 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 ...
76 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 ...
83 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 ...
91 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 ...
108 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 ...
80 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 ...
118 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 ...
98 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 ...
147 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 ...
106 views

153 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 ...
34 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 ...
55 views

### Min-cost flow with per-edge flow conservation

I am trying to solve a linear program that is identical to a min-cost flow problem, except for a difference in the flow-conservation constraint. Instead of the summed outgoing flow equaling the summed ...
205 views

### Faster implementation of “or” constraints in ILP

I have implemented a set of "or" constraints in my ILP using binary decision variables (as in this method). It works fine for smaller problems, but when I try to increase the number of ...
117 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: ...
517 views

311 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{...
1k views

### How to find all vertices of a polyhedron

I have a convex polyhedron given by a set of linear inequalities, for example: $$x_1 \geq 0,~~ x_2 \geq 0, ~~x_3\geq 0 \\ x_1+x_2\leq 1,~~ x_2+x_3\leq 1,~~ x_3+x_1\leq 1$$ I want to list all the ...
107 views

### Find a particular optimal solution

After writing an integer linear program in AMPL, I solved it using CPLEX. Now, I have some variables that must necessarily be 1, others that must necessarily be 0 and finally it is possible that some ...
42 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 ...
67 views

167 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 &\...
92 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 ...
42 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 ...
198 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 ...
55 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 ...
174 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 \...
147 views

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

Given the table ...
133 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 ...
152 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 ...
51 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)?...
289 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 ...
83 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 ...