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 ...
Siazam's user avatar
  • 11
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 ...
Jarred Wyatt's user avatar
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 ...
Erel Segal-Halevi's user avatar
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 ...
Demitri's user avatar
  • 11
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 (...
Sam's user avatar
  • 87
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*} ...
graphtheory123's user avatar
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 ...
occasional's user avatar
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 ...
Erel Segal-Halevi's user avatar
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(...
Tuong Nguyen Minh's user avatar
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 ...
Marlon Brando's user avatar
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 ...
Erel Segal-Halevi's user avatar
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 ...
Mikkel Honningsvåg Sandhaug's user avatar
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
Shayan Helali's user avatar
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 ...
Vv J's user avatar
  • 19
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$...
Srinivasan B's user avatar
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: ...
Recursion's user avatar
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. ...
XXia's user avatar
  • 49
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 ...
Evan's user avatar
  • 1
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 ...
Baghban's user avatar
  • 131
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 : ...
graphtheory123's user avatar
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, ...
Shanya Tiwari's user avatar
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 ...
Baghban's user avatar
  • 131
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 ...
Sam's user avatar
  • 87
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 ...
graphtheory123's user avatar
-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)\...
Uni ewr's user avatar
  • 21
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
Tharindu Kariyawasam's user avatar
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, ...
Basma Ben Mahmoud's user avatar
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 \...
Mason's user avatar
  • 515
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 ...
Caleb O's user avatar
  • 13
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 ...
nflgreaternba's user avatar
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 ...
lukdooxb1's user avatar
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}...
nflgreaternba's user avatar
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 ...
Basma Ben Mahmoud's user avatar
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$. ...
manofthousandnames's user avatar
0 votes
0 answers
40 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
51 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
46 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
  • 386
2 votes
1 answer
233 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
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 ...
lukdooxb1's user avatar
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 ...
user56202's user avatar
  • 233
1 vote
1 answer
149 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
129 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
95 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
34 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
98 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
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] [...
QuestioningPanda's user avatar
3 votes
1 answer
203 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
84 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
62 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
2 3 4 5
17