Questions tagged [linear-programming]
For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.
686
questions
0
votes
2
answers
30
views
Linear Programming - Model understaffing
I am reading up a bit on Linear Programming and have taken a lot from "Scheduling Emergency Room Physicians" (by Michael W. Carter & Sophie D. LaPierre, Health Care Management Science 4, ...
- 31
2
votes
1
answer
21
views
LP Sensitivity Analysis with multiple simultaneous changes
TLDR: When doing sensitivity analysis (specifically the objective coefficients), there maximum allowable increase and decrease before the solution changes is only valid when a single coefficient ...
2
votes
1
answer
90
views
Find the minimum number of equipment required for a service period
I'm starting to learn operations research and trying to get my head around this problem that I have.
Problem statement: Find the minimum number of equipment needed to run a service schedule.
There are ...
- 21
1
vote
1
answer
95
views
Conditional Statements in an LP model
I am currently working on a large workforce/manpower planning model for an aviation company. This model should decide whether to hire a new pilot or to let pilots fly overtime.
It has two skillsets. ...
- 11
0
votes
1
answer
74
views
Mixed Integer Programming - How to model a term in objective function with a constant multiplied by (1-Decision Variable)
I am solving an optimization problem, where I want to minimize the objective function
$$Z = \sum_q \left(D_q \text{fare}_q - \sum_{p \ne q} \Delta D^p_q \text{fare}_q \right) (1-Z_q)$$
Each $q$ is an ...
4
votes
1
answer
90
views
What are some good references of OR techniques applied to revenue management?
For teaching purposes, I am looking for some nice examples of revenue management problems which are tackled with optimization techniques, ideally linear programming (including MIPs).
For example, this ...
- 12.3k
3
votes
3
answers
225
views
Upper bound on length of solution of linear program
Consider the linear program:
$$\text{maximize} ~~ c\cdot x \\ \text{subject to} ~~ A\cdot x\leq b, ~~x\geq 0.$$
Suppose $A$ is an $m\times n$ matrix, $b$ an $m\times 1$ vector and $c$ an $n\times 1$ ...
0
votes
1
answer
103
views
Determine the daily production program that maximizes the company's output
The problem:
The mechanical workshop can produce $600$ units of part #1 or $1200$ units of part #2 per shift. The production capacity of the thermal workshop, where these parts are sent for heat ...
- 3
1
vote
1
answer
100
views
Rational LP, its Rational solution and a minimum precision
Suppose we have an LP with rational coefficients.
To my knowledge, this implies that the optimal solution to that LP is also rational. In other words, every variable may be written as:
$$x_{i}^{\star} ...
- 143
0
votes
1
answer
98
views
How to formulate the minimum and maximum range of possible values?
In Store $X$, shelf 1 accounted for $\frac{1}{4}$ of Bakery $C$ 's average weekly sales and shelf 2 accounted for $\frac{2}{3}$ as much as shelf 1 . If shelves 3 and 4 each accounted for less than ...
- 121
1
vote
1
answer
65
views
Sign of the reduced cost in LP
I'm new to operation research. I'm confusing about the sign of reduced cost and I have a few questions that I'd like to ask. Suppose that I solve a maximization problem, considering a variable x with ...
1
vote
1
answer
55
views
Python and GLPK to solve Linear programming problem (infeasible solution)
I'm using Python and the GLPK Solver to find recommendations for an infeasible problem.
I'm optimizing for price, and this is the problem data:
Define problem data
foods = ['Food 0', 'Food 1', 'Food 2'...
- 13
0
votes
0
answers
84
views
Dual of a LP with a variable restricted to be negative
I have to find the dual of following LP:
Minimize $ x_1 + x_2 + x_3$
subject to
$4x_1 + 8x_2 \geq3$
$7x_2 + 4x_3 \leq 6$
$3x_1 - 2x_2 + 5x_3 = 7$
$x_1 \leq 0, x_2 \geq 0, x_3$ is unrestricted
I ...
- 1
6
votes
4
answers
2k
views
Linear programming, except each "thing you can spend time on" has its own feasible region/requirements
In a game I am trying to optimize for, the goal of the game is to get each of your 23 "skills" to exceed a certain amount of "experience" in the shortest time possible. There are ...
- 61
0
votes
1
answer
84
views
How to identify which node is serving each customer?
I have a linear programming problem. There are two questions:
Consider 2 centers (1,2) that should serve clients [s,b,c,t], What it the minimum distance cost. The formulation is straight forward.
The ...
- 1,120
4
votes
1
answer
154
views
Separating violated cover inequalities
Consider a knapsack problem with binary variables and a standard knapsack constraint $\sum_{j\in N}a_jx_j\leq b$.
A set $C\subseteq N$ is a cover if $\sum_{j\in C}a_j >b$
If $C\subseteq N$ is a ...
- 3,207
1
vote
2
answers
107
views
Minimal infeasible constraint set
Many modern SAT and SMT solvers offer a feature where they can report why a problem is unsatisfiable, something called an "unsat core."
Are there any optimization solvers (in my case, ...
- 113
0
votes
0
answers
30
views
Dual prices remain stable but negative in column generation
I arrive at an objective function value that I know to be optimal. However, dual prices remain negative (which leads me to believe another pattern can be added, but when I do, the dual prices don't ...
1
vote
3
answers
61
views
PuLP ensure first and last choice
I have an assignment problem where I have $N$ locations and $M$ dates for each location, and the goal is to choose $K$ location-date pairs that maximize revenue. There are a number of constraints, for ...
- 23
0
votes
1
answer
61
views
How to formulate an MIP so that a binary variable is 0 or 1 depending on whether another variable is nonzero?
I have a binary indicator variable $i \in \{ 0, 1 \}$ and an integer variable $c \in \mathbb{Z}$.
I am trying to come up with a formulation in which $i = 0$ if $c = 0$ and $i = 1$ if $c \neq 0$.
...
- 143
2
votes
2
answers
78
views
Small negative decision variable returned in Gurobipy model
I have a multi-period model in gurobipy with 7 types continuous decision variables and 1 type of binary (Thousands indexed total). The model solves properly and the solution has passed many validation ...
- 105
2
votes
1
answer
103
views
Must the Newly Generated Column be used in RMP in the Column Generation Method?
When I used Column Generation, I found a column with reduced cost < 0, and added it to the Restricted Master Problem.
Must the newly added column be used in the solution of RMP at once? If not, ...
- 21
5
votes
2
answers
119
views
What are my options for exact linear programming solvers in python3 that work as of April 2023?
So a while back I had asked this question: Is there a Linear Programming Library that natively supports fractions instead of floating point arithmetic?
And basically the overwhelming consensus was ...
- 359
3
votes
2
answers
635
views
Writing a constraint of an integer programming in a linear form
I modeled an optimization problem in an integer programming format. The main constraint I came up with is now nonconvex. I would like to see if there is another equivalent formulation in which the ...
- 133
0
votes
1
answer
80
views
1
vote
1
answer
118
views
Linearize conditional constraint
Consider a variable c from the domain {-1,0,1}. I have the following constraint:
IF $c = 1 \Rightarrow x = 1 $ ELSE $x = 0$
How do I linearize this constraint?
- 21
0
votes
1
answer
35
views
Array of string in OPL
how to make 2d array of strings in Cplex
//indics
{string} cluster=...;
setof(string) darkstore =...;
setof(string)demandpoint =...;
//data
cluster={chav,sree};
demandpoint=[{tsnami,adholokam,...
1
vote
0
answers
51
views
How to speed up state of charge constraint in Pyomo model
Context: I am working on a small electricity market model in Pyomo. It optimizes the capacity of different technologies and generation in at least 43800 hours. One of the technologies is a battery. ...
- 11
1
vote
2
answers
82
views
Solver is not convering
I have cars and persons and I want each persons to be in a car.
Moreover, each person has a number of persons they can share a car with.
I have implemented a model (with binary variables and constant ...
- 424
1
vote
2
answers
61
views
How to tackle online scheduling problems?
In scheduling problems, one usually has different options as objective functions (makespan, tardiness, etc). However, for any such type of scheduling problem one can consider an online version of it ...
- 199
0
votes
0
answers
35
views
Is Converting to Standard Form Necessary to Check if a Proposed Solution is a Basis in Linear Programming?
If I have a Lp problem should I make it to standard form and then calculate number of 0s in the proposed solution and compare it to :
number of equation - number of variables;
And that's for checking ...
1
vote
1
answer
80
views
Solver for Flexible Job Shop Scheduling Problem
I have a FJSSP that I would like to solve. However, the jobs in this problem have deadlines and in addition there are setup times between two jobs. Because of this, my objective function is not just ...
- 199
2
votes
1
answer
74
views
Obtaining the dual ray of an infeasible lp to generate a benders feasibility cut
I am struggling to correctly interpret the meaning of a dual ray for an infeasible primal lp.
Consider the following example.
$$
\min z = y_1 + y_2 -2y_3
$$
s.t
$$y_1 -2y_1 -y_3 \ge 3 $$
$$-2y_1 - ...
- 21
1
vote
4
answers
116
views
How to perform clustering of a large number of nodes?
I have a clustering problem with around 400-500 nodes. The edge between any two nodes has a weight (between 0 and 1, 0: can be considered as there is no edge/connection between these two nodes) as ...
- 2,191
0
votes
0
answers
26
views
When Supply < Demand - distributing resources v/s meeting as much demand
In network modelling LP , when Supply < Demand and we use normal balance of flow rule for all the constraints, i.e. (inflow - outflow) <= supply or demand, we say we are trying to redistribute ...
1
vote
1
answer
50
views
Linearize constraints on a truncated variable
Let $K$ and $Q$ be two variables, and $Q_\min$ and $Q_\max$ be two parameters. I need a series of linear constraints to define $Q$ vis-a-vis the value of $K$ based on the following rules:
If $K \le ...
- 11
0
votes
0
answers
52
views
Multi-Scenario Gurobi Python Output
I have an lp and am trying to solve multiple scenarios at once. One of my scenarios is infeasible though this is not the issue.
For some reason, when I print m.status, both solutions have a status of ...
- 105
1
vote
1
answer
123
views
Solver for quadratically constrained mixed-integer linear programs
I have an optimization problem with vectors $x$, $y$, and $z$, where $x$ is an integer vector. My objective function is linear (i.e. $\|y\|_1$), but one of my constraints is quadratic ($x^Ty \leq z$). ...
- 183
1
vote
1
answer
69
views
Single item unconstrained lot-sizing with multiple suppliers and minimum order quantities
Variation of the traditional lot-sizing problem - with some additional complexities:
multiple suppliers (S1, S2, S3), with different procurement lead-time
Suppliers have to be allocated based on a ...
- 119
3
votes
2
answers
148
views
How to find the maximizing number of expected delivered units of a probabilistic minimum cost flow problem?
I am a Bitcoin / Lightning Network open source developer and researcher and new here but very active on the sister site. In the context of my research I discovered the field of operations research ...
- 131
2
votes
1
answer
131
views
Reduced cost fixing for binary programs
Consider the binary program
$$ \min_{ x \in \{0,1\}^N } \left\{ c^T x \mid Ax \leq b \right\}$$
where $A$ and $b$ are real matrices with appropriate dimensions. I am interested in solving large binary ...
- 41
1
vote
0
answers
34
views
Budgeted uncertainty on the RHS
Suppose we consider budgeted uncertainty (Bertsimas and Sim, 2002) for the following scenario. We have a binary decision variable $x_{i,j}$, where $i \in I$ and $j \in J$ (two sets). We then have the ...
- 392
-2
votes
1
answer
62
views
Mixed Integer programming - Problem modelling coincidence restriction in scheduling match problem
I am trying to model and solve a problem for maximize audience of matches that must be scheduled in different slots (I am using python PulP library). Below I explain the problem and the model process ...
- 19
2
votes
3
answers
244
views
Identifying the minimum number of required machines to schedule jobs
I am relatively new to the topic of optimization. I am currently trying to address the following problem:
We are given a set of jobs, say $J$ with release times, deadlines and duration. Jobs can be ...
- 392
2
votes
0
answers
28
views
Recoverable Robustness for an optimization problem
I am relatively new to the concept of recoverable robustness. I am researching the robust version of an optimization problem. I currently have methods to address the problem with perfect knowledge. ...
- 392
1
vote
1
answer
107
views
Mixed Integer Programming - How to model objective function with variables that depends on the solution? [duplicate]
I am modelling an optimization problem that is described as follows:
I would like to maximize audience for scheduling matches. There are n eligible teams and n/2 different slots.
Teams will only play ...
- 19
1
vote
1
answer
59
views
Scheduling tasks to minimize the total number of utilized cores
I currently have a scheduling algorithm which computes an approximate solution, say S, for the nominal scenario of a given problem instance, say N. Given that N changes in a way and becomes infeasible,...
- 392
0
votes
0
answers
55
views
Gamma uncertainty in the RHS of a constraint
I am new to the concept of robust optimization.I am trying to formulate the robust variation of a Binary Integer Program. Suppose we have a constraint of the form $\sum{x_{i,j}} \geq b_j$ for $ i \in ...
- 392
2
votes
1
answer
70
views
Separation oracle gives optimisation
Suppose I want to minimize a linear function $f$ over a convex set $K$ and I have only access to a separation oracle, that is, given a point, the oracle returns yes if the point is in $K$ and ...
- 121
5
votes
1
answer
189
views
Short cuts when using the simplex algorithm
I haven't really kept myself up to date with research on the simplex algorithm for several years. I have taught linear programming, but it has not focused on the cutting edge of things.
I remember ...
- 6,072