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
1 answer
60 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 ...
Sam's user avatar
  • 67
1 vote
0 answers
83 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 ...
graphtheory123's user avatar
-1 votes
1 answer
56 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)\...
Uni ewr's user avatar
  • 21
1 vote
0 answers
69 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
Tharindu Kariyawasam's user avatar
1 vote
1 answer
55 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, ...
Basma Ben Mahmoud's user avatar
2 votes
0 answers
84 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 \...
Mason's user avatar
  • 515
0 votes
1 answer
113 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 ...
Caleb O's user avatar
  • 13
3 votes
1 answer
272 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 ...
nflgreaternba's user avatar
0 votes
1 answer
51 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 ...
lukdooxb1's user avatar
1 vote
1 answer
87 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}...
nflgreaternba's user avatar
2 votes
1 answer
247 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 ...
Basma Ben Mahmoud's user avatar
1 vote
1 answer
119 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$. ...
manofthousandnames's user avatar
0 votes
0 answers
36 views

Proof of Dual Simplex Ratio Test

I have been trying to find proof of the ratio test for Dual Simplex, that is, selecting the variable that enters the base. Specifically, I was interested in knowing why by making that choice, reduced ...
Pedro García's user avatar
2 votes
0 answers
50 views

Implement a rolling horizon approach into a schedulig problem

I have just come across the topic of 'Rolling Horizon' in my literature research and would now like to apply it myself, but unfortunately I don't know where to start. This is my model, which is ...
lukdooxb1's user avatar
1 vote
0 answers
41 views

How to decompose the problem with overlapping blocks?

If the original problem contains the diagonal block structure property or other specific properties then we can apply column generation or other decomposition algorithms to solve it. However, if the ...
ytsao's user avatar
  • 366
2 votes
1 answer
231 views

How to modify a model to be cyclic?

I have the following question. I have the following physician problem with the indices $I$ (doctor), $T$ (days) and $J$ (shifts). $x_{itj}$ is the decision variable, $d_{tj}$ is the demand and $g$ is ...
manofthousandnames's user avatar
0 votes
1 answer
108 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 ...
lukdooxb1's user avatar
4 votes
0 answers
91 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 ...
user56202's user avatar
  • 233
1 vote
1 answer
99 views

Creating a decision variable that is the sum of other variables in PuLP

I'm trying to represent the following problem with PuLP: A car factory needs to maximize profit with an X amount of car models. Each car model has an individual profit and a manufacturing limit, and ...
user avatar
0 votes
1 answer
123 views

Question on Column generation

I am implementing a Column Generation algorithm to solve a set partitioning problem. The master problem takes the form : $\min \sum_{i \in I} c_i \lambda_i$ s.t $\sum_{i \in I} a_{ji} \lambda_i = 1, \...
CHE's user avatar
  • 113
2 votes
1 answer
93 views

How to transfer an objective with separate positive and negative parts into linear programming

I've got to deal with an optimization problem as follows, $$ \begin{aligned} \max_{x,y} & a^Tx+y^TKx\\ {s.t.}&Ax=b\\ &{Cx}\leq d\\ l&\leq y\leq u\end{aligned} $$ where $x \in \bf{R}^n$,...
Kaiming Zhang's user avatar
1 vote
0 answers
33 views

Calling Cplex from R through a MPS-like file

I have a working - and long - R code to generate a mps file to be read by cplex. Because I work with large instances I am finding troubles (too much time) in producing a large mps file. Is there a way ...
Di Al's user avatar
  • 11
2 votes
1 answer
86 views

Solving a weighted XOR-SAT problem

I want to solve a variant of the weighted XOR-SAT problem. Concretely, Given $n$ boolean variables $x_1,\ldots,x_n$ each of which is assigned a non-negative cost $c_1,\ldots,c_n\in\mathbb{R}_{\ge 0}$ ...
nalzok's user avatar
  • 123
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 ...
Clankk's user avatar
  • 1
