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
1 vote
1 answer
82 views

Metaheuristics or Exact algorithms to solve a non-linear multi-objective optimization problem?

The multi-objective optimization problem settings are as defined below: Objective 1: Minimize $f_1(X_1,X_2)=C_0+C_1(1/X_1)+C_2(X_2/X_1)$ Objective 2: Minimize $f_2(X_1,X_2)=D_0+D_1X_1+D_2X_2+D_3(X_2/...
vp_050's user avatar
  • 179
1 vote
1 answer
119 views

Constraints to avoid disjointed solutions in a MIP

Given an directed graph $G= (N,E)$, where $N$ is the set of nodes and $E$ is the set of all edges, each associated with a direction. $G$ is a connected graph but not necessarily a complete graph. A ...
CHE's user avatar
  • 113
1 vote
1 answer
96 views

MILP - Find out model size

Ucame across a paper today and this paper mentioned that the model size is $O(\mid I\mid\cdot\mid T \mid)$. I am also sitting on a MILP problem right now. Does my model size also amount to this size ...
Karl Seidl's user avatar
1 vote
3 answers
226 views

MIP constraints with chronological ordering

I am using a MIP formulation to decide which dates and locations (i.e. stops) should be chosen for a route that maximizes the total revenue over all chosen stops. My decision variable $X$ is the ...
3Li's user avatar
  • 35
4 votes
1 answer
388 views

Is Benders decomposition and the L-shaped method the same algorithm?

I've been studying the Benders decomposition method to solve stochastic integer problems. I've also stumbled across papers using a so called L-shaped-algorithm which also divides into master problem ...
Arctic_Skill's user avatar
2 votes
1 answer
521 views

Runtime of LP vs MILP

I was wondering how the run time of an LP and an MILP model compare to each other. I found out that MIPs are NP-hard, where as LPs aren't, but it don't really understand what it means. Does that mean ...
lukdooxb1's user avatar
3 votes
1 answer
102 views

Modify objective function for equal solution distribution

I have the following question. I have a LP with the objective function. $\max\sum_{i\in I}^{}\sum_{p\in P}^{}sales_{ip}$ Here, the number of sales over all individuals $i$ is to be maximized for all ...
lukdooxb1's user avatar
0 votes
0 answers
107 views

CVXPY stuck in Compilation step during solving linear program

I'm trying to solve a linear program with 869532 variables and 8869 constraints in CVXPY. The CVXPY gets stuck in the Compilation session right before passing the problem to the solver. Here's the ...
Mohammad Namakshenas's user avatar
7 votes
1 answer
627 views

How can one model a binary variable?

I am looking for the formulation of a constraint that does the following. I want to introduce a new binary variable $\kappa_{it}$ that takes the value 1 if the sum of the other binary variable $\...
nflgreaternba's user avatar
2 votes
0 answers
76 views

When do two integer linear programs yield the same solution?

This question is cross-posted from math stack exchange An illustrative example Consider an integer linear program $\min -2x_1 + x_2$ subject to $x_1 - x_2 \leq 3$ and $x_1 + x_2 \leq 10$ and integer $...
fool's user avatar
  • 121
2 votes
1 answer
136 views

Conditional constraints in MILPs

I want to understand how to represent iff constraints in MILPs. For example, I want to represent the following as the constraints of a MILP $$ c = \begin{cases} 1 &\text{if } d \geq e \\ 0 & \...
Anonymous Bunny's user avatar
0 votes
2 answers
111 views

Modelling a binary variable in LPs

I need your help. I'm setting up an LP and I'm trying to find constraints to introduce the binary varibale $b_{ij}$. So it should take the value 0 if the sum of all $a_{ij}$ values to the period t are ...
Karl Seidl's user avatar
-1 votes
1 answer
77 views

Literature for the Big-M constraint method

I've come across the possibility of introducing binary variables in linear programming with the Big-M method here several times now. Here is an example: \begin{align} &(1-x_{i})\le \sum_i y_i\\ &...
marvelfab12's user avatar
2 votes
2 answers
135 views

Transportation Problem

I want to create a transportation model. I have identified importing and exporting countries with their estimated demand and supply. The cost of transportation per one uni is already calculated for ...
user avatar
-1 votes
1 answer
64 views

How to set an objective to minimize the variance in ratio of allocation

I am trying to write a model where I have to distribute fractions of rent from properties to loans. The objective is to distribute the rents as equally as possible given the loan balance. Say there ...
Ashok Khatri's user avatar
0 votes
1 answer
239 views

LP - How to model binary variable that indicates a switch

I have the following question / concern. I have a modeling problem with the decision variable $d_{ptm}$ which indicates whether product $p$ was serviced by machine $m$ in period $t$. It takes the ...
marvelfab12's user avatar
-1 votes
3 answers
196 views

Multi objective optimization is giving wrong results

I am trying to solve a multi objective optimization problem. I have a set of nodes belonging to different counties and each node is associated with some cost and some priority. I want to select the ...
MSS's user avatar
  • 111
1 vote
1 answer
49 views

How to sum over periods till Period t?

I am trying to set up a constraint that does the following. I a binary variable $p_{it}$ that indicates whether a student $i$ passed the test in $t$. 1 if yes and 0 if no. Now I want to set up a ...
nflgreaternba's user avatar
0 votes
1 answer
59 views

Help finding linear constraint - LP

I have the following question. I have two variables $w_{nds}$ and $m_{nd}$. The first variable indicates whether a nurse $n$ works shift $s$ on day $d$. The second one indicates the motivation of ...
nflgreaternba's user avatar
4 votes
1 answer
92 views

Nurse Rostering constraints - LP

I am fairly new to linear programming since I came across this topic at university this semester. We mainly focus on nurse rostering. In the lecture, we created a very basic rostering model with an ...
nflgreaternba's user avatar
0 votes
2 answers
136 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, ...
mingabua's user avatar
2 votes
1 answer
247 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 ...
Abilash's user avatar
  • 63
2 votes
1 answer
175 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 ...
Asheesh's user avatar
  • 23
1 vote
1 answer
152 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. ...
Adri's user avatar
  • 11
0 votes
1 answer
97 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 ...
Eslam Mahmoud's user avatar
4 votes
1 answer
164 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 ...
Kuifje's user avatar
  • 13.3k
3 votes
3 answers
417 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$ ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
122 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 ...
Bohdan's user avatar
  • 3
1 vote
1 answer
123 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} ...
Cris's user avatar
  • 143
