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
3 votes
0 answers
70 views

Identifying problem: Assignment + Job Shop Scheduling

I am new to OR. Hence, I want your advice on the problem I am trying to solve: Given: $O_1 \rightarrow O_2 \rightarrow O_3 \rightarrow ... \rightarrow O_n$: the sequence of operations to produce $1$ ...
user avatar
  • 139
3 votes
1 answer
118 views

Project task scheduling based on available budget per period

I have a challenge that is a bit backwards from the usual labour resource leveling problem. In my case I have a fixed budget pool over a period to deliver some of the work packages (not enough per ...
user avatar
  • 133
1 vote
1 answer
73 views

Help with dual of a problem

Could anyone confirm me if I write the correct dual for my problem? The different sets confuse me a lot. $s$ is the source node and $t$ the sink node. I'm uncertain if the last dual constraint in ...
user avatar
  • 313
6 votes
2 answers
419 views

What would be a representative/appropriate name for operations research?

Assuming you have a masters degree in operations research and this masters degree is offered in an economics department of your university. What would be a representative/appropriate name to describe ...
user avatar
3 votes
2 answers
120 views

How to input this LP model of a buffer allocation problem in Gurobi?

I am doing research on optimizing a simple buffer allocation and need to run my model. I am new to this but someone told me about using Gurobi and I do not for the life of me know how to create the ...
user avatar
  • 39
0 votes
1 answer
138 views

How to put this restriction using Gurobi in python

I am doing an optimization problem for the filling and extraction of a warehouse. One of the constraints is that the filling volume cannot exceed a given limit for one day: For example, on the 3rd of ...
user avatar
  • 27
3 votes
1 answer
60 views

Methods to solve integer linear inequalities with products of two variables

I'm interested in solving the following system of equations over the integers: \begin{align*} x_l^3 &\le x_l^1x_l^2 & \text{ for } l = 1,\ldots,s \\ A x &\le b \\ 0 &\le x \end{align*} ...
user avatar
  • 131
0 votes
2 answers
87 views

On the non-sufficiency of total unimodularity of the constraint matrix in the definition of an integer polytope

Is there an example of an $m\times n$ integer matrix $A$ and an integer vector $b\in \mathbb {Z}^{m}$ such that the polyhedron $P := \{ x\in \mathbb {R}^{n} \mid A x \leq b\}$ is integer, while $A$ is ...
user avatar
2 votes
3 answers
149 views

How to use condition in cplex?

I want to use conditions to my variable. dvar boolean x[I][J][K][L] dvar in h[i] my code is ...
user avatar
  • 21
2 votes
1 answer
105 views

How to formulate cumulative sum of LpVariable in Pulp Python

I have a Multiple product LP optimization problem in which the product(B1,B2,D) will be received in variable quantity with respect to date column. The Optimizer should LP variable Output as Assy Out ...
user avatar
1 vote
1 answer
77 views

Solving Graph Partitioning Problems with Gurobi and Pyomo

I am trying to solve a graph partitioning problem for a large number of structurally similar random graphs with an 0-1 LP. Most of these problems are solved within 0.x seconds. Some graphs take the ...
user avatar
  • 267
4 votes
0 answers
48 views

bilinear problem proof for NP-completeness of degeneracy check

In the paper "Some NP-complete problems in linear programming" (https://doi.org/10.1016/0167-6377(82)90006-2), there are several proofs given to show that testing for degeneracy in LPs is NP-...
user avatar
  • 533
6 votes
0 answers
55 views

Robust Linear Optimization for avoiding diminishing returns

My engineering problem can be formulated as an LP as shown below \begin{align} \max_{\mathbf{x}}~~&\mathbf{a}^T\mathbf{x} \\ \mbox{s.t.}~~~&\mathbf{b}^T\mathbf{x} \leq B~~,~~\mathbf{1}^T\...
user avatar
1 vote
0 answers
59 views

How to solve this problem with Gurobi add-in Opensolver excel

My main problem is that, when I try to solve an optimization using Gurobi with the OpenSolver add-in, I get the error that there is no feasible solution. To summarize, my variable $X_i$ has a maximum ...
user avatar
  • 27
5 votes
3 answers
779 views

how to "calm down" optimizer

I want to optimize a charging schedule for Battery Electric Vehicles (BEV) along a grid line, taking into account customer wishes (when to be done with charging with what State of Charge (SOC)) and ...
user avatar
  • 231
2 votes
3 answers
118 views

Warm starting ideas for iteratively solving a model with a few additional constraints

I'm trying to solve a MILP model iteratively, and at each iteration a few constraints are added to the problem that cut off the previous optimal solution. I'm trying to figure out ways to implement a ...
user avatar
  • 29
8 votes
4 answers
230 views

Common problems/puzzles that can creatively be solved with linear programming?

I am interested in common problems/puzzles that have a clear set of rules/constraints and objective that lends itself to modeled and solved with a linear program. Especially for people new to LPs, I ...
user avatar
  • 433
2 votes
1 answer
55 views

Load to ship assignment problem

Problem We’d like to optimize the delivery of loads across a network using a fleet of ships. Assume there is a set of $\mathcal{S}$ ships that need to deliver the set of $\mathcal{L}$ loads in a ...
user avatar
  • 129
0 votes
0 answers
62 views

Decision whether to serve the current table now or skip it

Can the following problem be formulated as a LP/IP problem, where an agent (waiter) that has just arrived at a certain table has to decide whether to visit that table now, or skip the current table ...
user avatar
5 votes
1 answer
95 views

Linearizing this absolute difference objective function $\min\sum_{i=1}^{I}\sum_{j=1}^{i}|x_i-x_j|$

For $x_i>0, i=1,\ldots,I$, I tried to linearize this objective function $$\min\sum_{i=1}^{I}\sum_{j=1}^{i}|x_i-x_j|$$ as $$\min\sum_{i=1}^{I}\sum_{j=1}^{i}y_{ij}$$ subject to \begin{align} & y_{...
user avatar
  • 406
2 votes
1 answer
62 views

How to optimize multiple linear regressions based on cost?

I have an optimization problem where I'd like to maximize revenue and I have separate variables for cost and revenue. Building a single unit of a product takes 100 hours of labor I have a list of ...
user avatar
  • 197
5 votes
1 answer
155 views

How to use max flow to schedule machines? (building a network)

Suppose you manage a machine shop with $k$ machines and have $n$ jobs to process today. Each job $i=1,2,3,4,5,\ldots,n$ requires $p_i>0$ minutes of processing time on any machine and has a ...
user avatar
7 votes
1 answer
232 views

Why are several of the decision variables zero at the corner point of a polytope?

I have the following equational Linear Program: \begin{align}\max&\quad c^T x\\\text{s.t.}&\quad Ax=b\\&\quad x\ge0\end{align} The matrix $A$ is $m\times n$, where $m\le n$, $c\in \mathbb{...
user avatar
6 votes
1 answer
96 views

Using CBC CLI Arguments in Pyomo

I am currently using the cbc solver with Pyomo opt = SolverFactory('cbc') opt.solve(model) How can more options for Cbc be used,...
user avatar
2 votes
1 answer
119 views

Defining Objective Function in PuLP

I have a binary variable $X_{ijk}$ which I have defined as the following : ...
user avatar
1 vote
1 answer
96 views

How to get negative shadow price for minimization problem in Gurobi?

I am currently working on a scheduling problem (MIP) to minimize cost, and my idea is to first generate a set of discrete initial solutions, and build an LP model with the discrete initial solution to ...
user avatar
  • 19
6 votes
1 answer
95 views

Light weight proof of strong duality in linear programming

For teaching purposes, I believe it can be good to use very light-weight proofs of deep results, as it often answers the question "why is it true" better than other types of proofs. By "...
user avatar
  • 5,347
3 votes
1 answer
73 views

Are there examples where introducing clusters of binary variables provides a benefit for solving?

I have a larger model with a large number of binary variables among many others. For the purpose of this question, consider the effect that the binary variables impose on the model to be similar to ...
user avatar
  • 303
5 votes
0 answers
76 views

Dual instability, degeneracy, tailing off effect - Which are the causes and which are the effects?

Dual instability, degeneracy, and the tailing off effect are often mentioned together in papers. However, I cannot seem to find a clear explanation on which of these cause the other and vice versa? ...
user avatar
  • 389
3 votes
4 answers
284 views

How to see constraint violation for network flow problem

I am testing to see if my network is balanced as part of a larger protection-interdiction-restoration problem. To do this, I'm solving the problem as a minimum cost network flow problem to see if the ...
user avatar
3 votes
1 answer
60 views

LP Objective function for distributing workload

In this example, we have a group of students that each needs to be paired with a teacher. Each student has a different number of questions to ask the teacher, and each student-teacher pairing has a ...
user avatar
4 votes
1 answer
312 views

Difference between solving Assignment Problem using the Hungarian Method vs. LP

When trying to solve for assignments given a cost matrix, what is the difference between using Scipy's linear_sum_assignment function (which I think uses the ...
user avatar
1 vote
0 answers
41 views

Indexing weeks in MILP: better to have 12 weeks, or 3 months at 4 weeks each?

As a general rule, when building decision variables, is it computationally preferable to index along fewer dimensions instead of more when the count of permutations are identical? For context, I'm ...
user avatar
2 votes
0 answers
55 views

Pyomo optimisation not working (gas plant dispatch)

background I am trying to write an pyomo script to optimally dispatch a gas plant based on perfect foresight of electricity prices. I believe I am 90% of the way there, just a few issues. Problem The ...
user avatar
2 votes
0 answers
72 views

Are these LP equivalent?

This follows from a previous post of mine (see also). In that post I assumed that there existed no pair of rows (denoted $\mathbf x^i$) such that $\mathbf x^{i'}\geq\mathbf x^i$. I believe that I can ...
user avatar
  • 591
5 votes
1 answer
242 views

Writing a specific MILP problem

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 ...
user avatar
  • 215
3 votes
1 answer
110 views

Benders decomposition feasibility/ optimality cuts

I am trying to understand Benders Decomposition method. I am reading this book Decomposition techniques in mathematical programming by A Conejo, E Castillo, R Minguez. The book provides an example of ...
user avatar
  • 223
-5 votes
1 answer
106 views

How to make Gurobi solve huge LP/IP model with only using A,b,c matrices?

I work on the scaling of MIP. I have scaled the A,b,c matrices of the huge original model. These matrices have more than 25000 rows and columns. I need to make Gurobi solve the scaled model. Normally, ...
user avatar
  • 105
2 votes
1 answer
35 views

How does a ratio of fixed cost to variable cost affect the problem difficulty?

I am working on an OR scheduling problem where OR opening cost is considered a fixed cost when a surgery is scheduled. If OR is used beyond a certain time, overtime cost is incurred. I would like to ...
user avatar
6 votes
3 answers
122 views

Linear Programming problem for finding supplier

I have a linear programming problem in front of me that I am searching to solve in R (any package), seems like an unbalanced assignment problem to me with relaxed constraints on columns (repeated ...
user avatar
  • 183
7 votes
4 answers
806 views

is prime? in Operations Research

Is there a way to linearize is prime? in Operations Research? is prime(n) being true if $n$ is a prime number or false otherwise....
user avatar
  • 533
7 votes
2 answers
298 views

how can I modify my LP to activate the most constraints possible?

Suppose I have a linear program (LP) that has many optimal solutions. Of those optima, I want to find the optimum that activates (aka, "pegs" or "bumps") the largest number of ...
user avatar
  • 533
2 votes
1 answer
81 views

What is the dual of this LP?

Here is my simple LP problem for a constant symmetric positive matrix $d$ and continuous decision variables $x$: \begin{align}\max&\quad\sum{x_i}\\\text{s.t.}&\quad x_i + x_j \leq d_{ij}\\&...
user avatar
  • 533
3 votes
1 answer
124 views

Will all constraints in this LP be binding?

This is a follow up to my previous questions here and here . I've added the assumption that $m=2$. Say $\mathbf{X}$ is a $n\times 2$ matrix with no negative entries and such that every row and every ...
user avatar
  • 591
1 vote
1 answer
67 views

Will constraints in this LP be satisfied as equalities?

This is a follow up of my previous question. I repeat it below with an additional condition (in italics). Say $\mathbf{X}$ is a $n\times m$ matrix with no negative entries and such that every row and ...
user avatar
  • 591
4 votes
1 answer
82 views

Minimum up time for a machine in a linear program?

If we let $x_i$ = 1 if a machine is on during hour $i$, and 0 if the machine is off, how would we enforce a constraint that requires the machine to be “on” for a minimum of at least $M$ hours? For ...
user avatar
  • 433
1 vote
1 answer
48 views

When will constraints in an LP be satisfied as equalities?

Say $\mathbf{X}$ is a $n\times m$ matrix with no negative entries. Assume further that every row and every column have at least a non zero element. Denote $\langle\mathbf{X}\rangle$ the cone spanned ...
user avatar
  • 591
4 votes
2 answers
241 views

Python Pulp - LpMinimize Not Returning Expected Output - Scheduling Problem

I'm working on my first pulp model and something isn't going quite right. It looks like it's close, but for some reason it is not respecting one of my constraints... It's a scheduling problem and I am ...
user avatar
  • 63
10 votes
2 answers
224 views

The First Ever Linear Programming Problems

I have heard that Linear Programming was first used by: Dantzig to solve problems involving US military logistics in the Second World War Kantorovich to solve problems involving transportation of ...
user avatar
  • 1,839
4 votes
1 answer
166 views

Why is it called the "Simplex" Algorithm/Method?

I have been trying to learn more about the Simplex Algorithm/Method. In particular, I am interested in knowing why this algorithm is called the "Simplex Algorithm". For instance, when ...
user avatar
  • 1,839

1
2 3 4 5
10