0 votes
1 answer
81 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] [...
QuestioningPanda's user avatar
3 votes
1 answer
158 views

Warm starting a LP problem with PuLP and Gurobi

I have a set of many similar linear programs (LP). All these LPs have the same objective function, and almost all constraints are the same. The only difference is for one linear constraint $f(x)=a_{i}$...
Quentin PLOUSSARD's user avatar
0 votes
1 answer
62 views

How to set the parameters for GLOP for a DUAL_FEASIBLE case

Now I have a linear programming model, I have tried to formulate this model with or-tools, and then solve it with the GLOP but failed. After reaching the 15-minute time limit, the status of GLOP is ...
Ying's user avatar
  • 105
0 votes
0 answers
61 views

Using docplex with mpmath

In Python 3.10, is it possible to use docplex along with mpmath (https://mpmath.org/), e.g., to compute expressions in constraints and objectives with arbitrary precision?
Stencil's user avatar
  • 101
1 vote
1 answer
153 views

Job Scheduling with Energy Consumption using Linear Programming

I'm looking for some advice for an optimization problem regarding scheduling jobs in a datacenter. So I have a list of jobs and each job has a required time for finishing and a number of cores it has ...
wind.leon's user avatar
2 votes
1 answer
78 views

Reducing optimality to feasibility in non-linear programs

It is well-known that, given a linear program: minimize $c^T x$ such that $A x\leq b$, it is possible to reduce the program to deciding feasibility of the following set of constraints: $Ax \leq b, A^T ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
53 views

Making a batch of related linear problems more efficient

I have a linear system that is of the form $$My = b \\ L \leq y \leq U$$ i.e. all of the $y_i$ are potentially bounded, and there are various linear relationships between them. I want to find the ...
ConMan's user avatar
  • 111
1 vote
0 answers
31 views

Moment based linearization of PDF for LP based optimization

Suppose I’m interested in modeling risk/volatility using the Cauchy distribution and I’d like to optimize some allocations using linear programming. The Cauchy distribution is quadratic in nature but ...
jbuddy_13's user avatar
  • 519
3 votes
2 answers
148 views

Will adding this constraint help my model?

I am solving a maximization problem with continuous variables $x,z\in \mathbb{R}^+$ and binary variable $\delta \in \{0,1\}$. I am maximizing $x$ subject to side constraints and would like to enforce ...
abcd's user avatar
  • 55
1 vote
0 answers
56 views

transform minimize weighted sum of absolute value into a linear optimization

For example, we have an optimization problem $$ \min \sum_{i=1}^{n} |w_{i} - a_{i}| b_{i} \quad \text{s.t.} \quad \sum_{i=1}^{n} c_i w_i = 0 $$ and $a_i, b_i, c_i$ are given. How to convert it into a ...
Pique's user avatar
  • 11
1 vote
1 answer
110 views

Benchmark problems for Benders Decomposition

We are implementing a scheduling model using Benders Decomposition. Does someone know of any existing implementation of Benders or any repositories that contain continuous or integer problems solved ...
Vivek's user avatar
  • 21
0 votes
1 answer
76 views

Sum only over weekend days

I would like to adjust my constraint so that the x are only ever added for the weekend of a week, i.e. days 6,7 and then 13,14 and 20,21 etc.. That would be my previous formulation, but how can I ...
mingabua's user avatar
1 vote
1 answer
74 views

Optimal currency conversion Linear Programming

I have a question about Ex 1.11 of "Linear Optimization" by Bertsimas, Tsitsiklis: Suppose that there are $N$ available currencies, and assume that one unit of currency $i$ can be exchanged ...
Andrew's user avatar
  • 163
0 votes
1 answer
73 views

Problems understanding model notation in LPs

today I came across a paper that uses a type of model notation I have never come across before. These are the objective function and constraints I don't quite understand. I am specifically interested ...
mingabua's user avatar
0 votes
0 answers
93 views

Detect presolve status in pulp model

Hi 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 ...
Bhavya Budhia's user avatar
2 votes
0 answers
35 views

Addressing Variable Multiplication in Constrained Infinity-Norm Maximization with Hypercube & Polyhedron Constraints

I am reaching out to this knowledgeable community for assistance with a complex optimization problem that I have been investigating. Here is the formulation of the problem I'm addressing: $$\tag{1} \...
Diego Fonseca's user avatar
0 votes
1 answer
123 views

Maximum Flow Linear Programming

So this is the maximum flow problem and I have two questions here: Why do we write maximize X_jt and why not X_st, since we want to maximize the flow from the source node to the end node? And why do ...
uni_lad's user avatar
  • 39
1 vote
1 answer
68 views

LP: Constraining the maximum of two variables

I have two variables in an LP problem, a and b, both bound in range $(0,1)$ and constrained such that $a+b=1$. So if a=0.25 then b=0.75. I have added a variable t constrained such that $t \ge a-b$ $t \...
jbuddy_13's user avatar
  • 519
4 votes
2 answers
231 views

Column generation: set partitioning vs set covering

I am working with a column generation algorithm and have noticed that convergence is much faster when my master is a set covering problem ($Ax\ge 1$) compared to when it is a set partitioning problem (...
Rom's user avatar
  • 41
0 votes
2 answers
82 views

"GLPK: No Primal Feasible Solution" for Travelling Salesman Problem (Dantzig–Fulkerson–Johnson formulation)

I have a problem with implementing the Dantzig–Fulkerson–Johnson formulation to solve the following Travelling Salesman Problem: \begin{bmatrix} M & 21 & 17 & 19 & 21 & 22\\ 26 &...
satk0's user avatar
  • 123
2 votes
0 answers
90 views

Understanding the condition of the bounded variable algorithm in the linear programming

Following is the section 7.3 of Operation Research An Introduction by Hamdy A. Taha, Define the upper-bounded LP model as, $$\max z=\{CX|(A,I)X=b,0\leq X\leq U\}$$ The bounded algorithm uses only the ...
N00BMaster's user avatar
1 vote
1 answer
147 views

Primal-Dual Simplex Algorithm

Are there any recommended textbooks or notes to learn the details about the primal-dual simplex algorithm?
Lin Sen's user avatar
  • 25
0 votes
0 answers
69 views

Constants in Penalty Function in Linear Optimization

A constant in a linear optimization problem does not influence the decision variables and thus may be discarded (as in this example: max z = x_1 + 2x_2 + 3x_3 + 37)....
Lukas's user avatar
  • 101
1 vote
0 answers
137 views

Non-Linear objective function due to piecewise component (part 2)

This is a follow up to this question: Non-Linear objective function due to piecewise component Consider a piecewise function but now with three segments but the objective remains the same as: $\sum_{n}...
akkha's user avatar
  • 67
2 votes
1 answer
124 views

logic constraints for IP model

I have been struggling with the formulation of logic constraints. Is there any source you would recommend to understand the topic better or trick of formulation of the constraints?
uni_lad's user avatar
  • 39
1 vote
2 answers
291 views

PuLp is ignoring all of the constraints given to it

I am trying to solve a portfolio optimization problem using PuLP where given a dictionary of stock tickers and their returns for the day, returns a set of weights for each stock such that portfolio ...
Josh Smith's user avatar

1
2 3 4 5
16