0 votes
1 answer
155 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 ...
Coo's user avatar
  • 121
1 vote
1 answer
575 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 ...
Nguyen Quang Anh's user avatar
1 vote
1 answer
177 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'...
Joao Branco's user avatar
0 votes
0 answers
117 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 ...
A Y's user avatar
  • 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 ...
cookmeplox's user avatar
0 votes
1 answer
90 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 ...
Optimization team's user avatar
5 votes
2 answers
293 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 ...
Joris Kinable's user avatar
1 vote
2 answers
166 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, ...
Nate's user avatar
  • 113
0 votes
0 answers
41 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 ...
user11638's user avatar
1 vote
3 answers
87 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 ...
3Li's user avatar
  • 35
0 votes
1 answer
384 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$. ...
graphtheory123's user avatar
2 votes
2 answers
108 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 ...
TroyE219's user avatar
  • 105
2 votes
1 answer
150 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, ...
West Wind's user avatar
5 votes
3 answers
440 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 ...
Sidharth Ghoshal's user avatar
3 votes
2 answers
701 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 ...
Red shoes's user avatar
  • 133
0 votes
1 answer
138 views

Optimal blending of gasoline via LP

...
N_ote's user avatar
  • 11
1 vote
1 answer
187 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?
Waldo's user avatar
  • 19
0 votes
1 answer
82 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,...
Kiran Kumar S's user avatar
1 vote
0 answers
94 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. ...
funkypenguin's user avatar
1 vote
2 answers
83 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 ...
Meth's user avatar
  • 424
1 vote
2 answers
84 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 ...
John D's user avatar
  • 199

1 2
3
4 5
17