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

Mixed Integer Linear Programming

I don't know if this is appropriate and accepted here, so I apologize in advance. I just really need help in a problem that I've been working on for months now. Is someone up to help me create a model ...
1 vote
1 answer
39 views

Converting a function composing of multipe pieces into a linear equation

I have a variable (alpha) which depends on some other binary variables, denoted as X_i. So, for some combination of other variables, alpha may take a value (Beta_j). I added some auxillary variables (...
2 votes
1 answer
57 views

What approximation is guarantees when solving an LP with floating-point numbers?

Given a linear program $$\begin{align} \text{maximize} \quad & c^{T}x \\ \text{s.t.} \quad & A x \leq b \end{align} $$ I can solve it exactly in polynomial time, using e.g. interior-point ...
0 votes
0 answers
32 views

Need help with understanding LP and ILP modelling

Hoping someone may be able to point me in the right direction. Im looking more for a "Tutor" to help with my Uni work. I am struggling to grasp LP, ILP and NLP concepts. The only part I seem ...
1 vote
1 answer
70 views

How to track the first timestep at which a binary variable becomes 1 in an IP? [duplicate]

I have an MIP where I have a binary variable $y_t$ which is set to 1 or 0 and is indexed by time t. It can be set to 1 at multiple timestamps but it is never continuously 1 for more than single ...
1 vote
1 answer
68 views

A tool for finding integer solutions to linear systems

I have a system of linear equations $A x = 0$, where $A$ is an integer matrix, and I want to find a non-zero solution, if it exists. In that case, a rational solution exists. Multiplying by the common ...
1 vote
1 answer
75 views

How to model $\max\limits_{x\in X} \min\limits_{y\in Y} \max\limits_{z\in Z} f(z)$ as single MILP

I have the following optimization problem: \begin{align*} \max\limits_{x\in X} &\min\limits_{y\in Y} \max\limits_{z\in Z} & f(z) \\ &\text{such that} & (x, y, z)\in P \end{align*} ...
2 votes
1 answer
83 views

Why this ILP and LP are equivalent?

Let's consider a competition with $n$ questions. Each question has a price $p_i$ and a score $v_i$. To advance to the next round of the competition, we need to accumulate a minimum score of $D$. We ...
4 votes
3 answers
316 views

How to maximize the number of variables with value at least 0?

Given a matrix $A$ and a vector $b$, I would like to find a vector $x$ satisfying the set of linear constraints $A x \leq b$, and subject to that, contains as many variables as possible with ...
4 votes
3 answers
710 views

Clustering points based on a distance matrix

Although I asked this question on stackoverflow to possibly reach a broader audience, I wonder your inputs about this problem. Without giving much research into this, I thought p-center problem ($x_{...
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$ ...
1 vote
1 answer
100 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 ...
1 vote
1 answer
60 views

Fast Algorithms for Min-cost Multicommodity Flow Problem with Most Arcs Having 0 cost

I have a min-cost multicommodity flow problem with the following characteristics: Flows can be fractional (integer flows not required) Set of commodity types is $K$, set of demand nodes is $\\{ d_k : ...
0 votes
0 answers
45 views

Solving convex separable programming problem using interior point method?

In my engineering application, all decision variables are non-negative and everything is convex separable. In addition to that, the only function that I am trying to approximate with grid point are $f(...
1 vote
1 answer
64 views

Economic interpretation of shadow/dual variables in LP

I have recently read a text which deals with the dual variables attached to constraints. In an economic sense, one can interpret them as shadow variables indicating market clearing for resource ...
1 vote
1 answer
59 views

Linearizing a quadratic constraint

I am working on a quadratic conic optimization problem, but I have discovered that it would be preferable if the quadratic constraint is linearly approximated. In other words, I need some way to make ...
1 vote
1 answer
877 views

How to obtain reduced cost in the graphical sensitivity analysis?

According to some tables in the book Operations Research by Hamdy Taha(7th edition), it seems that for a variable whose optimal value is zero, reduced cost can be evaluated by the following formulas: ...
0 votes
2 answers
121 views

Converting a piecewise function to linear equations

I am trying to build a MILP model. In this model, I have a dependent variable (alpha) that its value depends on the value of some other variables (or different combination of some other variables). In ...
1 vote
1 answer
188 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 ...
1 vote
1 answer
59 views

How to write a constraint to find the index of the min value in a set?

Consider this example with set A={100,50,150}. Min value in this set is 50. How to find out that the index of 50 is 2 in this set? I need 2 as the answer to put it in another constraint
0 votes
0 answers
120 views

Detect presolve status in pulp model

I am running a model using pulp CBC and have few constraints in the model that may make the model infeasible if wrong input is given to the model. I can see while my model runs that in case of ...
8 votes
1 answer
279 views

Workforce Scheduling problem - Modelling to minimize resources

I am working on a scheduling program for a service desk. I want to decide the number of people required to come in at each shift. The data I have is: There are 4 overlapping shifts Arrival pattern at ...
1 vote
1 answer
62 views

Connections between Bounds in MIPs

we are currently learning about MIP/MILP minimization at university and have become familiar with the branch-and-bound algorithm. Unfortunately, the relationship between upper bound, lower bound and ...
0 votes
2 answers
72 views

How to write a If then else constraint with continuous variables

I have a problem under investigation which requires if, elseif and else conditions to implement as a constraint in a mixed integer program. Any leads will be appreciated. Thanks a lot. Let $x_t$, $y_t$...
0 votes
1 answer
76 views

Scheduling optimization problem - Where to begin?

Class Scheduling Optimization for a Trade School We are exploring ways to model, simulate, and optimize class scheduling for a trade school, focusing on addressing the complex dynamics of managing ...
1 vote
0 answers
36 views

How to convert unit-capacity network flow into transportation problems?

I am working on a problem that can be modeled as a minimum-cost network flow problem where the capacity of edges is 1. I found Exercise 3.8, Chapter 5 of Parallel and Distributed Computation: ...
3 votes
1 answer
417 views

How to modify master problem and individual sub problems in column generation?

This is a follow-up post regarding this one. I deleted this new post once before, as I was unhappy with the formulation. I have the following basic nurse scheduling MILP, which tries to cover the ...
1 vote
1 answer
47 views

Cplex no solution but no conflict

I am solving a problem using benders decomposition. The master problem is solved by cplex.The subproblems are logic and can be solved without using cplex solver. The scale for subproblem is large. ...
1 vote
1 answer
83 views

Dual to Primal conversion

I recently tried to solve a primal minimization problem using its maximization dual. In the optimal simplex tableau of the dual, there was a slack variable and only one dual variable in the basis. So, ...
0 votes
0 answers
53 views

How to initialize a parameter (belonging to the first stage model) in a two stage model, taking its value from second stage model?

I am working on a two stage approach in order to reduce the complexity of a scheduling model which is an NP-hard problem. I have to implement a while loop in order to repeat solving the models in case ...
0 votes
1 answer
64 views

Scheduling: Connecting the end and the beginning of the planning horizon

I would like to create a rota that repeats every 28 days and adheres to the usual rules. These include the minimum/maximum number of consecutive working days and the break days. I have created a model ...
2 votes
1 answer
153 views

How to pass the values of a variable of the first model to a parameter of the second model?

I am working on a scheduling problem which is NP-hard problem. Therefore, I decided to implement two-stage strategy to speed up the solution process. I need to pass the values of a variable from the ...
5 votes
2 answers
558 views

Transform nonlinear cost function to get LP or MILP

I'm trying to schedule power of multiple prosumers in a microgrid. The problem includes a cost function with min and max ...
2 votes
1 answer
149 views

Sensitivity Analysis

In an Operations Research Problem: "A beverage company wants to produce a new juice with a mixed flavor, using only orange and pineapple flavors. Orange flavor contains 5% of vitamin A and 2% of ...
1 vote
0 answers
92 views

Converting a Linear Program with TU Constraint Matrix to a Nonlinear Convex Model: Solver Performance?

I'm currently working on a large Mixed Integer Program (MIP) where the constraint matrix is Totally Unimodular (TU), allowing me to model it as a Linear Program (LP) for efficiency, as total ...
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. ...
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 ...
0 votes
1 answer
82 views

Ensure complete cycle in binary succession matrix LP [PuLP]

I have a set of orders N, for which i have to determine an optimal sequence. I wrap this decision within a binary matrix x[i][j], meaning whether i is succeeded by j. For example [[0 1 0 0] [0 0 1 0] [...
1 vote
0 answers
77 views

Coding Operation research algorithms

Can you suggest good books to refer regarding coding operation research algorithms like transportation algorithm, assignment algorithm etc What are the best practices for coding those algorithms
-1 votes
1 answer
64 views

How to linearize a product of an integer and a binary variable

i have this constraint right here, which is not linear. How would i linearize such a product. $number_t$ is a positive integer and $new_t$ and $reset_t$ are binary. $$number_t = (number_{t-1}+new_t)\...
1 vote
1 answer
64 views

Weighted sum in the objective function

I am working on my actual model. The objective function aims to maximize the preferences related to each criterion pc to select the best contract that fits with the project characteristics( c1= size, ...
2 votes
0 answers
86 views

Re-formulating an LP where a subset of constraints can be loosened?

I have an LP of the structure below (omitting some constraints that are not directly applicable for this question). $$\text{min } c'x$$ $$Ax + By \geq d$$ for a given $A \in R^{m \times a}_{>0}, B \...
0 votes
1 answer
119 views

Generalize working days constraints

I have the following constraints. The first ensures that in my shift plan there are always exactly two days off between blocks of working days and only then does the next block begin. It reads as ...
0 votes
1 answer
125 views

PuLP is ignoring constraints, and setting everything to 0 for minimization problem

I have a multi-objective optimization problem I am trying to solve with competing objectives. I am trying to model a network of industrial businesses which can share wastewater rather than sending it ...
1 vote
1 answer
96 views

Help with formulating the objective function of my subproblem

i have a pretty basic question regarding column generation. I have the following scheduling problem i would like to solve with column generation: \begin{align} &\min\sum_{t}^{}\sum_{s}^{}slack_{ts}...
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, ...
0 votes
0 answers
47 views

Objective/Cost Function Normalization (MPC)

I am trying to develop an MPC. In this MPC, I predict the temperature and try to bring the sensor value to the desired setpoint temperature. I predict the temperature in the next 180 minutes for the ...
2 votes
1 answer
250 views

Replace the constraint using ==> by a linear formulation

I would like to know how to express the continuity constraint without using a decision variable in the conditional form. My challenge is to stay with a linear formulation. I will start to explain my ...
1 vote
1 answer
127 views

How do I linearize such a constraint?

I was wondering, how one would linearize such a constraint, to make it applicable to LPs. $ a_{i}=(a_{i-1}+b_{i})(1-c_{i})-d_{i}$ $a_i$ gives information of the number of assigned jobs to machine $i$. ...
4 votes
0 answers
92 views

Any recommendations for learning about polyhedra and integer programming?

My knowledge on convex polyhedra and systems of linear inequalities (facets, edges, Farkas Lemma, projections, duality, etc.) is very scattered, and I'l like to go through a book to solidify it. I'm ...

1
2 3 4 5
17